A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and
Shepherd, shows that quantum computers can efficiently sample from probability
distributions that cannot be exactly sampled efficiently on a classical
computer, unless the PH collapses. Aaronson and Arkhipov take this further by
considering a distribution that can be sampled efficiently by linear optical
quantum computation, that under two feasible conjectures, cannot even be
approximately sampled classically within bounded total variation distance,
unless the PH collapses.
In this work we use Quantum Fourier Sampling to construct a class of
distributions that can be sampled by a quantum computer. We then argue that
these distributions cannot be approximately sampled classically, unless the PH
collapses, under variants of the Aaronson and Arkhipov conjectures.
In particular, we show a general class of quantumly sampleable distributions
each of which is based on an "Efficiently Specifiable" polynomial, for which a
classical approximate sampler implies an average-case approximation. This class
of polynomials contains the Permanent but also includes, for example, the
Hamiltonian Cycle polynomial, and many other familiar #P-hard polynomials.
Although our construction, unlike that proposed by Aaronson and Arkhipov,
likely requires a universal quantum computer, we are able to use this
additional power to weaken the conjectures needed to prove approximate sampling
hardness results.
