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 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.
We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state ∣ψ⟩ for Bob to recover any expectation value ⟨ψ∣M∣ψ⟩ given an observable M with M Hermitian and ∣∣M∣∣op≤1. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of Ω(2nε−2) on the one-way randomized classical communication, improving upon an additive error lower bound of Ω(2n) as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a Ω(2n) versus O(poly(n)) separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an Ω(2nε−2) lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an Ω(nε−2) lower bound when restricted to Paulis, and an Ω(2nε−2) lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.
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.
Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.