Optimal Quantum State Testing Even with Limited Entanglement

Quantum Physics [Submitted on 8 Apr 2026] Optimal Quantum State Testing Even with Limited Entanglement Chirag Wadhwa, Sitan Chen In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state \rho, test whether it matches some target state \sigma or is \epsilon-far from it. For certifying d-dimensional states, \Theta(d/\epsilon^2) copies of \rho are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/\epsilon^2) copies of \rho. 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/\epsilon^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 \epsilon < \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^{\Omega(1)} copies are necessary to achieve optimal rates for certification in the high-precision regime. Comments: 45 pages. Abstract shortened to meet arXiv requirements Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2604.07460 [quant-ph]   (or arXiv:2604.07460v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.07460 Focus to learn more Submission history From: Chirag Wadhwa [view email] [v1] Wed, 8 Apr 2026 18:01:51 UTC (57 KB) Access Paper: view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.DS References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)