# When Does Adaptivity Help for Quantum State Learning?

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 10 Jun 2022.

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

- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [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)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [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)
- [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)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)

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

- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [Learning pure quantum states (almost) without regret](https://mlsanity.com/paper/2406.18370/) (2024)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [An optimal tradeoff between entanglement and copy complexity for state tomography](https://mlsanity.com/paper/2402.16353/) (2024)
- [Quantum state-agnostic work extraction (almost) without dissipation](https://mlsanity.com/paper/2505.09456/) (2025)
- [Tight Lower Bounds for State Tomography with Limited Entanglement](https://mlsanity.com/paper/2609.05718/) (2026)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [Online Learning of Pure States is as Hard as Mixed States](https://mlsanity.com/paper/2502.00823/) (2025)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [Adaptivity can help exponentially for shadow tomography](https://mlsanity.com/paper/2412.19022/) (2024)
- [Learning Pure Quantum States in Any Dimension (Almost) Without Regret](https://mlsanity.com/paper/2605.09019/) (2026)

## Abstract (arXiv)

We consider the classic question of state tomography: given copies of an unknown quantum state ρ∈mathbbCd× d, output widehatρ which is close to ρ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, Theta(d2/ε2) copies are necessary and sufficient to get trace distance ε. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses O(d3/ε2) copies, and multiple papers have posed it as an open question to understand whether or not this rate is tight. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires Omega(d3/ε2) copies, matching the best known upper bound. We do so by a new proof technique which directly bounds the ``tilt'' of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is γ-close in infidelity to ρ using only tildeO(d3/γ) copies, which is optimal for incoherent measurements. In contrast, it is known that any nonadaptive algorithm requires Omega(d3/γ2) copies. While it is folklore that in 2 dimensions, one can achieve a scaling of O(1/γ), to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.