Open-System Quantum Annealing in Mean-Field Models with Exponential Degeneracy^*

Real-life quantum computers are inevitably affected by intrinsic noise resulting in dissipative nonunitary dynamics realized by these devices. We consider an open-system quantum annealing algorithm optimized for such a realistic analog quantum device which takes advantage of noise-induced thermalization and relies on incoherent quantum tunneling at finite temperature. We theoretically analyze the performance of this algorithm considering a $p$-spin model that allows for a mean-field quasiclassical solution and, at the same time, demonstrates the first-order phase transition and exponential degeneracy of states, typical characteristics of spin glasses. We demonstrate that finite-temperature effects introduced by the noise are particularly important for the dynamics in the presence of the exponential degeneracy of metastable states. We determine the optimal regime of the open-system quantum annealing algorithm for this model and find that it can outperform simulated annealing in a range of parameters. Large-scale multiqubit quantum tunneling is instrumental for the quantum speedup in this model, which is possible because of the unusual nonmonotonous temperature dependence of the quantum-tunneling action in this model, where the most efficient transition rate corresponds to zero temperature. This model calculation is the first analytically tractable example where open-system quantum annealing algorithm outperforms simulated annealing, which can, in principle, be realized using an analog quantum computer.

Popular Summary

Implementing universal quantum computation remains years away given the requirement of resource-intensive error correction to mitigate the effect of intrinsic hardware noise. Nevertheless, existing hardware is suitable for the implementation of optimization algorithms such as open-system quantum annealing in which the minimum value of a complex function of a large number of binary variables is sought. Open-system quantum annealing is closely related to classical simulated annealing that relies on stochastic dynamics and relaxation toward thermal equilibrium. Here, we present a tailored solvable example that demonstrates a regime in which the open-system quantum annealing algorithm outperforms simulated annealing.

We consider a model consisting of Ising spins that interact with each other; both pairwise interaction and interaction of triples of spins are included. Our model is characterized by a unique ground state and a metastable state with exponential degeneracy. Open-system quantum annealing includes quantum tunneling, which may improve the relaxation times. However, identifying a class of problems in which open-system quantum annealing provides a computational advantage remains an open question. We use a quasiclassical description to analyze the performance of the open-system quantum annealing algorithm optimized to take advantage of the noise-induced dissipative relaxation and quantum tunneling through potential barriers, and we identify a regime in which quantum annealing is superior. This work represents progress that could, in principle, be implemented on realistic hardware, and the speedup mechanism that we recover, which is most efficient at vanishing temperature, may have many applications.

We expect that the generic features identified in this example may make it possible to classify complex optimization problems in terms of open-system, quantum annealing performance.

Figure 1

Thermodynamic functions of a classical model characterized by the order parameter $M$ above (blue lines) and below (red lines) the phase transition temperature. Dashed lines correspond to potential energy, and solid lines correspond to free energy that includes the entropy, shown separately by a dash-dotted black line. The difference between dashed and solid lines shows the contribution from entropy. $\delta F$ is the free energy difference that has to be overcome by classical Monte Carlo dynamics at temperatures below the transition $T<T_c$.

Figure 2

The effective classical potential is shown for $s=0$, the pure transverse-field case (left); $s=s_{\mathrm{QPT}}\approx 0.698$, the zero-temperature quantum phase transition point (center); and $s=1$, the pure classical potential (right). Different lines (bottom to top on all plots) correspond to different values of $k=0,\dots ,0.5$ with equal intervals. Note that in the absence of the transverse field, the states with different values of $k$ are degenerate. Here, $q_{\min }=0$ and $q_{\max }\approx 0.467$.

Figure 3

Tunneling action as a function of inverse temperature $\beta$, for $q_{\min }=0$, $q_{\max }=0.533$ at $s=0.85>s_{\mathrm{QPT}}$. Left: Black dots and the solid blue line fit correspond to an optimal finite-temperature quantum-tunneling action. The horizontal dotted line is the $\beta \to \infty$ limit of the incoherent tunneling action corresponding to the quantum-mechanical tunneling from the lowest level of the metastable well corresponding to $k=0$. The solid black line corresponds to the optimal action of the classical Glauber dynamics. Blue and red dashed lines show the classical over-the-barrier escape action at $k=0$ and along the line $q=1-2k$ with the potential maximum at $k_{*}\approx 0.152$, respectively. The latter, $k_{*}$, is the point of inflection, i.e., the point where the minimum of the right potential well merges with the maximum at the barrier top (see Fig. 2). The vertical dashed line corresponds to the temperature-driven phase transition point ${\beta }_{PT}\approx 4.32$ corresponding to equal occupation of the two potential wells. Inset: $T(E)=-\partial S/\partial E$ at fixed $k$, which corresponds to the period of quantum-mechanical tunneling trajectory in the imaginary time representation. The dominant contribution comes from tunneling at the energy determined from $T(E)=\beta$ for $\beta >T_{\min }$; at $\beta <T_{\min }$, the transition rate is dominated by the over-the-barrier escape. Different lines from bottom to top correspond to different values of $s$ at fixed $k=0$. Red dots correspond to $T_{\min }$. Note that the minimum $E_{\min }$: $T(E_{\min })=T_{\min }$ does not correspond to the highest tunneling energy. This means that the transition from the quantum-tunneling regime to over-the-barrier escape has discontinuous first-order character. Right: Quantum-classical transition region on a larger scale. Black dots correspond to the dominant tunneling action at each $\beta$. Different lines show the quantum-mechanical tunneling action for fixed $k$; colors correspond to growing $0\le k\le 0.152$ (red to blue). The quantum-tunneling process conserves energy and the total spin value $k$. At $k>k_{\mathrm{LR}}$, the point where $E_L(k_{\mathrm{LR}})=E_R(k_{\mathrm{LR}})$, the quantum mechanical tunneling process requires the state in the metastable well to be at an energy $E\ge E_R(k)$, which comes with an additional thermal excitation cost $\beta [E_R(k)-E_L(k)]$ in the tunneling action. Therefore, for growing $k$, the tunneling action $S(\beta )$ resembles linear classical dependence. Solid black and dashed red and blue lines are the same as in the left figure.

Figure 4

Left panel: Inverse critical temperature dependence on the transverse-field strength ${\beta }_{\mathrm{PT}}(s)$ for $q_{\min }=0.88$, $q_{\max }=0.955$. The horizontal dashed line corresponds to the classical transition temperature, and the vertical dashed line marks the point of the quantum phase transition. Right panel: Comparison of the vanishing temperature quantum-tunneling action to that of the classical over-the barrier escape. The blue line shows optimal over-the-barrier escape action along the critical lineshown in the left panel. Blue points correspond to the same values of $s$ as in the left figure. The horizontal blue line corresponds to the transition rate at the critical temperature in the classical model, $s=1$. The vertical line corresponds to the point of zero-temperature quantum phase transition. The red line corresponds to the vanishing temperature limit of the quantum-tunneling action. The red horizontal dashed line corresponds to the minimum of the quantum-tunneling action at the quantum phase transition point. The local exhaustive search corresponds to $\xi =(1/N)\log {\tau }_{\mathrm{es}}=Q_{\mathrm{cl}}(q_{\min })\approx 0.227$, larger than the quantum annealing time.

Figure 5

Left panel: Quantum mechanical tunneling action at vanishing temperature in the incoherent regime as a function of the transverse-field parameter $s$. Different curves correspond to different values of $q_{\max }=0.929$, 0.946, 0.958, 0.961 (order is from bottom to top on the right side of the plot) with fixed $q_{\min }=0.9$. Note that the optimal tunneling rate emphasized by the horizontal dashed lines does not always correspond to the phase-transition point denoted by vertical dashed lines. Right panel: Optimal action for SA (blue) and QA (red) at $q_{\min }=0.88$ for different values of $q_{\max }$ [see Eqs. (19) and (20) and the text for details]. The dashed red line corresponds to the coherent quantum-tunneling action (scaling as $1/2$ of the action in the incoherent regime). The vertical dashed line corresponds to $q_{\min }=\frac{3}{2}{q}_{\max }$, at which point the classical potential has a degenerate ground state at $q=q_{\min }$ and $q=1$. At this point, both the SA action and the QA action diverge; however, the QA action diverges logarithmically slow, in contrast to the SA action. For the parameters chosen, the local exhaustive search corresponds to $\xi =(1/N)\log {\tau }_{\mathrm{es}}=Q_{\mathrm{cl}}(q_{\min })\approx 0.227$, which is above the value of the QA action in the figure, except for the close vicinity of the divergence point, i.e., QA is faster than SA and an exhaustive search for most of the parameter values.

Figure 6

Left panels: Potential barrier between the metastable and the ground state, Eq. (4), corresponding to $s=1$ for two pairs of values $(q_{\min },q_{\max })$ equal to (0, 0.633) (upper plot) and (0.88, 0.955) (lower plot). Right panel: Scaling exponent of the optimal computation time of quantum annealing (red) [see Eqs. (6) and (19)] and simulated annealing (blue) given by $(1/N)\log \tau$, with $\tau$ given by Eq. (a2) as a function of the location of the metastable minimum $q_{\min }$ and the top of the barrier $q_{\max }$. The lower of the two surfaces corresponds to the shorter computation time. QA is advantageous for a range of parameters corresponding to sufficiently narrow potential barriers. Solid lines in the plane $S=0$ correspond to $q_{\min }=q_{\max }$ and $q_{\min }=\frac{3}{2}{q}_{\max }$ (under both surfaces in the figure) outlining the range of possible potentials in the cubic model Eq. (4).