Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. 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. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

Figure 1

Plot of the potential as in the 1D quantum Hamiltonian (with the entropic force canceled by $V_{\mathrm{fict}}$) at various $s$ for $n=100, \omega =260\sqrt{n}, \delta =0.1{(100/n)}^{1/4}$, and $\tau =1000/n^{5/4}$. At $s=\frac{1}{2}$ both the exact numerical ground state and the tight-binding approximate ground state are shown in the middle panel.

Figure 2

A log-log (base 10) scale plot of the cost of quantum adiabatic computation versus the number of qubits with the choice of parameters $\omega =260\sqrt{n}, \delta =0.1{(100/n)}^{1/4}$, and $\tau =1000/n^{5/4}$. Since the ground state of the Hamiltonian lies in the permutation symmetric subspace it can be obtained numerically to a large number of qubits. Like predicted by tight binding, the cost scales like $O\left(n^3\right)$ for large $n$.

Figure 3

Plot of $V(w,s)$ as seen by SSMC for $n=100$ with the choice of parameters $\omega =260\sqrt{n}, \delta =0.1{(100/n)}^{1/4}$, and $\tau =1000/n^{5/4}$. Also shown is the walker distribution for 1000 walkers and 4000 time steps and the predicted distribution $D\left(w\right)$, which is proportional to the quantum ground state in the permutation symmetric subspace. For $s<0.5$ diffusion biased towards $w=n/2$ and teleportation to higher Hamming weight balance to track $D\left(w\right)$. For $s>0.5$ SSMC can still track $D\left(w\right)$ as depicted, but it requires exponential resources.

Figure 4

Semilogarithmic (base 10) scale plot of the cost of SSMC versus the number of qubits with the same choice of parameters as in Fig. 2. As predicted, this scales superpolynomially with the number of qubits, converging towards the expected $exp\left[O\left(\sqrt{n}\right)\right]$ scaling as $n$ increases.

Figure 5

Cost of adiabatic optimization compared to the cost of SSMC for the “spike” potential from [7, 11, 12, 13, 14]. The cost of SSMC is estimated as $(\mathrm{No}.\mathrm{ofwalkers})\times (\mathrm{No}.\mathrm{oftimesteps})/\left(\mathrm{probabilityofsuccess}\right)$. At the bit numbers we were able to test ($n\le 1280$), one observes a large discrepancy in scaling between SSMC and adiabatic optimization. Best-fit power-law scalings are shown, illustrating a roughly quintic speedup of adiabatic computing over SSMC. However, both the analysis of [15] and the systematic-looking behavior of the residuals from the fit to the SSMC cost suggest that asymptotic behavior for $n\to \infty$ may differ from the trends seen here. All SSMC trials shown here used 8000 walkers.