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.
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know that blind delegation protocols can achieve information-theoretic security. In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating BQP computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with O(nd) bits of classical communication implies that BQP⊂MA/O(nd). We conjecture that this containment is unlikely by providing an oracle relative to which BQP⊂MA/O(nd). We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, then there exist non-uniform circuits of size 2n−Ω(n/log(n)), making polynomially-sized queries to an NPNP oracle, for computing the permanent of an n×n matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol, namely QCMA/qpoly∩coQCMA/qpoly. Then, we show that having such a protocol for delegating NP-hard functions implies coNPNPNP⊆NPNPPromiseQMA.
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.
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.
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.