# Why is sampling from probability distributions generated by specific quantum circuits classically intractable?

I was reading a paper by Benedetti et al. titled Parameterized quantum circuits as machine learning models. Its authors state the following:

We also know that sampling from the probability distribution generated by instantaneous quantum polynomial-time circuits is classically intractable in the average case. A natural application for them is in generative modeling where the task itself requires sampling from complex probability distributions

Could someone explain why "sampling from the probability distribution" would be intractable? Does it mean that if we tried to classically simulate the p.d. of the quantum state prepared by these specific quantum circuits, that would be intractable?

For reference, the authors also state the following in their other work on A generative modeling approach for benchmarking and training shallow quantum circuits:

For example, learning probabilistic generative models is in many cases an intractable task <...>

Although this seems to be stating the same/similar thing, I cannot fully understand this statement either.

• This paper gives a nice review of hardness results for sampling from different families of quantum circuits (you might want to search the term "IQP" to answer your first question). arxiv.org/abs/1809.07442 Dec 29 '21 at 17:11

If the cost of such simulation is $$\theta(2^n)$$ where $$n$$ is the number of qubits, then the problem is exponentially difficult for a classical computer, while being polynomially difficult for a quantum machine.