Toward Instance-Optimal State Certification With Incoherent Measurements

Abstract

We revisit the basic problem of quantum state certification: given copies of unknown mixed state $\rho \in {\mathbb{C}}^{d\times d}$ and the description of a mixed state $\sigma$, decide whether $\sigma =\rho$ or $\Vert \sigma -\rho {\Vert }_{\mathsf{tr}}\ge \epsilon$. When $\sigma$ is maximally mixed, this is mixedness testing, and it is known that $\Omega (d^{\Theta (1)}/{\epsilon }^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 $d^{\Theta (1)}$ dependence for certain kinds of mixed states $\sigma$, e.g. ones which are approximately low rank? More ambitiously, does there exist a simple functional $f:{\mathbb{C}}^{d\times d}\to {\mathbb{R}}_{\ge 0}$ for which one can show that $\Theta (f(\sigma )/{\epsilon }^2)$ copies are necessary and sufficient for state certification with respect to any $\sigma$? 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 $\sigma$ 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.

arXiv comment52 pages, 1 figure, v2: refined exposition

References in corpus (15)

• Quantum state tomography via compressed sensing
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Direct Fidelity Estimation from Few Pauli Measurements
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Quantum state discrimination and its applications
• Practical characterization of quantum devices without tomography
• Asymptotic Error Rates in Quantum Hypothesis Testing
• Information-theoretic bounds on quantum advantage in machine learning
• Sample-optimal tomography of quantum states
• Models of quantum complexity growth
• Reliable quantum certification for photonic quantum technologies
• Quantum Algorithmic Measurement
• Spectral measures of powers of random matrices
• Quantum Tomography From Few Full-Rank Observables
• Entanglement is Necessary for Optimal Quantum Property Testing

Cited by in corpus (3)

• Statistical Methods for Quantum State Verification and Fidelity Estimation
• Quantum advantages for Pauli channel estimation
• A Hierarchy for Replica Quantum Advantage