Entanglement is Necessary for Optimal Quantum Property Testing
Preprint
Abstract
There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent---but possibly adaptively chosen---measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given $d$-dimensional quantum state is equal to or $\epsilon$-far in trace distance from the maximally mixed state. While it is known how to achieve optimal $O(d/\epsilon^2)$ copy complexity using entangled measurements, we show that with independent measurements, $\Omega(d^{4/3}/\epsilon^2)$ is necessary, even if the measurements are chosen adaptively. This resolves a question of Wright. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Quantum Overlapping TomographyPhysical Review Letters, 2020
- On the Power of Conditional Samples in Distribution TestingSIAM Journal on Computing, 2016
- Reliable quantum certification of photonic state preparationsNature Communications, 2015
- Practical Characterization of Quantum Devices without TomographyPhysical Review Letters, 2011
- Barycentric decomposition of quantum measurements in finite dimensionsJournal of Mathematical Physics, 2010
- A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete DataIEEE Transactions on Information Theory, 2008
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Random-matrix theory of quantum transportReviews of Modern Physics, 1997
- Diagrammatic method of integration over the unitary group, with applications to quantum transport in mesoscopic systemsJournal of Mathematical Physics, 1996
- Asymptotic behavior of group integrals in the limit of infinite rankJournal of Mathematical Physics, 1978