Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.


Recording Details

Scientific Areas: 
PIRSA Number: 


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.