4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – forky40
    Dec 29 '21 at 17:11
3
$\begingroup$

The problem that led to an important role of IQP circuits is Boson Sampling. Boson sampling algorithm has to sample from a distribution based on the permanent of some complex matrix. Computing complex matrices permanents is #P-hard, meaning it is at least NP-Complete (or harder, not proven yet.) The same problem is efficiently solvable by a sub-universal IQP model.

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.

Wikipedia page on Boson Sampling gives a pretty good overview. You may also find this NPJ article on quantum sampling problems and this Medium article on preparation of arbitrary distributions using a quantum computer.

$\endgroup$
3
  • 2
    $\begingroup$ "If you have a probability distribution generated by a hard to simulate circuit ... then to sample it you'd need to... simulate the hard to simulate circuit." Could you maybe provide more justification for this claim? For instance, there might be circuits that are hard to simulate classically but whose output distribution can be approximated with a hard calculation that doesn't involve circuit simulation whatsoever. Factoring comes to mind. $\endgroup$
    – forky40
    Dec 29 '21 at 16:48
  • 1
    $\begingroup$ You are right, perhaps my statement sounds much broader than intended. I had in mind certain probability distributions generated by certain quantum circuits that are hard to simulate classically, like Boson Sampling. I will improve my answer, thank you for your comment! $\endgroup$
    – 3yakuya
    Dec 29 '21 at 22:49
  • 2
    $\begingroup$ I think this is somewhat misleading. For the boson sampling example, computing the permanents is hard, yes, but that doesn't imply that the problem of sampling from the corresponding probability distribution is also hard. That turns out to be the case (under a few assumptions), but it doesn't immediately follow. The situation for IQP circuits is similar, afaik $\endgroup$
    – glS
    Dec 30 '21 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.