Abstract Learning problems involve settings in which an algorithm has to make decisions based on data, and possibly side information such as expert knowledge. This study has two main goals. First, it reviews and generalizes different results on the data and model complexity of quantum learning, where the data and/or the algorithm can be quantum, focusing on information‐theoretic techniques. Second, it introduces the notion of copy complexity, which quantifies the number of copies of a quantum state required to achieve a target accuracy level. Copy complexity arises from the destructive nature of quantum measurements, which irreversibly alter the state to be processed, limiting the information that can be extracted about quantum data. As a result, empirical risk minimization is generally inapplicable. The paper presents novel results on the copy complexity for both training and testing. To make the paper self‐contained and approachable by different research communities, an extensive background material is provided on classical results from statistical learning theory, as well as on the distinguishability of quantum states. Throughout, the differences between quantum and classical learning are highlighted by addressing both supervised and unsupervised learning, and extensive pointers are provided to the literature.
Abstract Learning problems involve settings in which an algorithm has to make decisions based on data, and possibly side information such as expert knowledge. This study has two main goals. First, it reviews and generalizes different results on the data and model complexity of quantum learning, where the data and/or the algorithm can be quantum, focusing on information‐theoretic techniques. Second, it introduces the notion of copy complexity, which quantifies the number of copies of a quantum state required to achieve a target accuracy level. Copy complexity arises from the destructive nature of quantum measurements, which irreversibly alter the state to be processed, limiting the information that can be extracted about quantum data. As a result, empirical risk minimization is generally inapplicable. The paper presents novel results on the copy complexity for both training and testing. To make the paper self‐contained and approachable by different research communities, an extensive background material is provided on classical results from statistical learning theory, as well as on the distinguishability of quantum states. Throughout, the differences between quantum and classical learning are highlighted by addressing both supervised and unsupervised learning, and extensive pointers are provided to the literature.
Statistical learning theory provides the mathematical foundations for understanding generalization from finite data. As quantum computing and quantum machine learning continue to develop, there is increasing interest in whether analogous principles can be formulated for learning settings involving quantum data, quantum models, or quantum computation. This paper offers an introductory perspective on quantum statistical learning theory. We begin by recalling the basic ideas of classical statistical learning theory, including empirical risk minimization, hypothesis classes, generalization, and sample complexity, and then discuss how these concepts must be adapted in the quantum setting. In particular, we distinguish between learning with classical data using quantum algorithms, learning with quantum models, and learning directly from quantum data. We then develop a resource-sensitive description that separates population risk, ideal empirical risk, and finite-shot empirical risk. This distinction makes explicit the different roles of training sample size and measurement budget. For a binary measurement-based classifier, we derive a finite-shot condition relating the required measurement budget to the sample size, confidence level, and classification margin. We further discuss how finite-sample generalization, finite-measurement estimation, and hardware imperfections can be represented as distinct contributions to experimentally observed learning performance. We conclude with a discussion of open problems and directions toward a more unified theory of generalization and learnability in quantum learning.
Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning---for which statistical guarantees are available---cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most polynomial speedups over efficient classical algorithms, even in cases where quantum access to the data is naturally available.
This paper reviews recent advances in quantum learning theory for continuous-variable (CV) systems. Quantum learning theory investigates how to extract classical information from quantum systems as efficiently as possible. CV systems are ubiquitous in nature and in quantum technologies, as they describe bosonic and quantum-optical systems. While quantum learning theory for finite-dimensional systems has been extensively studied, the corresponding theory for CV systems has only recently begun to develop; here we provide a concise review. We focus on the following questions: what is the minimum number of copies (the sample complexity) required to learn a non-Gaussian state, possibly under energy constraints? What is the sample complexity for learning Gaussian states? How does the performance of CV state learning depend on non-Gaussianity? How can one test whether a state is Gaussian or far from the set of Gaussian states? And how can Gaussian processes be learned efficiently? Central to these topics, we also review several bounds on the trace distance between CV states in terms of their covariance matrices, which may be of independent interest. Overall, this work summarises selected developments in tomography of CV systems and highlights a selection of open problems.
The ability to extract general laws from a few known examples depends on the complexity of the problem and on the amount of training data. In the quantum setting, the learner's generalization performance is further challenged by the destructive nature of quantum measurements that, together with the no-cloning theorem, limits the amount of information that can be extracted from each training sample. In this paper we focus on hybrid quantum learning techniques where classical machine-learning methods are paired with quantum algorithms and show that, in some settings, the uncertainty coming from a few measurement shots can be the dominant source of errors. We identify an instance of this possibly general issue by focusing on the classification of maximally entangled vs. separable states, showing that this toy problem becomes challenging for learners unaware of entanglement theory. Finally, we introduce an estimator based on classical shadows that performs better in the big data, few copy regime. Our results show that the naive application of classical machine-learning methods to the quantum setting is problematic, and that a better theoretical foundation of quantum learning is required.
In supervised learning, an inductive learning algorithm extracts general rules from observed training instances, then the rules are applied to test instances. We show that this splitting of training and application arises naturally, in the classical setting, from a simple independence requirement with a physical interpretation of being nonsignaling. Thus, two seemingly different definitions of inductive learning happen to coincide. This follows from the properties of classical information that break down in the quantum setup. We prove a quantum de Finetti theorem for quantum channels, which shows that in the quantum case, the equivalence holds in the asymptotic setting, that is, for large numbers of test instances. This reveals a natural analogy between classical learning protocols and their quantum counterparts, justifying a similar treatment, and allowing us to inquire about standard elements in computational learning theory, such as structural risk minimization and sample complexity.
Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan