The role of shared randomness in quantum state certification with unentangled measurements

Abstract

Given $n$ copies of an unknown quantum state $\rho \in {\mathbb{C}}^{d\times d}$, quantum state certification is the task of determining whether $\rho ={\rho }_0$ or $\Vert \rho -{\rho }_0{\Vert }_1>\epsilon$, where ${\rho }_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $\rho$ at a time. When there is a common source of shared randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $\Theta (d^{3/2}/{\epsilon }^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that $\Theta (d^2/{\epsilon }^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without shared randomness. We develop a unified lower bound framework for both fixed and randomized measurements, under the same theoretical framework that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.

29 pages, 2 tables. Comments welcome