We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are $n$ quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce $k$-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.
We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are n quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce k-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.
Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.
Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).
This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept classCscales asO(∣C∣). This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound toO(VC∗log∣C∗∣), whereC∗is the set of extreme points of the convex closure ofCandVC∗is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling asO(log∣C∗∣). Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.
Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of k-qubit quantum operators, i.e., operations applicable on only k out of d qubits. The problem is studied according to the quantum probably approximately correct (QPAC) model abiding by quantum mechanical laws such as no-cloning, state collapse, and measurement incompatibility. With the delicacy of quantum samples and the richness of quantum operations, one expects a significantly larger quantum sample complexity. This paper proves the contrary. We show that the quantum sample complexity of k-qubit quantum operations is comparable to the classical sample complexity of their counterparts (juntas), at least when dk≪1. This is surprising, especially since sample duplication is prohibited, and measurement incompatibility would lead to an exponentially larger sample complexity with standard methods. Our approach is based on the Pauli decomposition of quantum operators and a technique that we name Quantum Shadow Sampling (QSS) to reduce the sample complexity exponentially. The results are proved by developing (i) a connection between the learning loss and the Pauli decomposition; (ii) a scalable QSS circuit for estimating the Pauli coefficients; and (iii) a quantum algorithm for learning k-qubit operators with sample complexity O(ε2k4klogd).
As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.
Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. Lower bounds on sample complexity in these models were previously established via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. The quantum sample complexity of this problem has been characterised up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, whereas the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharper lower bound for the Quantum Coupon Collector problem via the generalised Holevo-Curlander bounds. All the aspects of the problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest.