AQC 2016 - Simulated Quantum Annealing Can Be Exponentially Faster Than Classical

A Google TechTalk, June 27, 2016, presented by Elizabeth Crosson (Caltech) ABSTRACT: Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing: Cost functions with thin, high energy barriers can exhibit exponential separations between the run-time of classical simulated annealing, for which thermal fluctuations take exponential time to climb these barriers, and quantum annealing which can in some cases pass through such barriers efficiently, arguably by taking advantage of quantum tunneling. In this talk we will describe a proof which demonstrates that the Markov chain underlying SQA can efficiently sample its target distribution and find the global minimum of such a spike cost function in polynomial time. This result provides evidence for the growing consensus that SQA inherits at least some of the advantages that arise from tunneling in QA, and we will emphasize techniques in the proof which contribute to a further understanding of both the equilibrium distribution and the nonequilibrium dynamics of SQA. Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.