Entanglement is Necessary for Optimal Quantum Property Testing

There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [OW15, OW16, HHJ + 17, OW17, AISW19, BOW19]. 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, Ω(d 4/3 /ǫ 2 ) is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [Wri16]. 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.