Quantum Algorithms for Classical Sampling Problems

Sampling from classical probability distributions is an important task with applications in a wide range of fields, including computational science, statistical physics, and machine learning. In this seminar, I will present a general strategy of solving sampling problems on a quantum computer. The entire probability distribution is encoded in a quantum state such that a measurement of the state yields an unbiased sample. I will discuss the complexity of preparing such states in the context of several toy models, where a polynomial quantum speedup is achieved. The speedup can be understood in terms of the properties of classical and quantum phase transitions, which establishes a connection between computational complexity and phases of matter. To conclude, I will comment on the prospects of applying this approach to challenging, real-world tasks.