Entanglement is Necessary for Optimal Quantum Property Testing

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.

arXiv comment31 pages, comments welcome

References in corpus (14)

• Random-Matrix Theory of Quantum Transport
• Direct Fidelity Estimation from Few Pauli Measurements
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Practical characterization of quantum devices without tomography
• Diagrammatic method of integration over the unitary group, with applications to quantum transport in mesoscopic systems
• Asymptotic Error Rates in Quantum Hypothesis Testing
• Quantum Overlapping Tomography
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Reliable quantum certification for photonic quantum technologies
• Systematic approach to statistics of conductance and shot-noise in chaotic cavities
• Spectral measures of powers of random matrices
• Property Testing of Joint Distributions using Conditional Samples
• A Chasm Between Identity and Equivalence Testing with Conditional Queries
• Adaptive Lower Bound for Testing Monotonicity on the Line

Cited by in corpus (6)

• Quantum statistical query learning
• Improved quantum data analysis
• Toward Instance-Optimal State Certification With Incoherent Measurements
• Sample optimal Quantum identity testing via Pauli Measurements
• Quantum Proofs of Proximity
• Testing identity of collections of quantum states: sample complexity analysis