Dynamics of reverse annealing for the fully connected $p$-spin model

Reverse annealing is a relatively new variant of quantum annealing in which one starts from a classical state and increases and then decreases the amplitude of the transverse field, in the hope of finding a better classical state than the initial state for a given optimization problem. We numerically study the unitary quantum dynamics of reverse annealing for the mean-field-type $p$-spin model and show that the results are consistent with the predictions of equilibrium statistical mechanics. In particular, we corroborate the equilibrium analysis prediction that reverse annealing provides an exponential speedup over conventional quantum annealing in terms of solving the $p$-spin model. This lends support to the expectation that equilibrium analyses are effective at revealing essential aspects of the dynamics of quantum annealing. We also compare the results of quantum dynamics with the corresponding classical dynamics to reveal their similarities and differences. We distinguish between two reverse annealing protocols we call adiabatic and iterated reverse annealing. We further show that iterated reverse annealing, as has been realized in the D-Wave device, is ineffective in the case of the $p$-spin model but note that a recently introduced protocol (“$h$-gain”), which implements adiabatic reverse annealing, may lead to improved performance.

Figure 1

Static phase diagram for $\mathrm{\Gamma }=1$ and $p=3$. The axis $\lambda =1$ corresponds to conventional QA. ARA starts from $\lambda =s=0$ and ends at $\lambda =s=1$. Lines for $c=0.7,0.8$, and 0.9 represent first-order phase transitions.

Figure 2

System size dependence of the energy gap for conventional QA ($\lambda =1$), shown blue dashed line, and ARA ($\lambda =s$) for several values of $c$. The linear behavior in the $c=0.9$ case is consistent with inverse polynomial scaling, while the curvature seen for $c=0.7$ and 0.8 is consistent with inverse exponential scaling. Here, as in Fig. 1, we set $\mathrm{\Gamma }=1$ and $p=3$.

Figure 3

Phase diagrams in the $s\text{−}\lambda$ plane for $p=3$ for different values of the amplitude of transverse field for (a) $\mathrm{\Gamma }=2$, (b) $\mathrm{\Gamma }=5$, and (c) $\mathrm{\Gamma }=10$. Curves indicate first-order phase transitions.

Figure 4

Error probability as a function of system size for $p=3$ and $\tau =100$. In panel (a) we set $\mathrm{\Gamma }=1$ and in (b) $\mathrm{\Gamma }=2$. Blue dashed lines are for conventional QA. In panel (a), the final error probabilities of ARA are close to those of conventional QA. In panel (b), in contrast, ARA with $c=0.8$ and 0.9 has much smaller errors than QA.

Figure 5

TTS for $N=45$ and $p=3$ as a function of $\tau$ for (a) $\mathrm{\Gamma }=1$ and (b) $\mathrm{\Gamma }=2$. In the case of larger $\mathrm{\Gamma }$, the TTS for ARA is shorter than that for QA. Note the existence of minima in the TTS for $\mathrm{\Gamma }=2$.

Figure 6

Size dependence of TTS of conventional QA (blue dashed line), ARA with $\mathrm{\Gamma }=1,c=0.8$ (green dash-dotted line), and $\mathrm{\Gamma }=2,c=0.8$ (green solid line). As seen in the phase diagrams in Figs. 1 and 3, ARA with $\mathrm{\Gamma }=1,c=0.8$ encounters a first-order transition whereas $\mathrm{\Gamma }=2,c=0.8$ does not. This difference in statics is reflected in the dynamics as the exponential and polynomial dependence of the optimal TTS.

Figure 7

Time evolution of the magnetization under ARA (orange full line) and SVD (blue dashed line) as a function of the normalized annealing time $s$ for (a) $\mathrm{\Gamma }=1$, (b) $\mathrm{\Gamma }=2$, and (c) $\mathrm{\Gamma }=4$ with $N=50,c=0.8$, $p=3$, and $\tau =40$.

Figure 8

Contour plot of the semiclassical potential $V_{\mathrm{SC}}$ as a function of the angles $sin{\theta }_1$ and $sin{\theta }_2$. Panels (a) $s=\lambda =0.2$ and (b) $s=\lambda =0.3$ for $\mathrm{\Gamma }=2$ show that the minimum of the potential evolves continuously as a function of time $s(=\lambda )$ without encountering a phase transition, in agreement with the phase diagram Fig. 3. This leads to a large value of the magnetization at the end of the anneal as in Fig. 9. By contrast, if $\mathrm{\Gamma }$ is larger than a threshold value close to 3 as in panels (c) and (d) where $\mathrm{\Gamma }=3.4$, the minimum at an earlier time $s=\lambda =0.3$ in (c) splits into two (almost) degenerate minima as in (d) $s=\lambda =0.49$, and the system has to transition from a local minimum near the center of the figure to the global minimum at the right-top. This transition is possible by quantum tunneling, since the barrier width and height are not very large at these parameter values, but is impossible for the classical SVD algorithm, resulting in the difference seen in Fig. 9.

Figure 9

Final magnetization as a function of the strength of transverse field $\mathrm{\Gamma }$ for $N=50$, $\tau =40$, $c=0.8$, and $p=3$. The orange solid line represents the case of ARA and blue-dashed is for SVD.

Figure 10

Time evolution of the magnetization under spin-vector Monte Carlo at finite temperature ${\beta }^{-1}$ with $N=50,c=0.8$, $\mathrm{\Gamma }=4$, and 500 sweeps (a sweep is a complete Metropolis update of all the spins at a given $s$) where $\beta =$ (a) 10, (b) 5, and (c) 1. The width of the light-blue hue is the standard deviation calculated from 100 runs. (a) Since $\beta =10$ is too large (temperature too low) for the system to escape the basin of the initial state, the magnetization just wiggles around the initial value. (b) At a higher temperature $\beta =5$, the state can hop over the energy barrier to reach the correct ferromagnetic state in the end. (c) If the temperature is too high $\beta =1$, the state becomes completely random.

Figure 11

Annealing schedule of a single cycle of IRA for $\tau =10$. The schedule in IRA is nonmonotonic as a function of time, starting and ending at $s=1$.

Figure 12

Distribution of magnetization of the final state with various initial conditions (indicated by the values of $c$) with two different minimum values of $s$ [above (a) $s_{min}=0.5$ and below (b) $s_{min}=0.3$ the critical $s$ value], and $N=50$ and $\tau =10$.

Figure 13

Energy spectrum of IRA during a single cycle and occupation probability (represented by the red thickness) for $N=10$, $p=3$, $\tau =10$, and $s_{min}=0.3$. The black dashed lines represent the energy spectrum. In (a) the system starts in the ground state ($c=1$) and in (b) it starts in an excited state ($c=0.8$).

Figure 14

Transition probabilities ${\left(P^r\right)}_{ji}$ from state $i$ (horizontal axis) to state $j$ (vertical axis) with $i=0$ the ground state, $i=1$ the first excited state, etc., for $p=3,N=10,s_{min}=0.5$, where (a) $\tau =30,r=1$; (b) $\tau =30,r=5$; (c) $\tau =8,r=1$; and (d) $\tau =8,r=3$. Panels (b) and (d) are for the results after $r$ repetitions. In this case of $s_{min}=0.5$, the phase transition is not crossed so the probability of staying in the ground state is high, as seen in the left-top element in each panel. The general tendency is clearly that transitions to the ground state, shown in the top row, are small except for the top-left corner, which represents the probability to stay in the initially given ground state. Panel (a) has a rather large $\tau$ and the system stays close to adiabatic, which is reflected in the high probabilities along the diagonal. In panel (c), with a smaller $\tau$, some diabatic transitions take place as seen by the increased brightness of the off-diagonal elements. Since $s_{min}=0.5>s_c$, the energy gap ${\mathrm{\Delta }}_{01}$ between the ground state and the first excited state remains relatively large, but transitions do occur between excited states because the energy gaps between higher energy states are smaller than ${\mathrm{\Delta }}_{01}$.

Figure 15

Transition probabilities ${\left(P^r\right)}_{ji}$ from state $i$ to state $j$ for $p=3,N=10,s_{min}=0.3$, after $r$ repetitions, where (a) $\tau =30,r=1$; (b) $\tau =30,r=5$; (c) $\tau =10,r=1$; and (d) $\tau =10,r=5$. Since $s_{min}=0.3<s_c$, a phase transition occurs, accompanied by a relatively small energy gap between the ground state and the first excited state, which causes a diabatic transition to the first excited state, after which the state returns to the ground state at the second avoided crossing, which is represented as bright yellow in the top-left corner of panel (a). When started from an excited state $i>0$, the system does not reach the ground state. The reason is that the existence of many avoided crossings causes both upward and downward transitions and does not unilaterally favor downward transitions toward the ground state.