##
**Video URL**
http://pirsa.org/21120007

## 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.

## Details

**Talk Number**21120007

**Speaker Profile**Dominik Wild

**Collection**Perimeter Institute Quantum Discussions

- Quantum Information

**Scientific Area**

- Scientific Series

**Talk Type**

**Subject**Quantum Physics

**Source Repository**PIRSA