Adiabatic optimization versus diffusion Monte Carlo methods

作者：Jarret Michael^*; Jordan Stephen P; Lackey Brad

来源：Physical Review A, 2016, 94(4): 042318.

DOI：10.1103/PhysRevA.94.042318

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 L-1 and L-2 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.

• 出版日期2016-10-13