# Instance-Optimal Quantum State Certification with Entangled Measurements

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 8 Jul 2025.

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

- [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)
- [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)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Few Single-Qubit Measurements Suffice to Certify Any Quantum State](https://mlsanity.com/paper/2506.11355/) (2025)

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

- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)

## Abstract (arXiv)

We consider the task of quantum state certification: given a description of a hypothesis state σ and multiple copies of an unknown state ρ, a tester aims to determine whether the two states are equal or ε-far in trace distance. It is known that Theta(d/ε2) copies of ρ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies [CHW07,OW15,BOW19]. However, these bounds are for a worst-case σ, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies [CLO22,CLHL22], they remained open when testers are unrestricted in the kind of measurements they can perform. We address this open question by proving nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements. Analogously to the unentangled setting, we show that the optimal copy complexity for certifying σ is given by the worst-case complexity times the fidelity between σ and the maximally mixed state. We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest. This method also allows us to recover the Omega(d/ε2) lower bound for mixedness testing [OW15], i.e., certification of the maximally mixed state, with a surprisingly simple proof.