Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement.
In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.
Comments
37 pages, 3 figures. Added explanatory figures, simplified parts of the proofs, and revised the exposition. Main results unchanged
Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement.
In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.
In learning theory, the VC dimension of a concept class C is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept c∈C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model
Θ(dϵ+log(1/δ)ϵ)
examples are necessary and sufficient for a learner to output, with probability 1−δ, a hypothesis h that is ϵ-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c∈C, we know that
Θ(dϵ2+log(1/δ)ϵ2)
examples are necessary and sufficient to output an hypothesis h∈C whose error is at most ϵ worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is
Ω(d1−ηϵ+d+log(1/δ)ϵ) for arbitrarily small constant η>0.
Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ϵ) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of \emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an ϵ-approximate of an unknown quantum process c∗ from a known finite concept class C with probability 1−δ using samples {(x1,c∗(x1)),(x2,c∗(x2)),…}, where {x1,x2,…} are computational basis states sampled from an unknown distribution D and {c∗(x1),c∗(x2),…} are the (possibly mixed) quantum states outputted by c∗. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state c∗ from an known finite set C, and we want to learn with probability 1−δ an ϵ-approximate of c∗ with as few copies of c∗ as possible. We show that the problem of PAC learning quantum process can be solved with O(ϵ2log∣C∣+log(1/δ)) samples when the outputs are pure states and O(ϵ2log3∣C∣(log∣C∣+log(1/δ))) samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size ∣C∣ is exponential in the number of qubits, an exponentially improvement over a full state tomography.
$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\eps} + \frac{\log(1/δ)}{\eps}\Big) $$ examples are necessary and sufficient for a learner to output, with probability 1−δ, a hypothesis h that is $\eps$-close to the target concept c. In the related agnostic model, where the samples need not come from a c∈C, we know that $$ Θ\Big(\frac{d}{\eps^2} + \frac{\log(1/δ)}{\eps^2}\Big) $$ examples are necessary and sufficient to output an hypothesis h∈C whose error is at most $\eps$ worse than the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting, quantum examples cannot be much more powerful: the required number of quantum examples is $$ Ω\Big(\frac{d^{1-η}}{\eps} + d + \frac{\log(1/δ)}{\eps}\Big)\mbox{ for all }η> 0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\eps)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors.
A fundamental question in PAC learning is determining the number of labeled examples required to learn a concept class to a desired accuracy and confidence. In classical learning theory, this quantity is characterized by the VC-dimension, while several quantum generalizations have established analogous results when examples are provided in quantum superposition. In this work, we study a distinct quantum PAC-learning model in which concepts are functions acting on quantum states. We demonstrate that the VC-dimension, although still relevant, fails to fully capture the sample complexity of this model. To further characterize this setting, we develop a new lower bound on the required number of samples and establish an upper bound when the states in the domain are linearly independent. Remarkably, this upper bound has a form similar to the classical PAC-learning bound. We further examine a setting in which the learner receives more informative data and show that the limitations of the VC-dimension persist in this extended model.
We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.
Studies addressing the question Can a learner complete the learning securely? have recently been spurred from the standpoints of fundamental theory and potential applications. In the relevant context of this question, we present a classical-quantum hybrid sampling protocol and define a security condition that allows only legitimate learners to prepare a finite set of samples that guarantees the success of the learning; the security condition excludes intruders. We do this by combining our security concept with the bound of the so-called probably approximately correct (PAC) learning, and therefore, we call the condition quantum secure PAC learning condition. We show that while the lower bound on the learning samples guarantees PAC learning, an upper bound can be derived to rule out adversarial learners. Such a secure learning condition is appealing, because it is defined only by the size of samples required for the successful learning and is independent of the algorithm employed. Notably, the security stems from the fundamental quantum no-broadcasting principle. No such condition can thus occur in any classical regime, where learning samples can be copied. Owing to the hybrid architecture, our scheme also offers a practical advantage for implementation in noisy intermediate-scale quantum (NISQ) devices.