5

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.

glS
  • 27,510
  • 7
  • 37
  • 125
karolyzz
  • 299
  • 1
  • 7

1 Answers1

3

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.

3yakuya
  • 672
  • 3
  • 10