Vadim Smelyanskiy, Google

Title: Quantum Tunneling as a Computational Resource   (Video) 

Abstract:  In this talk we address a  question: whether quantum tunneling can be used as a computational resource in open-system   quantum annealing (QA) approach to classical optimization. We show that Quantum Monte Carlo (QMC) simulations can efficiently predict the performance of the quantum annealing algorithm for tunneling through a barrier. We develop an instantonic calculus to study the thermally assisted tunneling decay of a metastable state in a fully connected quantum spin model. The tunneling problem can be mapped onto the Kramers escape problem of a classical random dynamical field. QMC simulates this classical problem efficiently.  We show analytically that the exponential scaling with the number of spins of the  tunneling decay rate and the escape rate of the QMC process are identical. We relate this effect to the existence of a dominant instantonic tunneling path. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC compared to QA. We also provide theoretical and experimental evidence that pefactor plays an important role in achieving a substantial computational advantage of quantum tunneling compared to QMC.