Energetic Perspective on Rapid Quenches in Quantum Annealing

There are well-developed theoretical tools to analyze how quantum dynamics can solve computational problems by varying Hamiltonian parameters slowly, near the adiabatic limit. On the other hand, there are relatively few tools to understand the opposite limit of rapid quenches, as used in quantum annealing and (in the limit of infinitely rapid quenches) in quantum walks. In this paper, we develop several tools that are applicable in the rapid-quench regime. Firstly, we analyze the energy expectation value of different elements of the Hamiltonian. From this, we show that monotonic quenches, where the strength of the problem Hamiltonian is consistently increased relative to fluctuation (driver) terms, will yield a better result on average than random guessing. Secondly, we develop methods to determine whether dynamics will occur locally under rapid-quench Hamiltonians and identify cases where a rapid quench will lead to a substantially improved solution. In particular, we find that a technique we refer to as “preannealing” can significantly improve the performance of quantum walks. We also show how these tools can provide efficient heuristic estimates for Hamiltonian parameters, a key requirement for practical application of quantum annealing.

Popular Summary

One important practical area where quantum computing is poised to provide faster and better solutions is combinatorial optimization, solving problems such as scheduling deliveries efficiently. Quantum hardware designed for optimization uses a continuous-time process that seeks out lower-energy states that encode good solutions. Most of the theoretical results in this area focus on slow evolutions that do not work well on current imperfect quantum hardware. In this work, we provide tools for rapid quenches, fast evolutions that are suitable for current hardware. Each run is less likely to find a good solution, but it is cost-effective to do many repeats and take the best solution overall.

Several types of fast evolutions are known, including quantum annealing, where the cold environment of the quantum hardware helps to find low-energy states, and quantum walks, in which the quantum hardware is run for a short time without variation of the controls from their initial settings. We show that if the controls are varied monotonically, on average these fast evolutions will find better solutions. We then show that local information about the evolution is enough to predict when the solutions will be substantially better than guessing. Combining both results provides a way to efficiently specify the control settings to achieve these gains.

The quantum computers with most qubits currently (around 2000) are built specifically for solving optimization problems. Our tools enable this hardware to be exploited more effectively and facilitate the design of better optimization algorithms for solving practical problems.

Figure 1

The annealing schedule for the two-stage quantum walks in Fig. 2 (solid red line), Fig. 3 (dot-dashed blue line), and Fig. 4 (dashed magenta line). In all cases the step occurs at $t=10$ (dotted black line).

Figure 2

Two-stage quantum walk using the Hamiltonian in Eq, (5) with ${\gamma }_1=2$ and ${\gamma }_2=\frac{1}{2}$. The instantaneous quench occurs at time $t_1=10$ (vertical dotted line). The top panel shows energy expectation values $E_{\mathrm{\Gamma }}=\mathrm{\Gamma }⟨H_{\mathrm{driver}}⟩+⟨H_{\mathrm{prob}}⟩$ (gold line), $\mathrm{\Gamma }⟨H_{\mathrm{driver}}⟩$ (green line), and $⟨H_{\mathrm{prob}}⟩$ (blue line). Also shown are a guide for the eye at zero energy (dashed black line) and the minimum eigenvalue of $H_{\mathrm{prob}}$ (dashed red line). The bottom panel shows the probability $P(t)$ of being in the ground state of $H_{\mathrm{prob}}$ at time $t$ (blue line) and the probability of random guessing (dashed red line).

Figure 3

Two-stage quantum walk on a nine-qubit Sherrington-Kirkpatrick spin glass, ID code ovcjhwbhtcpcvwicoxpdpvjzqojril from the public repository in Ref. [72] with ${\gamma }_1=4$ and ${\gamma }_2=1$. The instantaneous quench occurs at time $t_1=10$, (vertical dotted line). The top panel shows energy expectations $E_{\mathrm{\Gamma }}=\mathrm{\Gamma }⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}+⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (gold line), $\mathrm{\Gamma }⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}$ (green line), and $⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (blue line). Also shown are a guide for the eye at zero energy (dashed black line) and the minimum eigenvalue of $H_{\mathrm{prob}}$ (dashed red line). The bottom panel shows the probability $P(t)$ of being in the ground state of $H_{\mathrm{prob}}$ at time $t$ (blue line).

Figure 4

Biased two-stage quantum walk on a nine-qubit Sherrington-Kirkpatrick spin glass, ID code ovcjhwbhtcpcvwicoxpdpvjzqojril from the public repository in Ref. [72] with ${\gamma }_1=3$ and ${\gamma }_2=1$, using a biased driver [Eq. (7)], biased toward the optimal solution of $H_{\mathrm{prob}}$ using $\theta =\pi /8$. The instantaneous quench occurs at time $t_1=10$ (vertical dotted line). The top panel shows energy expectations $E_{\mathrm{\Gamma }}=\mathrm{\Gamma }⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}+⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (gold line), $\mathrm{\Gamma }⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}$ (green line), and $⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (blue line). Also shown are a guide for the eye at zero energy (dashed black line) and the minimum eigenvalue of $H_{\mathrm{prob}}$ (dashed red line). The bottom panel shows the probability $P(t)$ of being in the ground state of $H_{\mathrm{prob}}$ at time $t$ (blue line).

Figure 5

Schedule $A(t)$ (solid lines) and $B(t)$ (dashed lines) of a preannealed quantum walk using $\gamma \approx 1.004$ and $t_1=4$ (vertical dotted blue line), $t_1=0.5$ (vertical dotted magenta line), and $t_1=0$ (red line; pure QW).

Figure 6

Preannealing performed on a nine-qubit Sherrington-Kirkpatrick spin glass, ID code ovcjhwbhtcpcvwicoxpdpvjzqojril from Ref. [72], for preannealing times $t_1=4$ (blue lines), $t_1=0.5$ (magenta lines), and $t_1=0$ (red lines; i.e., pure quantum walk). Dotted lines show when the preannealing ends. The top panel shows expectation values $E_{\mathrm{\Gamma }}(t)=(A/B)⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}+⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (dot-dashed lines), $⟨H_{\mathrm{prob}}{⟩}_{\psi (t)}$ (solid lines), and $\frac{A}{B}⟨H_{\mathrm{driver}}{⟩}_{\psi (t)}$ (dashed colored lines). The dashed black line indicates the minimum eigenvalue of $H_{\mathrm{prob}}$. The bottom panel shows the success probability $P(t)$ to be in the lowest eigenstate of $H_{\mathrm{prob}}$ at time $t$.

Figure 7

The top panel shows the success probability $⟨\overline{P}⟩$ for $n=5$ to $n=11$ for $21$ different linearly spaced preannealing times from $t_1=0$ to $t_1=4$; darker magenta color indicates higher $n$. All data are averaged over all 10 000 Sherrington-Kirkpatrick instances from Ref. [72] at each size. The bottom panel shows the scaling exponent $\kappa$ for a model where $p_{\mathrm{success}}\propto 2^{\kappa n}$ extracted from the linear fit on log-linear axes for different preannealing times in the inset. The inset shows the scaling of success probability versus $n$ for the same $t_1$ values, with $t_1=0$ in red and $t_1=4$ in dark blue (same color coding as the main figure).

Figure 8

Comparison, for two different $n=9$ SK instances, between the average dynamic coefficient $\overline{\chi }$ (solid red line, right axis) and the gap between the ground state and the first excited state (solid blue line, left axis). The quantities are plotted against the schedule parameter $s$ in the AQC-like paramaterization $A(t)=1-s(t),B(t)=s(t)$. The maximum of $\overline{\chi }$ and the minimum gap are indicated by the dotted red and blue lines, respectively. (a) The instance with ID code ovcjhwbhtcpcvwicoxpdpvjzqojril from Ref. [72], used in Figs. 3, 4, and 6. (b) The $n=9$ instance from Ref. [72] (ID code cpahzppaxangdnisyqutdbbjlkqamc) with the smallest minimum gap.

Figure 9

Semianalytical lower bound (solid red line) on $\overline{\chi }$ as a function of the ratio of moments ${\mu }_2(p_{\zeta })/{\mu }_1^2(p_{\zeta })$ of the distribution, governed by $p_{\zeta }$, of the rescaled energy gaps ${\zeta }_{jk}$ between computational basis states connected by the driver Hamiltonian $H_{\mathrm{driver}}$. Also shown are minimum ($0.0$, dot-dashed green line) and maximum ($0.25$, dotted blue line) possible values of $\overline{\chi }$. The lower bound is nontrivial for ${\mu }_2(p_{\zeta })/{\mu }_1^2(p_{\zeta })<1.0$ (left of dashed gray line) and is trivially zero otherwise.

Figure 10

Average success probability $P_{100}$ between $t=0$ and $t=100$ (solid blue line) calculated on the basis of $10000$ independent random points within this range and $\overline{\chi }$ (dashed red line) versus $\gamma$ for the two-qubit system given in Eq. (5). The vertical dotted line indicates the value of ${\gamma }_{\chi }$.

Figure 11

Log-linear plot of average short-time success probability $⟨P_{\mathrm{short}}⟩$ against number of qubits $n$ for quantum walks on the spin-glass dataset from Ref. [72] using the heuristic hopping rate ${\gamma }_{\chi }$ derived for each instance by optimization of the average dynamic coefficient $\overline{\chi }$ (red line). Also shown for comparison is $⟨P_{\mathrm{short}}⟩$ obtained with the fine-tuned heuristic hopping rate ${\gamma }_{\mathrm{heur}}$ (blue line) described in Ref. [55].

Figure 12

(a) A heuristic quench schedule of duration $t_f=2.0$ (red line) derived from the average dynamic coefficient $\overline{\chi }$ for a typical nine-qubit spin-glass instance from Ref. [72]. For comparison, a linear schedule (also of duration $t_f=2.0$) is also shown. (b) The instantaneous success probability $P(t)$ for measuring the problem ground state for each time $t$ as the quench progresses along the heuristic schedule (red line) and the linear schedule (blue line).