# Toward Instance-Optimal State Certification With Incoherent Measurements

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 53 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [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)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)

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

- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [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)
- [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)
- [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)
- [Adaptivity can help exponentially for shadow tomography](https://mlsanity.com/paper/2412.19022/) (2024)
- [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 revisit the basic problem of quantum state certification: given copies of unknown mixed state ρ∈mathbbCd× d and the description of a mixed state σ, decide whether σ = ρ or |σ - ρ|_mathsftr ≥ ε. When σ is maximally mixed, this is mixedness testing, and it is known that Omega(dTheta(1)/ε2) copies are necessary, where the exact exponent depends on the type of measurements the learner can make [OW15, BCL20], and in many of these settings there is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this dTheta(1) dependence for certain kinds of mixed states σ, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional f:mathbbCd× d→ℝ≥ 0 for which one can show that Theta(f(σ)/ε2) copies are necessary and sufficient for state certification with respect to any σ? Such instance-optimal bounds are known in the context of classical distribution testing, e.g. [VV17]. Here we give the first bounds of this nature for the quantum setting, showing (up to log factors) that the copy complexity for state certification using nonadaptive incoherent measurements is essentially given by the copy complexity for mixedness testing times the fidelity between σ and the maximally mixed state. Surprisingly, our bound differs substantially from instance optimal bounds for the classical problem, demonstrating a qualitative difference between the two settings.