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.

Adiabatic Optimization versus Diffusion Monte Carlo

Published

Author(s)

Stephen P. Jordan, Michael Jarret, Brad Lackey

Abstract

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Sub-Stochastic Monte Carlo. In fact, our simulations are good classical optimization heuristics in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k = 2,3,4.
Citation
Physical Review A
Volume
94

Keywords

quantum computing, optimization, adiabatic, Monte Carlo

Citation

Jordan, S. , Jarret, M. and Lackey, B. (2016), Adiabatic Optimization versus Diffusion Monte Carlo, Physical Review A (Accessed April 23, 2024)
Created October 13, 2016, Updated February 19, 2017