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.