Paper Info
Title
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 [1]-[6]. 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 ε-far in trace distance from the maximally mixed state. While it is known how to achieve optimal O(d/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) copy complexity using entangled measurements, we show that with independent measurements, Ω(d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4/3</sup> /ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. 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.
Year
DOI
Venue
2020
10.1109/FOCS46700.2020.00070
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
ISSN
quantum property testing,quantum tomography,distribution testing
Conference
1523-8288
ISBN
Citations 
PageRank 
978-1-7281-9622-0
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Sébastien Bubeck1147292.28
Sitan Chen216.46
Jerry Li322922.67