Direct comparison of quantum and simulated annealing on a fully connected Ising ferromagnet

We compare the performance of quantum annealing (QA, through Schrödinger dynamics) and simulated annealing (SA, through a classical master equation) on the $p$-spin infinite range ferromagnetic Ising model, by slowly driving the system across its equilibrium, quantum or classical, phase transition. When the phase transition is second order ($p=2$, the familiar two-spin Ising interaction) SA shows a remarkable exponential speed-up over QA. For a first-order phase transition ($p\ge 3$, i.e., with multispin Ising interactions), in contrast, the classical annealing dynamics appears to remain stuck in the disordered phase, while we have clear evidence that QA shows a residual energy which decreases towards zero when the total annealing time $\tau$ increases, albeit in a rather slow (logarithmic) fashion. This is one of the rare examples where a limited quantum speedup, a speedup by QA over SA, has been shown to exist by direct solutions of the Schrödinger and master equations in combination with a nonequilibrium Landau-Zener analysis. We also analyze the imaginary-time QA dynamics of the model, finding a $1/{\tau }^2$ behavior for all finite values of $p$, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit $p\left(\mathrm{odd}\right)=\infty$ is also discussed.

Figure 1

(a) Log-log plot of the residual energy density vs annealing time for QA-RT for $p=2$. The QA-RT raw data show the four different regimes discussed in the text. Here ${\mathrm{\Gamma }}_{\mathrm{i}}=2$. (b) The envelope construction illustrated: notice the large coherent oscillations of the finite-size LZ data, discussed in the text. The green thick line represents the geometrical envelope of our QA-RT finite-$N$ curves, obtained from LZ fit (black solid lines). (c) The spectrum for $N=64$. (d) The minimum gap ${\mathrm{\Delta }}_N$ (lines) and the more relevant dynamical gap (lines with symbols) vs the transverse field $\mathrm{\Gamma }$. The inset shows the scaling with $N$ of the minimum gap ${\mathrm{\Delta }}_N$ at the critical point.

Figure 2

(a) ${\epsilon }_N^{\mathrm{res}}\left(\tau \right)$ vs annealing time $\tau$ for SA at $p=2$, with vanishing final temperature $T_{\mathrm{f}}=0$. The data show almost no size dependence and follow asymptotically an exponential relaxation. (b) ${\epsilon }_N^{\mathrm{res}}\left(\tau \right)$ for $N=32$ in log-log scale, for different values of the final temperature $T_{\mathrm{f}}$. In (a) and (b) the initial temperature is $T_{\mathrm{i}}=2$. For $T_{\mathrm{f}}>0$ the asymptotic adiabatic regime ${\tau }^{-1}$ suggested by Eq. (19) is visible. (c) The instantaneous spectrum of the classical master equation for $N=128$. (d) The minimum gap relevant for the classical master equation dynamics (lines with symbols) and for equilibrium properties (lines).

Figure 3

(a) Log-log plot of the residual energy density vs annealing time for QA-RT for $p=3$. For first-order phase transition the characteristic annealing times ${\tau }_N^{*}$ increase exponentially with $N$; hence only for moderate $N$ the LZ regime is clearly visible. Here the initial transverse field is set to ${\mathrm{\Gamma }}_{\mathrm{i}}=2$. (b) Detail of the exponential fit on the regions in which the LZ approximation holds, used for the envelope construction. The envelope $1/log\left(\gamma \tau \right)$ (thick solid line) gives an estimate of the large-$\tau$ behavior of the residual energy in the thermodynamic limit $N\to \infty$. (c) The instantaneous spectrum vs the transverse field $\mathrm{\Gamma }$, close to the transition, for $N=64$. One can clearly see the series of avoided level crossings encountered by the paramagnetic phase coming from the right. (d) The minimum gap close to the critical point.

Figure 4

(a) ${\epsilon }_N^{\mathrm{res}}\left(\tau \right)$ for SA with $T_{\mathrm{i}}=2, T_{\mathrm{f}}=0$ when $p=3$. Differently from the case $p=2$, the relaxation rate $1/{\tau }_N^{*}$ depends on $N$ and vanishes with a power law in the thermodynamic limit. (b) Scaling of ${\tau }_N^{*}$ with $N$ for vanishing final temperature $T_{\mathrm{f}}$, compared with the power laws obtained analytically. (c) The classical equilibrium free-energy density $f(m,T)$ for the $p=3$ fully connected $p$-spin model vs the magnetization $m=\left({\sum }_j{\sigma }_j\right)/N$ for different temperatures. (d) The instantaneous spectrum of the classical master equation for $p=3$ and $N=128$. Notice the two quasidegenerate eigenvalues (exponentially close for $T>0$ and separated by a power-law gap for $T=0$), which effectively freeze the imaginary-time filtering capability of the master equation. In the thermodynamic limit the system remains “stuck” in the paramagnetic minimum around $m=0$.

Figure 5

(a) Residual energy density ${\epsilon }_N^{\mathrm{res}}\left(\tau \right)$ vs annealing time for QA-RT for $p=2$, compared to the results obtained through an imaginary-time Schrödinger dynamics (QA-IT). Here ${\mathrm{\Gamma }}_{\mathrm{i}}=2$. (b) Same as in (a), but for $p=3$.

Figure 6

Envelope construction illustrated for the transverse-field Ising chain.