Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. 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 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.
Population annealing Monte Carlo is an efficient sequential algorithm for simulating
k-local Boolean Hamiltonians. Because of its structure, the algorithm is inherently parallel and therefore well suited for large-scale simulations of computationally hard problems. Here we present various ways of optimizing population annealing Monte Carlo using 2-local spin-glass Hamiltonians as a case study. We demonstrate how the algorithm can be optimized from an implementation, algorithmic accelerator, as well as scalable parallelization points of view. This makes population annealing Monte Carlo perfectly suited to study other frustrated problems such as pyrochlore lattices, constraint-satisfaction problems, as well as higher-order Hamiltonians commonly found in, e.g., topological color codes.
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 Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-
k-SAT at
k=2,3,4.