Patrick Rall, UT-Austin

"Quantum Computers and Monte Carlo Estimation"

Abstract: Quantum computers have a fascinating relationship with randomness. Although quantum physics defies description with classical probability, quantum computers can be used to speed up the performance of Monte Carlo algorithms. In this defense I will present several quantum algorithms that illustrate this fact: First, I give a simplified quantum method for estimating probabilities that can be applied to any Monte Carlo estimation task. Second, I apply this technique to estimate several quantities in physics like correlation functions and the density of states. Finally, I give an improved method for measuring in the eigenbasis of an observable and extracting an estimate of the eigenvalue.