In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, ai∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, ai∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).
We study the power of quantum memory for learning properties of quantum systems and dynamics, which is of great importance in physics and chemistry. Many state-of-the-art learning algorithms require access to an additional external quantum memory. While such a quantum memory is not required a priori, in many cases, algorithms that do not utilize quantum memory require much more data than those which do. We show that this trade-off is inherent in a wide range of learning problems. Our results include the following: •We show that to perform shadow tomography on ann-qubit stateρwithMobservables, any algorithm without quantum memory requiresΩ~(min(M,2n))samples ofρin the worst case. Up to log factors, this matches the upper bound of [1], and completely resolves an open question in [2], [3]. •We establish exponential separations between algorithms with and without quantum memory for purity testing, distinguishing scrambling and depolarizing evolutions, and uncovering symmetry in physical dynamics. Our separations improve and generalize prior work of [4] by allowing for a broader class of algorithms without quantum memory. •We give the first tradeoff between quantum memory and sample complexity. More precisely, we prove that to estimate absolute values of alln-qubit Pauli observables, algorithms withk<nqubits of quantum memory require at leastΩ(2(n−k)/3)samples, but there is an algorithm usingn-qubit quantum memory which only requiresO(n)samples. The separations we show are sufficiently large and could already be evident, for instance, with tens of qubits. This provides a concrete path towards demonstrating real-world advantage for learning algorithms with quantum memory.
We study the power of quantum memory for learning properties of quantum systems and dynamics, which is of great importance in physics and chemistry. Many state-of-the-art learning algorithms require access to an additional external quantum memory. While such a quantum memory is not required a priori, in many cases, algorithms that do not utilize quantum memory require much more data than those which do. We show that this trade-off is inherent in a wide range of learning problems. Our results include the following: (1) We show that to perform shadow tomography on an n-qubit state rho with M observables, any algorithm without quantum memory requires Ω(min(M,2n)) samples of rho in the worst case. Up to logarithmic factors, this matches the upper bound of [HKP20] and completely resolves an open question in [Aar18, AR19]. (2) We establish exponential separations between algorithms with and without quantum memory for purity testing, distinguishing scrambling and depolarizing evolutions, as well as uncovering symmetry in physical dynamics. Our separations improve and generalize prior work of [ACQ21] by allowing for a broader class of algorithms without quantum memory. (3) We give the first tradeoff between quantum memory and sample complexity. We prove that to estimate absolute values of all n-qubit Pauli observables, algorithms with k<n qubits of quantum memory require at least Ω(2(n−k)/3) samples, but there is an algorithm using n-qubit quantum memory which only requires O(n) samples. The separations we show are sufficiently large and could already be evident, for instance, with tens of qubits. This provides a concrete path towards demonstrating real-world advantage for learning algorithms with quantum memory.
We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S> of its elements. One can think of |S>=∑_{i∈S}|i>/√|S| as the quantum version of a uniformly random sample over S, as in the classical analysis of the "coupon collector problem." We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n-k=O(1) missing elements then O(k) copies of |S> suffice, in contrast to the Θ(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Ω(k), then Ω(k log k) quantum samples are necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S>. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using 6 copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that
(1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group.
(2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n2/k).
As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0<c<1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.
Abstract The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein–Vazirani algorithm (Bernstein and Vazirani, in: Kosaraju (ed) Proceedings of the twenty-fifth annual ACM symposium on theory of computing, ACM, New York, 1993. 10.1145/167088.167097 ). A similar strategy can be applied in the case of noisy quantum training data, as was observed in Grilo et al. (Learning with errors is easy with quantum samples, 2017). However, extensions of these learning algorithms beyond the uniform distribution have not yet been studied. We employ the biased quantum Fourier transform introduced in Kanade et al. (Learning dnfs under product distributions via μ μ -biased quantum Fourier sampling, 2018) to develop efficient quantum algorithms for learning Boolean linear functions on n bits from quantum examples w.r.t. a biased product distribution. Our first procedure is applicable to any (except full) bias and requires O(ln(n)) O(ln(n)) quantum examples. The number of quantum examples used by our second algorithm is independent of n, but the strategy is applicable only for small bias. Moreover, we show that the second procedure is stable w.r.t. noisy training data and w.r.t. faulty quantum gates. This also enables us to solve a version of the learning problem in which the underlying distribution is not known in advance. Finally, we prove lower bounds on the classical and quantum sample complexities of the learning problem. Whereas classically, Ω(n) Ω(n) examples are necessary independently of the bias, we are able to establish a quantum sample complexity lower bound of Ω(ln(n)) Ω(ln(n)) only under an assumption of large bias. Nevertheless, this allows for a discussion of the performance of our suggested learning algorithms w.r.t. sample complexity. With our analysis, we contribute to a more quantitative understanding of the power and limitations of quantum training data for learning classical functions.
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, letCbe a class of polynomial-size concepts, and suppose thatCcan be PAC-learned with membership queries under the uniform distribution with error1/2−γby a timeTquantum algorithm. We prove that ifγ2⋅T≪2n/n, thenBQE⊂C, whereBQE=BQTIME[2O(n)]is an exponential-time analogue ofBQP. This result is optimal in bothγandT, since it is not hard to learn any classCof functions in (classical) timeT=2n(with no error), or in quantum timeT=poly(n)with error at most1/2−Ω(2−n/2)via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.