Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

Understand

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes.

• 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.