Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

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.

7 pages, 5 figures, updated organization, typos, journal reference added (results unchanged)

References in corpus (5)

• Bounds for the adiabatic approximation with applications to quantum computation
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Adiabatic optimization versus diffusion Monte Carlo
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Discrepancies between Asymptotic and Exact Spectral Gap Analyses of Quantum Adiabatic Barrier Tunneling

Cited by in corpus (6)

• Two-local qubit Hamiltonians: when are they stoquastic?
• Lower Bounds on Quantum Annealing Times
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians