2025/07/08 by Ryan O'Donnell, O'Donnell, Ryan, Chirag Wadhwa +1 · 1 voice · 4 citations
#quant-ph #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.2507.06010
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 Θ(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 Ω(d/ε2) lower bound for mixedness testing [OW15], i.e., certification of the maximally mixed state, with a surprisingly simple proof.