Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
This paper introduces a cryptographic framework for distribution and quantum state testing that overcomes traditional sample complexity and independence limitations by proving that polynomially many samples suffice to verify efficiently samplable distributions even when samples are adversarially generated and correlated, utilizing novel Kolmogorov complexity techniques to achieve these results and enable applications like assumption-free certified randomness and quantum advantage benchmarking.