What are known applications of quantum sampling?

Question

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.

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.