Simulated quantum annealing of double-well and multiwell potentials

We analyze the performance of quantum annealing as a heuristic optimization method to find the absolute minimum of various continuous models, including landscapes with only two wells and also models with many competing minima and with disorder. The simulations performed using a projective quantum Monte Carlo (QMC) algorithm are compared with those based on the finite-temperature path-integral QMC technique and with classical annealing. We show that the projective QMC algorithm is more efficient than the finite-temperature QMC technique, and that both are inferior to classical annealing if this is performed with appropriate long-range moves. However, as the difficulty of the optimization problem increases, classical annealing loses efficiency, while the projective QMC algorithm keeps stable performance and is finally the most effective optimization tool. We discuss the implications of our results for the outstanding problem of testing the efficiency of adiabatic quantum computers using stochastic simulations performed on classical computers.

Figure 1

Simulated quantum annealing (SQA) of symmetric and asymmetric double-well potentials. Top panel: potential energy $V\left(x\right)$ versus particle coordinate $x$. Central panel: residual energy ${\epsilon }_{\mathrm{res}}$ versus annealing time ${\tau }_f$ for the symmetric double well, obtained using the diffusion Monte Carlo (DMC) algorithm, the DMC algorithm with importance sampling (IS-DMC), the path-integral Monte Carlo algorithm with instanton move (PIMC+ins., from Ref. [29]), and via integration of the real-time Schrödinger equation (RT, from Ref. [36]). Bottom panel: as in the central panel (except for the RT data), for the asymmetric double-well. The horizontal brown dot-dashed lines indicate the lowest ${\epsilon }_{\mathrm{res}}$ reachable in the PIMC simulation due to the finite temperature. The thick black solid segments indicate fits to the DMC asymptotic data according to the power-law scaling ${\epsilon }_{\mathrm{res}}\sim {\tau }_f^{-1/3}$. The units of ${\tau }_f$ in PIMC and DMC simulations are different (see text). The thin dashed curves are guides to the eye. Here and in the other graphs the error bars are smaller than the symbol size.

Figure 2

Classical annealing (CA) and SQA of the asymmetric double-well potential. Residual energy ${\epsilon }_{\mathrm{res}}$ as a function of annealing time ${\tau }_f$ obtained using the metropolis algorithm with Lorentzian proposed moves (cyan triangles) and box-type moves (violet squares), and using the DMC algorithm (red circles). The thick black solid segments is a fit to the DMC asymptotic data with the power-law ${\epsilon }_{\mathrm{res}}\sim {\tau }_f^{-1/3}$. The dotted black curve is a fit to the CA box-moves data with the asymptotic law ${\epsilon }_{\mathrm{res}}^{\mathrm{HF}}\left({\tau }_f\right)$ (see text). The units of ${\tau }_f$ in CA and DMC simulations are different (see text).

Figure 3

CA and SQA of the washboard potential (shown in the inset). The symbols are defined as described in the caption of Fig. 2. The thick black solid segment is a fit to the DMC asymptotic data with the power-law ${\epsilon }_{\mathrm{res}}\sim {\tau }_f^{-1/3}$. The dotted black curve is a fit to the CA data with the logarithmic law ${\epsilon }_{\mathrm{res}}=c_1{log}^{-1}\left(c_2{\tau }_f\right)$, where the fitting parameters are $c_1$ and $c_2$.

Figure 4

CA and SQA of the quasidisordered potential (shown in the inset). The symbols and the curves are defined as described in the caption of Fig. 2.

Figure 5

Potential energy $V(x_1,x_2)$ of the two particle model (13) in the case $A=5$. The color scale represents the potential intensity; $x_1$ and $x_2$ are the coordinates of the two particles. The absolute minimum is at $V(-0.25,-0.208)\cong -9.99759$.

Figure 6

CA and SQA of the two particle model. Top panel: residual energy ${\epsilon }_{\mathrm{res}}$ versus annealing time ${\tau }_f$ obtained using CA with Lorentzian updates, for different intensities $A$ of the sinusoidal part of the potential. Central panel: data analogous to those in the top panel, obtained using the DMC algorithm. Bottom panel: comparison between CA and SQA at $A=5$. The thick black solid segment indicates the asymptotic scaling of the DMC data ${\epsilon }_{\mathrm{res}}\sim {\tau }_f^{-1/3}$, while the black dotted curve the one of the CA data ${\epsilon }_{\mathrm{res}}\sim {log}^{-1}\left(c{\tau }_f\right)$.

Figure 7

Final random-walker distribution in CA [panels (a) and (c)] and in SQA [panels (b) and (d)]. Panels (a) and (c) correspond to short annealing times ${\tau }_f={10}^3$, while panels (b) and (d) correspond to long annealing times ${\tau }_f={10}^5$. The color scale corresponds to the random-walker density.