# Quantum Algorithms for Classical Sampling Problems

### APA

Wild, D. (2021). Quantum Algorithms for Classical Sampling Problems . Perimeter Institute. https://pirsa.org/21120007

### MLA

Wild, Dominik. Quantum Algorithms for Classical Sampling Problems . Perimeter Institute, Dec. 01, 2021, https://pirsa.org/21120007

### BibTex

@misc{ pirsa_PIRSA:21120007, doi = {10.48660/21120007}, url = {https://pirsa.org/21120007}, author = {Wild, Dominik}, keywords = {Quantum Information}, language = {en}, title = {Quantum Algorithms for Classical Sampling Problems }, publisher = {Perimeter Institute}, year = {2021}, month = {dec}, note = {PIRSA:21120007 see, \url{https://pirsa.org}} }

Dominik Wild Max Planck Institute of Quantum Optics

## Abstract

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.