Coherence in Property Testing: Quantum-Classical Collapses and Separations

Understanding the power and limitations of classical and quantum information and how they differ is a fundamental endeavor. In property testing of distributions, a tester is given samples over a typically large domain \{0,1\}ⁿ. An important property is the support size both of distributions [Valiant and Valiant, STOC'11], as well, as of quantum states. Classically, even given 2^n/16 samples, no tester can distinguish distributions of support size 2^n/8 from 2^n/4 with probability better than 2^-Θ(n), even promised they are flat. Quantum states can be in a coherent superposition of states of \{0,1\}ⁿ, so one may ask if coherence can enhance property testing. Flat distributions naturally correspond to subset states, |φ_S rangle=1/sqrt{|S|}sum_{iin S}|irangle. We show that coherence alone is not enough, Coherence limitations: Given 2^n/16 copies, no tester can distinguish subset states of size 2^n/8 from 2^n/4 with probability better than 2^-Θ(n). The hardness persists even with multiple public-coin AM provers, Classical hardness with provers: Given 2^O(n) samples from a distribution and 2^O(n) communication with AM provers, no tester can estimate the support size up to factors 2^Ω(n) with probability better than 2^-Θ(n). Our result is tight. In contrast, coherent subset state proofs suffice to improve testability exponentially, Quantum advantage with certificates: With poly-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, Collapse of QMA: A general proof cannot improve testability of any quantum property whatsoever. We also show connections to disentangler and quantum-to-quantum transformation lower bounds.