AQC 2016 - Quantum Monte Carlo vs Tunneling vs. Adiabatic Optimization

A Google TechTalk, June 27, 2016, presented by Aram Harrow (MIT) ABSTRACT: Can quantum adiabatic evolution solve optimization problems much faster than classical computers? One piece of evidence for this has been their apparent advantage in "tunneling" through barriers to escape local minima. However, I will argue that quantum Monte Carlo is at most polynomially slower than stochastic quantum adiabatic optimization under a wide variety of settings. I will then discuss some prospects for demonstrating quantum supremacy with a near-term quantum computer. I will explain the difficulties in achieving this using adiabatic evolution and will explain the possibility of achieving this with low-depth quantum circuits. Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.