01455nas a2200157 4500008004100000245005600041210005600097260001500153300001100168490000700179520101300186100002001199700002401219700001701243856003701260 2016 eng d00aAdiabatic optimization versus diffusion Monte Carlo0 aAdiabatic optimization versus diffusion Monte Carlo c2016/07/12 a0423180 v943 a
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.
1 aJarret, Michael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1607.03389