Toward Instance-Optimal State Certification With Incoherent Measurements

  • 2021-02-25 18:59:11
  • Sitan Chen, Jerry Li, Ryan O'Donnell
  • 0

Abstract

We revisit the basic problem of quantum state certification: given copies ofunknown mixed state $\rho\in\mathbb{C}^{d\times d}$ and the description of amixed state $\sigma$, decide whether $\sigma = \rho$ or $\|\sigma -\rho\|_{\mathsf{tr}} \ge \epsilon$. When $\sigma$ is maximally mixed, this ismixedness testing, and it is known that $\Omega(d^{\Theta(1)}/\epsilon^2)$copies are necessary, where the exact exponent depends on the type ofmeasurements the learner can make [OW15, BCL20], and in many of these settingsthere is a matching upper bound [OW15, BOW19, BCL20]. Can one avoid this $d^{\Theta(1)}$ dependence for certain kinds of mixedstates $\sigma$, e.g. ones which are approximately low rank? More ambitiously,does there exist a simple functional $f:\mathbb{C}^{d\timesd}\to\mathbb{R}_{\ge 0}$ for which one can show that$\Theta(f(\sigma)/\epsilon^2)$ copies are necessary and sufficient for statecertification with respect to any $\sigma$? Such instance-optimal bounds areknown 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 usingnonadaptive incoherent measurements is essentially given by the copy complexityfor mixedness testing times the fidelity between $\sigma$ and the maximallymixed state. Surprisingly, our bound differs substantially from instanceoptimal bounds for the classical problem, demonstrating a qualitativedifference between the two settings.

 

Quick Read (beta)

loading the full paper ...