Diffusion Monte Carlo versus adiabatic computation for local Hamiltonians

Published

February 15, 2018

Author(s)

Stephen P. Jordan, Jacob Bringewatt, Alan Mink, William Dorland

Abstract

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n- body interactions. Here we present a new 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

Citation

Physical Review Letters

Volume

97

Pub Type

Journals

Download Paper

https://doi.org/10.1103/PhysRevA.97.022323

Keywords

quantum algorithms, optimization

Citation

Jordan, S. , Bringewatt, J. , Mink, A. and Dorland, W. (2018), Diffusion Monte Carlo versus adiabatic computation for local Hamiltonians, Physical Review Letters, [online], https://doi.org/10.1103/PhysRevA.97.022323 (Accessed October 8, 2025)