  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.
