Understanding the power of quantum data in machine learning is central to many proposed applications of quantum technologies. While access to quantum data can offer exponential advantages for carefully designed learning tasks and often under strong assumptions on the data distribution, it remains an open question whether such advantages persist in less structured settings and under more realistic, naturally occurring distributions. Motivated by these practical concerns, we introduce a systematic framework based on quantum lossy data compression to bound the power of quantum data in the context of probably approximately correct (PAC) learning. Specifically, we provide lower bounds on the sample complexity of quantum learners for arbitrary functions when data is drawn from Zipf's distribution, a widely used model for the empirical distributions of real-world data. We also establish lower bounds on the size of quantum input data required to learn linear functions, thereby proving the optimality of previous positive results. Beyond learning theory, we show that our framework has applications in secure delegated quantum computation within the measurement-based quantum computation (MBQC) model. In particular, we constrain the amount of private information the server can infer, strengthening the security guarantees of the delegation protocol proposed in (Mantri et al., PRX, 2017) [1].
Understanding the power of quantum data in machine learning is central to many proposed applications of quantum technologies. While access to quantum data can offer exponential advantages for carefully designed learning tasks and often under strong assumptions on the data distribution, it remains an open question whether such advantages persist in less structured settings and under more realistic, naturally occurring distributions. Motivated by these practical concerns, we introduce a systematic framework based on quantum lossy data compression to bound the power of quantum data in the context of probably approximately correct (PAC) learning. Specifically, we provide lower bounds on the sample complexity of quantum learners for arbitrary functions when data is drawn from Zipf's distribution, a widely used model for the empirical distributions of real-world data. We also establish lower bounds on the size of quantum input data required to learn linear functions, thereby proving the optimality of previous positive results. Beyond learning theory, we show that our framework has applications in secure delegated quantum computation within the measurement-based quantum computation (MBQC) model. In particular, we constrain the amount of private information the server can infer, strengthening the security guarantees of the delegation protocol proposed in (Mantri et al., PRX, 2017) [1].
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum information-theoretic quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum information-theoretic quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
Quantum information processing (QIP) studies the representation, manipulation, and transmission of information using quantum systems. By leveraging counterintuitive quantum phenomena such as superposition and entanglement, QIP enables new paradigms for computation, communication, and learning that can surpass classical limits in certain regimes. Foundational tasks in QIP include quantum data compression, quantum communication, and quantum learning and optimization, which together form the basis for scalable quantum technologies. This thesis develops new frameworks and algorithms at the intersection of quantum information theory, quantum learning, and quantum-inspired modeling. The thesis is organized into three parts. The first part studies quantum compression problems; the second addresses quantum communication; and the third develops quantum learning and optimization frameworks with applications to complex systems. In the first part, a new formulation for lossy quantum-classical source coding, termed rate-channel theory, is introduced, replacing the conventional distortion-based formulation with a posterior-channel-based framework under a block-error criterion. The framework is further generalized to incorporate quantum side information at the decoder. A connection between rate-channel theory and classical rate-distortion theory is also established, showing that optimal rate-distortion performance can be recovered under suitable conditions. These results provide a unified and flexible framework for data compression, which is essential for scalable quantum computing infrastructure, enabling efficient storage of quantum data, such as outputs from quantum sensors (e.g., MRI) and information encoded in photonic systems for satellite and optical communication. In the second part, the problem of computing functions of distributed sources over classical-quantum multiple access channels is studied. A new coding framework is developed that combines algebraic structured codes with unstructured random coding techniques, enabling efficient communication of functions without reconstructing individual sources. The resulting achievable conditions, expressed in terms of single-letter quantum information quantities, strictly enlarge the class of sources for which reliable computation is possible. These results contribute to the theoretical foundations of quantum network communication and are directly relevant to deep-space satellite-based quantum communication, distributed quantum computing, and the design of scalable quantum network infrastructures. In the final part, new approaches to quantum learning and optimization are developed. A geometry-aware quantum optimization framework is proposed based on a novel quantum information metric and an unbiased estimator constructed from single-shot measurements. This leads to an optimization method with constant sample complexity per iteration and provable exponential convergence under mild conditions, while avoiding saddle points and local minima. Such advances are particularly relevant for challenging optimization tasks in quantum sensing and quantum computational modeling of many-body systems. Building on this optimization framework, a Hamiltonian learning approach is introduced to infer interaction structures from time-resolved measurement data, with finite-sample guarantees and polynomial scaling with system size. This framework is further extended to develop a quantum-inspired generative model for gene regulatory network inference, where interactions are encoded as a parameterized Hamiltonian evolving over pseudotime. The proposed methods demonstrate strong performance on synthetic benchmarks and reveal biologically meaningful structures in real-world data, with applications to multi-omics integration, cancer genomics, and systems biology. Overall, this thesis advances the theoretical and algorithmic foundations of quantum information processing, with contributions spanning compression, communication, and learning. These developments support the design of resource-efficient and scalable quantum technologies, enabling applications in quantum sensing, quantum networks, distributed quantum computation, and the modeling of complex physical and biological systems.
Abstract Quantum learning models hold the potential to bring computational advantages over the classical realm. As powerful quantum servers become available on the cloud, ensuring the protection of clients’ private data becomes crucial. By incorporating quantum homomorphic encryption schemes, we present a general framework that enables quantum delegated and federated learning with a computation-theoretical data privacy guarantee. We show that learning and inference under this framework feature substantially lower communication complexity compared with schemes based on blind quantum computing. In addition, in the proposed quantum federated learning scenario, there is less computational burden on local quantum devices from the client side, since the server can operate on encrypted quantum data without extracting any information. We further prove that certain quantum speedups in supervised learning carry over to private delegated learning scenarios employing quantum kernel methods. Our results provide a valuable guide toward privacy-guaranteed quantum learning on the cloud, which may benefit future studies and security-related applications.
Generalization is a central concept in machine learning theory, yet for quantum models, it is predominantly analyzed through uniform bounds that depend on a model's overall capacity rather than the specific function learned. These capacity-based uniform bounds are often too loose and entirely insensitive to the actual training and learning process. Previous theoretical guarantees have failed to provide non-uniform, data-dependent bounds that reflect the specific properties of the learned solution rather than the worst-case behavior of the entire hypothesis class. To address this limitation, we derive the first PAC-Bayesian generalization bounds for a broad class of quantum models by analyzing layered circuits composed of general quantum channels, which include dissipative operations such as mid-circuit measurements and feedforward. Through a channel perturbation analysis, we establish non-uniform bounds that depend on the norms of learned parameter matrices; we extend these results to symmetry-constrained equivariant quantum models; and we validate our theoretical framework with numerical experiments. This work provides actionable model design insights and establishes a foundational tool for a more nuanced understanding of generalization in quantum machine learning.
This thesis consists of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. \n \nWe first study the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially higher communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed. We show that an ensemble given by Jain, Radhakrishnan, and Sen (ICALP'03) cannot be compressed by more than a constant number of qubits without shared entanglement, while in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. \n \nNext, we study the task of quantum state redistribution, the most general version of compression of quantum states. We design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to connect quantum state redistribution and Markov chains and gives an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. \n \nIn the last part, we focus on quantum algorithms for learning Boolean functions using quantum examples. We consider two commonly studied models of learning, namely, quantum PAC learning and quantum agnostic learning. We reproduce the optimal lower bounds by Arunachalam and de Wolf (JMLR’18) for the sample complexity of either of these models using information theory and spectral analysis. Our proofs are simpler than the previous ones and the techniques can be possibly extended to similar scenarios.