Quantum Mixedness Testing with Pauli Measurements

Abstract

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho ={\mathbb{I}}_d/d$ or $\Vert \rho -{\mathbb{I}}_d/d{\Vert }_1\ge \epsilon$ with high probability, where $d=2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n=\tilde{\Theta }\left({\sqrt{10}}^N/{\epsilon }^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube.