Optimal Quantum State Testing Even with Limited Entanglement
This addresses a tractability issue in quantum information processing for certifying high-dimensional states with high precision, though it is incremental as it builds on known testing and learning frameworks.
The paper tackles the problem of quantum state certification with limited entanglement, showing that near-optimal rates can be achieved using measurements on only t = d^2 copies at once, which improves over fully entangled protocols in the high-precision regime.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $Ï$, test whether it matches some target state $Ï$ or is $ε$-far from it. For certifying $d$-dimensional states, $Î(d/ε^2)$ copies of $Ï$ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all $O(d/ε^2)$ copies of $Ï$. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on $t$ copies at once, for some $1 < t \ll d/ε^2$. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d^2$. In the high-precision regime, i.e., for $ε< \frac{1}{\sqrt{d}}$, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d^2$ as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our upper bounds with smooth lower bounds that imply joint measurements on $t \geq d^{Ω(1)}$ copies are necessary to achieve optimal rates for certification in the high-precision regime.