On Cryptography and Distribution Verification, with Applications to Quantum Advantage

Abstract

One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing problem is roughly $O(\sqrt{N})$. However, many distributions of interest, including those which can be sampled efficiently, have exponential support size, and therefore the optimal identity tester also requires exponential samples. In this paper, we bypass this lower bound by considering restricted settings. The above $O(\sqrt{N})$ sample complexity identity tester is constructed so that it is not fooled by any (even inefficiently-sampled) distributions. However, in most applications, the distributions under consideration are efficiently samplable, and therefore it is enough to consider only identity testers that are not fooled by efficiently-sampled distributions. In this setting we can hope to construct efficient identity testers. We investigate relations between efficient verification of classical/quantum distributions with classical/quantum cryptography, showing the following results: (1). Classically efficiently samplable distributions are verifiable if and only if one-way functions do not exist. (2). Quantumly efficiently samplable distributions are verifiable by $\mathbf{P}^\mathbf{PP}$ with a polynomial number of samples. (3). Sampling-based quantum advantage can be verified quantumly (with a polynomial number of samples) if one-way puzzles do not exist. (4). If QEFID pairs exist, then some quantumly efficiently samplable distributions are not verifiable.