Property testing is a fundamental task both classically and quantumly. There is a wealth of results investigating property testing of classical probability distributions, where a tester is given samples of a distribution typically over a large domain, say  for large n. A central classical result is that to verify the support size of an unknown distribution requires  (Valiant&Valiant, STOC11) . In fact, to distinguish vastly different support sizes of flat distributions is hard: even given  samples, no tester can distinguish between flat distributions of support size  from  with probability better than  .

In the quantum setting, quantum states can be in a coherent superposition of many states of  , in particular, allowing a more global description of probability distributions. One can then ask how much coherence helps property testing. A natural way to encode a flat distribution is via subset states,   . We show that coherence alone is not enough to improve the testability of support size, (1) Even given  copies, no tester can distinguish between subset states of size  from  with probability better than  . In fact, we obtain a more general result showing that subset states are indistinguishable from Haar random states provided the support size is not too small nor too large. This also provides new constructions of pseudorandom (PRS) and pseudoentangled states. 

Given that standard property testing fails badly here, we enhance these models by allowing multiple provers. In particular, we show that  even interacting with multiple AM provers, classical property testing still fails, (2) Even given  samples from a classical distributions and interacting with  AM provers in  rounds, no classical tester can estimate the support size up to factors  with probability better than  . We obtain this classical lower bound via a curious reduction to fast mixing of high-dimensional expanders.

In contrast, we show that coherent subset state proofs suffice to improve testability exponentially, (3) With just polynomially many copies and subset state proofs, a tester can, with high probability, approximate the support size of a subset state of arbitrary size, or detect that the certificates are malicious. Our results show some of the power and limitations of coherence in property testing for a natural property and establish quantum-classical separations that are exponential in various parameters. 

Pei Wu obtained his PhD from UCLA. He is currently is a postdoc research fellow at the Weizmann Institute of Science. His research interest lies in theoretical computer science. He will start as an assistant professor at Pennsylvania State University, Fall 2024.