Reverse annealing for the fully connected $p$-spin model

Reverse annealing is a variant of quantum annealing that starts from a given classical configuration of spins (qubits). In contrast to the conventional formulation, where one starts from a uniform superposition of all possible states (classical configurations), quantum fluctuations are first increased and only then decreased. One then reads out the state as a proposed solution to the given combinatorial optimization problem. We formulate a mean-field theory of reverse annealing using the fully connected ferromagnetic $p$-spin model, with and without random longitudinal fields, and analyze it in order to understand how and when reverse annealing is effective at solving this problem. We find that the difficulty arising from the existence of a first-order quantum phase transition, which leads to an exponentially long computation time in conventional quantum annealing, is circumvented in the context of this particular problem by reverse annealing if the proximity of the initial state to the (known) solution exceeds a threshold. Even when a first-order transition is unavoidable, the difficulty is mitigated due to a smaller jump in the order parameter at a first-order transition, which implies a larger rate of quantum tunneling. Reverse annealing has not been studied analytically before, and this study paves the way toward a systematic understanding of this relatively unexplored protocol in a broader context.

Figure 1

Phase diagrams on the $\lambda \text{−}s$ plane for $p=3$ and three values of $c$. The curves represent lines of first-order transitions.

Figure 2

Phase diagram for $p=3$, 5, and 7. The parameter $c$ is fixed to 0.95.

Figure 3

Jump in magnetization along the first-order transition line for $p=3$ and 5 and several values of $c$.

Figure 4

Phase diagram for $p=2$. Most of the curves represent the lines of first-order transitions, and the dotted part of $c=0.5$ is for second-order transition.

Figure 5

Phase diagrams on the $s\text{−}\lambda$ plane for $p=3$ and 5 under bimodal random field. Lines represent first-order phase transitions. In both panels, $c$ increases monotonically from the uppermost curve to the bottom curve. The parameter $h_0$ for the amplitude of the random field is 0.5. Each line is for first-order transitions.

Figure 6

Jump in magnetization at first-order transitions for $p=3$ and 5. The parameter $h_0$ is 0.5.

Figure 7

Phase diagrams on the $s\text{−}\lambda$ plane for (a),(b) $p=3$ and (c),(d) $p=5$ under the Gaussian-distributed random field. The standard deviation $\sigma$ is 0.5 and 1. In all panels, $c$ increases monotonically from the uppermost curve to the bottom curve.

Figure 8

Jump in magnetization along the first-order transition line for $p=3$ under Gaussian random field. In both panels, $c$ increases monotonically from the uppermost curve to the bottom curve.

Figure 9

Phase diagram in the $s\text{−}\nu$ plane for $p=3$ (left) and $p=5$ (right) for conventional quantum annealing $\lambda =1$ with a nonstoquastic Hamiltonian. The red curve is a line of first-order transitions between the paramagnetic and ferromagnetic phases. The blue dotted curve is for second-order transitions.

Figure 10

Phase diagrams in the $s\text{−}\lambda$ plane for (a)–(c) $p=3$ and (d)–(f) $p=5$ for the nonstoquastic Hamiltonian. The parameter $\nu$ is set to $0.1,0.5$, and 0.9 (the smaller it is, the larger the amplitude of the nonstoquastic term). In (a), a first-order transition exists on the line $\lambda =1$, which disappears as soon as $\lambda$ becomes smaller than 1 and then reappears for smaller $\lambda$. In (d), in contrast, the transition on the line $\lambda =1$ is of second order, as seen in Fig. 9 (right), which is replaced by a line of first-order transitions for $\lambda$ below a threshold value. In all panels, $c$ increases monotonically from the uppermost curve to the bottom curve.

Figure 11

Phase diagrams in the $s\text{−}\lambda$ plane for the case of bimodal random field for (a)–(c) $p=3$ and (d)–(f) $p=5$. The parameter $\nu$ is $0.1,0.5$, and 0.9, and $h_0=0.5$ everywhere. In all panels, $c$ increases monotonically from the uppermost curve to the bottom curve.

Figure 12

Free energy of Eq. (12) as a function of $s$ for each magnetization value $m$. The parameter $\lambda$ is fixed to 0, and $p=3$ and $c=0.8$. For these parameters, there is no region where the solution $m=c-1$ appears, and the corresponding curve does not appear in the figure. The magnetization having the smallest free energy is selected in the ground state.