AQC 2016 - Adiabatic Quantum Computer vs. Diffusion Monte Carlo

A Google TechTalk, June 29, 2016, presented by Stephen Jordan (NIST) ABSTRACT: While adiabatic quantum computation using general Hamiltonians has been proven to be universal for quantum computation, the vast majority of research so far, both experimental and theoretical, focuses on stoquastic Hamiltonians. Conventional wisdom amongst Monte Carlo practitioners states that Monte Carlo simulations of stoquastic adiabatic computation will not suffer from the sign problem and will therefore converge efficiently. If this could be turned into a theorem it would prove that stoquastic adiabatic computers are incapable of exponential speedup over classical computation. The two major classes of Monte Carlo simulation algorithms are path integral Monte Carlo and diffusion Monte Carlo. In 2013, Hastings constructed a class of counterexamples in which path integral Monte Carlo will fail to efficiently simulate stoquastic adiabatic dynamics due to topological obstructions. Diffusion Monte Carlo algorithms should not be affected by topological obstructions. We are nevertheless able to construct a counterexample in which a non-topological obstruction prevents diffusion Monte Carlo from efficiently simulating a stoquastic adiabatic process. On typical instances such simulations may nevertheless work well. In fact, we introduce a new variant of diffusion Monte Carlo, which we call Substochastic Monte Carlo, tailored to simulating stoquastic adiabatic processes. In practice, we find that this performs so well that our Monte Carlo simulations of adiabatic optimization are good classical optimization heuristics in their own right, competitive with the best previous known heuristic solvers for Max-kSAT at k=2,3,4. Michael Jarret, Joint Center for Quantum Information and Computer Science, University of Maryland, Brad Lackey, Joint Center for Quantum Information and Computer Science, University of Maryland Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.