# Tight Bounds for Quantum State Certification with Incoherent Measurements

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 39 references that are in the map.
- First posted on arXiv 14 Apr 2022.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [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)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [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)

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

- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)
- [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)
- [Optimal high-precision shadow estimation](https://mlsanity.com/paper/2407.13874/) (2024)
- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [Purest Quantum State Identification](https://mlsanity.com/paper/2502.14334/) (2025)
- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)

## Abstract (arXiv)

We consider the problem of quantum state certification, where we are given the description of a mixed state σ ∈ mathbbCd × d, n copies of a mixed state ρ ∈ mathbbCd × d, and varepsilon > 0, and we are asked to determine whether ρ = σ or whether | ρ - σ |1 > varepsilon. When σ is the maximally mixed state frac1d Id, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of ρ at a time. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs O(d3/2 / varepsilon2) copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only Omega (d4/3 / varepsilon2) [Bubeck-Chen-Li '20], and it has been an outstanding open problem to close this polynomial gap. In this work, 1) we settle the copy complexity of mixedness testing with incoherent measurements and show that Omega (d3/2 / varepsilon2) copies are necessary, and 2) we show the instance-optimal bounds for state certification to general σ first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding certain matrix martingales, which we believe may be of independent interest.