aiqbench analysis
This research presents a significant advancement in quantum state certification by demonstrating that optimal testing rates can be achieved with limited entanglement, specifically requiring measurements on only $t = d^2$ copies rather than the previously necessary fully entangled approach. The study establishes near-optimal complexity bounds for high-precision regimes and extends these techniques to mixedness testing and purity estimation, offering a practical pathway to overcome the intractability of joint measurements in quantum systems.
Optimal Quantum State Testing Even with Limited Entanglement
arXiv:2604.07460v2 Announce Type: replace Abstract: 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 testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take $t \geq \Omega(d^2)$ to achieve the optimal rate for certification.
Abstract: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 testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take $t \geq \Omega(d^2)$ to achieve the optimal rate for certification.
v2: Improved lower bounds. 49 pages. Abstract shortened to meet arXiv requirements
Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
arXiv:2604.07460 [quant-ph]
(or arXiv:2604.07460v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2604.07460 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 398 words
