# Lower Bounds for Learning Quantum States with Single-Copy Measurements

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 29 Jul 2022.

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

- [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)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)

## Built on by (most cited first, 8 of 8)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Tight Lower Bounds for State Tomography with Limited Entanglement](https://mlsanity.com/paper/2609.05718/) (2026)
- [Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem](https://mlsanity.com/paper/2405.07226/) (2024)
- [Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements](https://mlsanity.com/paper/2609.10514/) (2026)
- [Advantage of Entangled Learning Rules in Quantum Measurement Class Learning](https://mlsanity.com/paper/2610.07328/) (2026)

## Abstract (arXiv)

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d-dimensional state. We first revisit a known lower bound due to Haah et al. (2017) on quantum tomography with accuracy ε in trace distance, when the measurements choices are independent of previously observed outcomes (i.e., they are nonadaptive). We give a succinct proof of this result. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes. In particular, this rigorously establishes the optimality of the folklore ``Pauli tomography" algorithm in terms of its sample complexity. We also derive novel bounds of Omega(r2 d/ε2) and Omega(r2 d2/ε2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of different measurements used by an algorithm. We extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp(O(d)) measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.