Abstract

The study of quantum computation is motivated by our belief in the existence of quantum advantage: that there are computational tasks that are easy for quantum computers but hard for classical ones. Sampling-based quantum advantage (the existence of quantum samplable but classically un-samplable distributions) is one of the most well-studied frameworks for quantum advantage, with specific instantiations such as Boson sampling and random-circuits having received significant study. One often-claimed disadvantage of sampling-based quantum advantage compared with more sophisticated frameworks, such as proofs of quantumness, is the lack of efficient (or even inefficient) verification. This disadvantage of sampling-based quantum advantage has been justified by appealing to the intuition that verifying distributions is impossible (even inefficiently). However this impossibility only holds when the adversarial distribution is some arbitrary (potentially un-samplable) distribution and it is reasonable to assume that adversarial distributions must also be samplable. We provide formal definitions for this version of verification of distributions and the verification of quantum advantage distributions. Using these definitions we prove the following results: Classically samplable distributions are PPT verifiable if and only if (io)-OWFs do not exist. Quantum samplable distributions are verifiable by QPT ^PP. If (io)-OWPuzz do not exist then quantum advantage distributions are QPT verifiable.