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 [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
$\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 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.