Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Diffusion Monte Carlo versus adiabatic computation for local Hamiltonians

Published

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

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 9, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created February 15, 2018, Updated August 1, 2019