I'm inspired by [1] which clearly lays out near term applications of quantum computing: optimization, simulation and sampling. They claim that quantum sampling is likely to be the first application that achieves quantum supremacy "Our calculations show that, for relatively small circuits involving high-fidelity quantum gates, it will be possible to sample from probability distributions that are inaccessible classically, using a circuit of just 7 × 7 qubits in layers that are around 25 deep"

However, the authors only loosely describe potential applications of quantum sampling, viz. "inference and pattern recognition in machine learning". Can anyone describe the utility of quantum sampling in further depth?

[1] Mohseni, M., Read, P., Neven, H., Boixo, S., Denchev, V., Babbush, R., ... & Martinis, J. (2017). Commercialize quantum technologies in five years. Nature, 543(7644), 171-174.

  • $\begingroup$ Welcome to QCSE. Aaronson has a proposal, for sampling of the kind mentioned in your linked paper. E.g. he proposes to use random sampling from a quantum circuit as a source for "complexity-certified" randomness. This may be useful, for example, in some cryptocurrencies. Google lectures on "Quantum Supremacy and its Applications". $\endgroup$ Commented Aug 8, 2020 at 1:51
  • $\begingroup$ one that comes to mind is (Huh et al. 2015), in the context of boson sampling $\endgroup$
    – glS
    Commented Aug 10, 2020 at 6:18

1 Answer 1


The two main classes of sampling problems demonstrating quantum supremacy are BosonSampling and IQP which are intermediate models of optical and qubit based quantum information processing architectures. Even reasonable approximations to the outputs from these problems, given some highly plausible conjectures, are hard for classical computers to compute. Recently the complexity of IQP sampling has been connected to the complexity of quantum algorithms for approximate optimization problems, suggesting further applications of IQP and closely related classes.

Applications of BosonSampling to molecular simulations, meteorology, and decision problems have been suggested, though more work is needed in this space.

For more information see this article.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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