Quantum and classical annealing in a continuous space with multiple local minima

The protocol of quantum annealing is applied to an optimization problem with a one-dimensional continuous degree of freedom, a variant of the problem proposed by Shinomoto and Kabashima. The energy landscape has a number of local minima, and the classical approach of simulated annealing is predicted to have a logarithmically slow convergence to the global minimum. We show by extensive numerical analyses that quantum annealing yields a power-law convergence, thus an exponential improvement over simulated annealing. The power is larger, and thus the convergence is faster, than a prediction by an existing phenomenological theory for this problem. Performance of simulated annealing is shown to be enhanced by introducing quasiglobal searches across energy barriers, leading to a power-law convergence but with a smaller power than in the quantum case and thus a slower convergence classically even with quasiglobal search processes. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum by a meticulous choice of annealing schedule. This latter result explicitly contrasts the role of tunneling in quantum annealing against the classical counterpart of stochastic optimization by simulated annealing.

Figure 1

Graph of the potential $V_{\mathrm{SK}}\left(x\right)$ in the vicinity of the global minimum at $x=0$, with parameters $h_0=w_0=0.2$. These parameters correspond, around the global minimum, approximately to the height of the energy barrier and the distance between neighboring minima. Inset: Zoomed-out view of the potential with the same parameter values, showing the 15 local minima (denoted $N_{\min }$) on each side of the origin. Due to the harmonic term in Eq. (1), the local minima are smoothed out far away from the origin.

Figure 2

Phase diagram showing $N_{\min }$, the number of local minima of $V_{\mathrm{SK}}\left(x\right)$, as a function of the parameters $h_0$ and $w_0$. Individual phases from $N_{\min }=0$ up to 7 are shown. In the region $N_{\min }\ge 8$, the phase boundaries become increasingly closely spaced, with $N_{\min }$ approaching infinity as one approaches the vertical axis $w_0=0$. This paper focuses on the point $h_0=w_0=0.2$ indicated by the circle, which lies within the region $N_{\min }\ge 8$.

Figure 3

Comparing the quantum ground state and classical equilibrium state of $V_{\mathrm{SK}}\left(x\right)$ with the same energies. The vertical axes reflect the actual values of all quantities plotted. (a) Quantum. The ground state probability density (red) with energy eigenvalue $E_0\approx 0.6$ (blue). (b) Classical. The Boltzmann distribution (green) with internal energy $U\approx 0.6$ (blue). The precise energies and their corresponding parameters ($m$ and $\beta$) are summarized in Table 1 (labeled $a$).

Figure 4

Comparing the quantum ground state and classical equilibrium state at lower energies. The panels are organized similarly to Fig. 3. Panels (a) and (b): Comparison at energy $\approx 0.1$. The precise energies and corresponding $m$ and $\beta$ are listed in Table 1, labeled $b$. Panels (c) and (d): At energy $\approx 0.01$, and labeled $c$ in Table 1. Note that the states have been rescaled for presentation purposes.

Figure 5

The quantum ground state and classical equilibrium state energies of $V_{\mathrm{SK}}\left(x\right)$ as a function of their respective parameters. (a) The red curve shows the quantum energy eigenvalue $E_0$ as a function of mass $m$. The lower blue line shows the zero-point energy of a harmonic oscillator with $k=1$, and the upper line shows one with $k=99.696$. (b) The classical internal energy $U$ as a function of inverse temperature $\beta$ (green), and the equipartition theorem for the harmonic oscillator (blue). The region between the two curves (shaded yellow) shows the “excess energy” of the system. In both panels, the vertical lines indicate the boundary (i.e., initial and final) parameter values of the various annealing stages. These parameters are summarized in Table 1. Stages are defined in Secs. 4 and 6.

Figure 6

The quantum energy gap $\mathrm{\Delta }$ as a function of mass $m$. The red curve shows that of $V_{\mathrm{SK}}\left(x\right)$, and the blue lines show those of the oscillators previously discussed in Fig. 5. The three quantum annealing stages are also shown. Stages 1, 2, and 3 are defined in Sec. 4.

Figure 7

Residual energy $R_{\mathrm{QA}}\left(T\right)$ [cf. Eq. (8)] as a function of total annealing time $T$, for the three stages of quantum annealing performed using the linear schedule Eq. (7). The three straight lines (black) are proportional to $T^{-2}$ and show the asymptotic behaviors of the curves. Lines connecting the data points are to guide the eye only.

Figure 8

An example of a wave function that is obtained if annealing is performed too quickly. The red curve shows the final probability density ${\left|\psi (x,T)\right|}^2$ obtained in stage 2 with $T=3250$, whose residual energy is also indicated in Fig. 7. The graph of $V_{\mathrm{SK}}\left(x\right)$ (black) is also shown for comparison. Note the spurious peaks located at the local minima, which are absent in the target ground state [cf. Fig. 4].

Figure 9

Snapshot of the wave function at time $t=44$ during annealing in stage 1 with $T=560$. (a) The probability density ${\left|\psi (x,t)\right|}^2$, with width given by the expectation value of $x^2$. (b) The probability current $j(x,t)$, with amplitude $j(x_0,t)$ at $x_0$. In both panels, the graph of $V_{\mathrm{SK}}\left(x\right)$ has been rescaled vertically for presentation purposes.

Figure 10

Time evolutions of (a) the width $\langle \psi \left(t\right)\left|x^2\right|\psi \left(t\right)\rangle$ and (b) the current amplitude $j(x_0,t)$ of the wave function in stage 1 under the linear schedule. The graphs of $T=320,560$, and 3250 are compared to show the effects of increasing annealing time. In panel (b), the diminishing of $j(x_0,t)$ toward zero with increasing $T$ indicates the approach to adiabaticity.

Figure 11

Comparing the performances of linear and nonlinear schedules in quantum annealing. Panels (a), (b), and (c) show the $R_{\mathrm{QA}}\left(T\right)$ [cf. Eq. (8)] versus $T$ curves in stages 1, 2, and 3, respectively. Legend for the schedules shown in panel (a) also applies to (b) and (c). The straight lines (black) are proportional to $T^{-2n}$ ($n=1$ to 4) and indicate the asymptotic behaviors of the curves. Lines connecting the data points are to guide the eye only.

Figure 12

Comparing the time evolutions of $j(x_0,t)$ under different annealing schedules $m^{\left(n\right)}\left(t\right)$ in stage 1. The oscillatory behavior under the linear schedule $m^{\left(1\right)}\left(t\right)$ (gray) has also been shown in Fig. 10 (green). For nonlinear schedules, the $j(x_0,t)$ are strictly positive, indicating a persistent current directed toward the global minimum throughout the entire annealing.

Figure 13

Tunneling exhibited by the wave function when annealing under a nonlinear schedule. Tics along the vertical axis represent the domain $x>0$ and also indicate the time evolution of $\sqrt{\langle \psi \left(t\right)\left|x^2\right|\psi \left(t\right)\rangle }$ in stage 1 under $m^{\left(3\right)}\left(t\right)$ with $T=560$ (red curve). The (green) shaded areas indicate the classically forbidden regions where $\langle \psi \left(t\right)\left|H\left(t\right)\right|\psi \left(t\right)\rangle <V_{\mathrm{SK}}\left(x\right)$. The shaded areas lying below the red curve are where the wave function exhibits tunneling.

Figure 14

Decrease of residual energy $R_{\mathrm{SA}}\left(T\right)$ [cf. Eq. (17)] with total annealing time $T$ for simulated annealing, performed under the linear schedule Eq. (16) in stage A. Results for three step sizes $s$ are shown. All data points are obtained by averaging over an ensemble of $N={10}^9$, and the error bars indicate finite-$N$ fluctuations (the error bars are generated as follows: the entire ensemble of size ${10}^9$ is divided, arbitrarily, into ten subensembles each of size ${10}^8$; the residual energy of each subensemble is calculated, and the largest and smallest ones obtained are indicated by the upper and lower bounds of the error bar). The solid line (black) is obtained by fitting a straight line to the data points of $s=1$. Thin lines connecting data points are to guide the eye only.

Figure 15

Residual energy $R_{\mathrm{SA}}\left(T\right)$ [cf. Eq. (17)] versus annealing time $T$ curves for simulated annealing under the linear schedule. The three slanting curves (circle, triangle, diamond) show the results for stages A to C, with each curve obtained using the optimum step size of that stage. The solid straight lines (black) are obtained by fitting to the data points of stages B and C. The two curves at the top (magenta squares) exhibit slow decay due to trappings by local minima, which happens when the step size is small ($\frac{s}{2}<w_0$). All data points are obtained by averaging over an ensemble of $N={10}^9$, and the error bars are generated in the same way as in Fig. 14. Thin lines connecting data points are to guide the eye only.

Figure 16

Decay of ${\langle V_{\mathrm{SK}}\left(x\right)\rangle }_t$ with time under the schedule Eq. (18) (${\beta }_i={10}^{0.29}$). Results for several different $s$ are shown. Ensemble size is $N={10}^7$ for all the curves. The errors due to finite-$N$ fluctuations are small and hence not shown. The curves collapse together asymptotically, decaying as ${\left({log}_{10}t\right)}^{-0.74}$ (solid line). Lines connecting the data points are to guide the eye only.

Figure 17

Ground state energy $E_0$ as a function of mass $m$, evaluated at points in $h_0\text{−}{w}_0$ phase space other than (0.2,0.2). The lines labeled “outer oscillator” have the same meaning as in Fig. 5. (a) The $E_0\left(m\right)$ curves where $h_0=9.1$ and $w_0$ varies. (b) The curves where $w_0=0.6$ and $h_0$ varies.

Figure 18

Two notable features on the energy gap curves. Solid curves (red) show the energy gap $\mathrm{\Delta }$ as a function of mass $m$. The lines labeled “outer oscillator” have the same meaning as in Fig. 6. (a) The $\mathrm{\Delta }\left(m\right)$ curve at the phase point $(w_0,h_0)=(3.7,11.1)$ has a minimum turning point when the mass is small. (b) At the phase point (0.5,11.1), the gap of $V_{\mathrm{SK}}\left(x\right)$ shows a steep and significant decrease relative to the gap of the oscillator.

Figure 19

Evolution of the gap curve as $w_0$ changes with $h_0$ held fixed. The curves exhibit salient changes when $w_0$ decreases below 2.5 and these are highlighted in color. To aid visualization, the other curves ($w_0\ge 3$) are plotted in gray. Note that decrease in $w_0$ corresponds to increase in $N_{\min }$ on the phase diagram, and hence increased complexity of $V_{\mathrm{SK}}{\left(x\right)}^{\prime }\mathrm{s}$ energy landscape. (a) For $h_0=0.5$ (small barrier). (b) For $h_0=15$ (large barrier).

Figure 20

Evolution of the gap curve when $w_0=1$ and $h_0$ increases from 0.5 to 15. To aid visualization, only the curves exhibiting prominent changes are plotted in color. Notice that for the gray curves ($8\le w_0\le 14$), their “flat gap” region (cf. Fig. 6) is collapsed onto a single horizontal line.

Figure 21

Snapshot of the probability current $j(x,t)$ at time $t=10$ in stage 2 under the linear schedule with $T=320$. The undulation of $j(x,t)$ between positive and negative values spatially indicates that the current flows in different directions at different points in space. We monitor the time evolution of $j(x,t)$ at $x=-0.025,-0.1$, and $-0.175$ (vertical lines), three $x$ positions located between the global minimum and the first local minimum of $V_{\mathrm{SK}}\left(x\right)$.

Figure 22

Time evolutions of $j(x,t)$ at $x=-0.025,-0.1,$ and $-0.175$ (cf. Fig. 21) in stage 2 under the linear schedule. For total annealing times (a) $T=320$, (b) $T=3250$, and (c) $T=10000$. Generally, the behaviors at all three spatial points exhibit the same trend toward adiabaticity as in stage 1 [cf. Fig. 10].

Figure 23

Comparing the time evolutions of the current amplitude $j(x_0,t)$ in stage 2 under nonlinear schedules. In general, the amplitude exhibits similar behavior to that in stage 1 (cf. Fig. 12), showing no oscillations and staying strictly positive throughout the entire annealing.

Figure 24

Time evolution of the current amplitude $j(x_0,t)$ in stage 3 under the linear schedule.