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.