2020/04/16 by Sebastien Bubeck, Sébastien Bubeck, Sitan Chen +4 · 13 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.2004.07869
31 pages, comments welcome
arxiv created 2020/04/16 · openalex publication_date 2020/04/16 · arxiv updated 2020/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 ε-far in trace distance from the maximally mixed state. While it is known how to achieve optimal O(d/ε2) copy complexity using entangled measurements, we show that with independent measurements, Ω(d4/3/ε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.