Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
For researchers in distribution testing and quantum verification, this work provides a new model and efficient algorithms that relax independence assumptions and reduce sample complexity.
The paper tackles distribution identity testing under a realistic model where the unknown distribution is efficiently samplable and samples can be adversarially correlated. It shows that polynomially many samples suffice for verification, overcoming the exponential sample complexity of standard identity testing.
One of the most fundamental problems in distribution testing is the identity testing problem: given samples $x_1,\ldots,x_s$, the goal is to determine whether the samples are drawn from a target distribution $\mathcal{D}$. When $\mathcal{D}$ is a distribution over $\bit^n$, the optimal sample complexity of identity testing is known to be $Ω(\sqrt{2^n})$. Furthermore, most existing results assume that the samples $x_1,\ldots,x_s$ are generated independently from an unknown distribution. In this work, we overcome both of these limitations by initiating study of distribution testing in a more realistic setting. In our model, the unknown distribution is promised to be efficiently samplable, while allowing the observed samples $x_1,\ldots,x_s$ to be adversarially generated and arbitrarily correlated. Under this model, we show that polynomially many samples suffice to verify distributions. We further characterize the computational complexity of verifying classically- and quantumly-samplable distributions. Our techniques also extend to verifications of quantum states. In establishing some of our results, we employ Kolmogorov complexity techniques in a novel manner. We also present multiple applications of Kolmogorov complexity that are of independent interest. In particular, we show that certified randomness with a classical efficient prover can be achieved without computational assumptions when inefficient verification is allowed. Furthermore, we also show that a natural quantum extension of a well-studied Kolmogorov complexity measure provides a good benchmark for certifying sampling-based quantum advantage.