Understanding the power and limitations of classical and quantum information, and how they differ, is an important endeavor. On the classical side, property testing of distributions is a fundamental task: a tester, given samples of a distribution over a typically large domain such as $\{0,1\}^n$, is asked to verify properties of the distribution. A key property of interest in this paper is the support size both of distributions, a central problem classically [Valiant and Valiant STOC'11], as well, as of quantum states. Classically, even given $2^{n/16}$ samples, no tester can distinguish between distributions of support size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-\Theta(n)}$, even with the promise that they are flat distributions.
In the quantum setting, quantum states can be in a coherent superposition of many states of $\{0,1\}^n$, providing a global description of probability distributions. One may ask if coherence can enhance property testing. A natural way to encode a flat distribution is via the subset states, $|\phi_S \rangle = 1/\sqrt{| S |} \sum_{i \in S} |i\rangle$. We show that coherence alone is not enough to improve the testability of support size.
(1) Coherence limitations. Given $2^{n/16}$ copies, no tester can distinguish between subset states of size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-\Theta(n)}$.
Our result is more general and establishes the indistinguishability between the subset states and the Haar random states leading to new constructions of pseudorandom and pseudoentangled states, resolving an open problem of [Ji, Liu and Song, CRYPTO'18].
The hardness persists even when allowing multiple public-coin AM provers for a classical tester.
(2) Classical hardness with provers. Given $2^{O(n)}$ samples from a classical distribution and $2^{O(n)}$ communication with multiple independent AM provers, no classical tester can estimate the support size up to factors $2^{\Omega(n)}$ with probability better than $2^{-\Theta(n)}$. Our hardness result is tight.
In contrast, coherent subset state proofs suffice to improve testability exponentially,
(3) Quantum advantage with certificates. With polynomially many copies and subset state proofs, a tester can approximate the support size of a subset state of arbitrary size.
Some structural assumption on the quantum proofs is required since we show that
(4) Collapse of QMA. A general proof cannot information-theoretically
improve testability of any quantum property whatsoever.
Our results highlight both the power and limitations of coherence in property testing, establishing exponential quantum-classical separations across various parameters. We also show several connections and implications of the study of property testing, in particular, in establishing quantum-to-quantum state transformation lower bounds, and to disentangler lower bounds.
