# Exponential separations between learning with and without quantum memory

arXiv: https://arxiv.org/abs/2111.05881 · HTML: https://mlsanity.com/paper/2111.05881/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 69 references that are in the map.
- First posted on arXiv 10 Nov 2021.

## Builds on (most cited first, 13 of 13)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Efficient estimation of Pauli observables by derandomization](https://mlsanity.com/paper/2103.07510/) (2021)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)
- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)

## Built on by (most cited first, 30 of 52)

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Representation Theory for Geometric Quantum Machine Learning](https://mlsanity.com/paper/2210.07980/) (2022)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [On quantum backpropagation, information reuse, and cheating measurement collapse](https://mlsanity.com/paper/2305.13362/) (2023)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Improved machine learning algorithm for predicting ground state properties](https://mlsanity.com/paper/2301.13169/) (2023)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [Revisiting dequantization and quantum advantage in learning tasks](https://mlsanity.com/paper/2112.00811/) (2021)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [The power and limitations of learning quantum dynamics incoherently](https://mlsanity.com/paper/2303.12834/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [Learning k-body Hamiltonians via compressed sensing](https://mlsanity.com/paper/2410.18928/) (2024)
- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)
- [Intelligent Computing: The Latest Advances, Challenges and Future](https://mlsanity.com/paper/2211.11281/) (2022)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)

## Abstract (arXiv)

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 Omega(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 Omega(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.