Adiabatic optimization versus diffusion Monte Carlo methods

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

Figure 1

The annealing schedule for example 1 recapitulates example 0 from $s=0$ to $s=1/2$. Afterwards, from $s=1/2$ to $s=1$, the potential on the all-zeros bitstring is lowered by some amount $c$.

Figure 2

The ground state of $H_1\left(s\right)$ lies within the subspace of states that are invariant under all permutations of qubits. Consequently, the ground state can be obtained numerically up to large numbers of qubits, as described in Appendix pp3. With our choices of $b$ and $c$, we numerically find that $p_{s=1}^{\left(1\right)}(0\cdots 0)$ is convergent to a constant (approximately equal to 1/2) in the limit $n\to \infty$.

Figure 3

Runtime comparison of several solvers from MAX-SAT 2016 contest.

Figure 4

Runtime of SSMC in MAX-SAT 2016 contest versus local experiments.