Abstract
We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can sample distributions that subexponential-size classical circuits cannot approximate even to TV distance 1-o(1). Prior work of Aaronson and Arkhipov (2011) showed such a separation for the case of exact sampling (i.e. TV distance 0), but separations for approximate sampling were only known for uniform algorithms. A key ingredient in our proof is a new hardness amplification lemma for the classical query complexity of the Yamakawa-Zhandry (2022) search problem. We show that the probability that any family of query algorithms collectively finds k distinct solutions decays exponentially in k.