Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers

We investigate alternative annealing schedules on the current generation of quantum-annealing hardware (the D-Wave 2000Q), which includes the use of forward and reverse annealing with an intermediate pause. This work provides new insights into the inner workings of these devices (and quantum devices in general), particularly into how thermal effects govern the system dynamics. We show that a pause midway through the anneal can cause a dramatic change in the output distribution, and we provide evidence suggesting thermalization is indeed occurring during such a pause. We demonstrate that upon pausing the system in a narrow region shortly after the minimum gap, the probability of successfully finding the ground state of the problem Hamiltonian can be increased over an order of magnitude. We relate this effect to relaxation (i.e., thermalization) after diabatic and thermal excitations that occur in the region near to the minimum gap. For a set of large-scale problems of up to 500 qubits, we demonstrate that the distribution returned from the annealer very closely matches a (classical) Boltzmann distribution of the problem Hamiltonian, albeit one with a temperature at least 1.5 times higher than the (effective) temperature of the annealer. Moreover, we show that larger problems are more likely to thermalize to a classical Boltzmann distribution.

Figure 1

Annealing schedule in GHz (units of $h=1$). The operating temperature ($T=12.1$ mK, or equivalently $0.25$ GHz) of the chip is also shown (black-dashed line).

Figure 2

Dimensionless annealing schedule. We plot the ratio $Q(s):=A(s)/B(s)$, and the ratio of the operating temperature ($T=12.1$ mK) to the strength of the problem Hamiltonian, $C(s):=k_{B}T/B(s)$.

Figure 3

Example of annealing parameter $s$ as a function of time $t$ for an anneal with a pause, for both forward and reverse annealing. Here a 1-$\mu \mathrm{s}$ pause ($t_p=1\mu \mathrm{s}$) is inserted into the annealing schedule at $s_p=0.5$ (i.e., at $t=0.5\mu \mathrm{s}$), which otherwise has a total anneal time of $t_a=1\mu \mathrm{s}$.

Figure 4

A cartoon example illustrating time scales relevant to analyzing a quantum annealer with coupling to a thermal bath. We indicate the thermal relaxation time scale $t_r$ by the blue solid line, the Hamiltonian evolution time scale $t_H$, by the red (horizontal) solid line, and the pause time scale, $t_p$, by the black-dashed line [26]. The diagram focuses on the part of the anneal where the relaxation time scale is shortest, around the location of the minimum gap of the problem (e.g., around $s=0.44$ in this example). We show four characteristic regions during the anneal. (1) (Yellow) At early times, when the ground state is separated by a large gap from any excited state, and the population in the ground state is approximately 1. (2) (Green) As the energy gap closes, and the thermalization time scale decreases rapidly, thermal excitations may occur. (3) (Purple) As the energy gaps open up, the relaxation time scale increases (exponentially). Once $t_r>t_H$ instantaneous thermalization can no longer occur. If however $t_r\lesssim t_p$, a pause may allow effective thermalization, which could lead to a significantly larger population in the ground state. We indicate the point where $t_r\approx t_p$ by $s_p^{\mathrm{opt}}$. Finally, in region (4) (blue), where $t_r\gg t_p$ is the longest time scale, very little population transfer will occur (even if one pauses the system for time $t_p$). The dynamics are effectively frozen.

Figure 5

Forward annealing with a pause for a single 783-qubit (planted-solution) problem instance (${\mathcal{I}}_{783}$). The top figure shows the success probability with respect to pause length $t_p$, and the location of the pause $s_p$. The total evolution time (aside from the pause) is 1 $\mu \mathrm{s}$. The corresponding bottom figure shows the average energy (in arbitrary units) returned by the annealer. Each data point is averaged from 10 000 anneals with five different choices of gauge. In the absence of a pause, $P_0\approx {10}^{-4}$.

Figure 6

Dependence of success probability $P_0$ on pause length $t_p$, for the same problem considered from Fig. 5 (${\mathcal{I}}_{783}$), where we fix $s_p=0.44$ (corresponding to the peak in Fig. 5). We see increasing the pause length corresponds to a larger success probability (although it mostly saturates around 500 $\mu \mathrm{s}$). In the absence of a pause the success probability is $P_0\approx {10}^{-4}$, which increases by several orders of magnitude to around 20%. The red solid line is the linear fit to the tail end ($t_p>{10}^{1.5}\mu \mathrm{s}$). Inset: same as main figure, but with linear scale on the $t_p$ axis. Each data point is averaged from 10 000 anneals with five different choices of gauge.

Figure 7

Effect of changing the pause length for a 12-qubit problem instance (${\mathcal{I}}_{12}^0$). Each data point is from 10 000 annealing runs using five different gauges. The anneal time $t_a=1\mu \mathrm{s}$ for all data sets is shown.

Figure 8

Effect of changing the anneal time for ${\mathcal{I}}_{12}^0$. Each data point is from 10 000 annealing runs using five different gauges. The pause length $t_p=100\mu \mathrm{s}$ for all data sets is shown.

Figure 9

The optimal pause point $s_p^{\mathrm{opt}}$ as a function of problem size, for two different problem classes (see legend). The problems are generated on a square subgraph of the chimera with “side length” SL, consisting of $\mathrm{SL}\times \mathrm{SL}$ unit cells each containing eight qubits (see Fig. 23 of Appendix pp4). Each SL shown [4,8,12,16] corresponds to (taking account for dead qubits) $N=[127,507,1141,2031]$, respectively. Each data point shown is an average over (at least) 50 instances. Error bars represent the standard deviation. Each instance (for each $s_p$ tested) is averaged from 10 000 anneals with five different choices of gauge, with $t_a=1\mu \mathrm{s}$ (not including the pause time), and $t_p=100\mu \mathrm{s}$.

Figure 10

The width of the peak on a graph of $|⟨E⟩|$ vs $s_p$, as a function of problem size. The FWHM is the width of the peak in the energy curve $|⟨E⟩|$ as a function of $s_p$, at $(|E(s_p^{\mathrm{opt}})|+|E_{\mathrm{BG}}|)/2$ where $E_{\mathrm{BG}}$ is the background average energy (i.e., the average energy returned from the annealer in the absence of a pause), and $E(s_p^{\mathrm{opt}})$ the (mean) energy returned by the annealer at the optimal pause point. Note, modulus is used since all energies observed are negative. The problems (same as in Fig. 9) are generated on a square subgraph of the chimera with “side length” SL, consisting of $\mathrm{SL}\times \mathrm{SL}$ unit cells each containing eight qubits (see Fig. 23 of Appendix pp4). Each SL shown [4,8,12,16] corresponds to (taking account for dead qubits) $N=[127,507,1141,2031]$, respectively. Each data point shown is an average over (at least) 50 instances. Error bars represent the standard deviation. Each instance (for each $s_p$ tested) is averaged from 10 000 anneals with five different choices of gauge, with $t_a=1\mu \mathrm{s}$ (not including the pause time), and $t_p=100\mu \mathrm{s}$.

Figure 11

For the planted problems of Fig. 9 (50 instances per side length), we plot the success probability under the default annealing schedule (with $t_a=1\mu \mathrm{s}$) $P_0$ as compared to the success probability for an anneal with pause ($t_p=100\mu \mathrm{s}$) at the optimal pause point, $P_0(s_p^{\mathrm{opt}})$. We see typically orders of magnitude improvement for the hard problems. Note, the problems, which are plotted vertically on the $y$ axis, have $P_0=0$ (i.e., are not solved once over all anneals). Note, some problems, which are not solved once, even under the pause, are not included.

Figure 12

Reverse annealing with pause at $s_p$ (solid lines), for four different initial configurations for a 12-qubit problem ${\mathcal{I}}_{12}^0$. We plot the average energy (arbitrary units) returned from 5000 anneals, evolved at rate $ds/dt=1\mu {\mathrm{s}}^{-1}$, and $t_p=100\mu \mathrm{s}$. We consider ground- and first excited-state configurations, as well as two highly excited energy levels. The energy level $E_i$ is indicated on the right-hand side. We also show the corresponding forward-annealing curve (black-dashed line). This problem has a minimum gap at $s=0.44$ indicated in the figure. Note a sample of the spectrum for this problem is shown in Fig. 21 in Appendix pp1.

Figure 13

Correlation between the location of the minimum gap, $s_{\mathrm{gap}}$, and the optimal pause point $s_p^{\mathrm{opt}}$ for 100 problems of size 12 qubits. These problems have $J_{ij}\in [-1,1]$ (uniformly random) and $h_i=0$. We divide the data into two groups based on their minimum gap ${\mathrm{\Delta }}_{\min }$ (see legend), and we also indicate by the dash-dot (vertical) line the location corresponding to $Q(s_{\mathrm{gap}})=0.1$. We fix the pause length to $t_p=1000\mu \mathrm{s}$, and total anneal time (excluding the pause) to $t_a=1\mu \mathrm{s}$. Data from the annealer is averaged over 10 000 anneals, with ten different choices of gauge.

Figure 14

Effect of reducing problem energy scale (for the same 100 problems studied in Fig. 13). We divide the problem Hamiltonian $H_p$ by 1,2,4,8 (see legend). Inset: mean data point for each group of 100 instances upon dividing $H_p$ by 1,2,4,8 (see legend). The dash-dot line is the least-squares fitting to the median data point. Error bars are the standard deviation.

Figure 15

KL divergence $D^{\mathrm{KL}}$ between data from the annealer $P_{\mathrm{DW}}$ and the Boltzmann distribution $P_{\mathrm{QBM}}$ (projected onto the computational basis) for various choices of $(s,T)$, for a single 12-qubit instance (${\mathcal{I}}_{12}^1$). The D-Wave data is sampled from an anneal with a pause of length $t_p=1000\mu \mathrm{s}$ at $s_p^{\mathrm{opt}}$, with $t_a=1\mu \mathrm{s}$ (from 10 000 anneals and ten choices of gauge). We indicate in the plot three key parameters; the physical temperature $T_{\mathrm{DW}}=12.1$ mK, the location of the minimum gap $s_{\mathrm{gap}}$, and the optimal pause point $s_p^{\mathrm{opt}}$. The white diamond corresponds to the minimum value of $D^{\mathrm{KL}}$ over all $(s,T)$, and is equal to $D_{\min }^{\mathrm{KL}}=0.01$ bits of information. Note, to be able to distinguish the features in the plot, we set the upper limit on the plot to be $D^{\mathrm{KL}}=0.2$ (any value above this is mapped to this color).

Figure 16

Comparison of the D-Wave probability distribution and the closest fit (as measured by KL-divergence) to a quantum Boltzmann (QBM) distribution of the form $\exp [-\beta (T)H(s)]$, where the fit is over the parameters $(s,T)$ for ${\mathcal{I}}_{12}^2$. Optimal values for this problem are $(s^{\ast },T^{\ast })=(0.76,18.5\mathrm{mK})$ (corresponding to $D_{\min }^{\mathrm{KL}}=0.03$). Here $p_i$ is the probability of observing a configuration with energy $E_i$, and $g_i$ is the degeneracy of that energy level. The solid and dash-dot lines are the least-squares fit for the annealer data and the QBM data, respectively. The annealer data is from a schedule with a pause at the optimal pause point ($s_p^{\mathrm{opt}}=0.59$), over 50 samples, each of 10 000 anneals (and ten gauges), with $t_a=1\mu \mathrm{s}$, $t_p=1000\mu \mathrm{s}$. Error bars are standard deviation over the 50 samples.

Figure 17

Fitting experimental data to linear fit for a single 501-qubit instance (${\mathcal{I}}_{501}^0$). We show data for three different pause points (and from the standard annealing schedule). We see the standard schedule is almost indistinguishable from the case where the anneal is paused at $s=0.2,0.8$ (slope $\tilde{\beta }\approx 0.35$), however, when pausing at $s=s_p^{\mathrm{opt}}=0.44$ for this instance, we see a change in the distribution returned (purple, with slope $\tilde{\beta }=0.44$). We also plot the corresponding classical Boltzmann distribution expected (black-dashed line) if the systems are thermalizing to $H_p$ at $s^{\ast }=s_p^{\mathrm{opt}}$, at temperature 12.1mK (with slope $\tilde{\beta }=0.61$). Note, freeze out at $s^{\ast }=1$ would give $\tilde{\beta }=2.52$. Inset: average energy returned by the annealer as a function of pause point for the same instance. The curve has a minimum value at $s_p^{\mathrm{opt}}=0.44$. Experimental data obtained from 10 000 anneals with five choices of gauge, with $t_a=1\mu \mathrm{s}$, and $t_p=100\mu \mathrm{s}$.

Figure 18

Quantifying accuracy of linear regression using $R^2$ for $\ln (p_i/g_i)$ as a function of $E_i$ (as demonstrated in Fig. 17) for a single 501-qubit instance (${\mathcal{I}}_{501}^0$). For each data point shown, we obtain a least-squares fitting from the distribution returned by the annealer from which we calculate the $R^2$ value. The solid line (red, right axis) is the average energy returned from the annealer. We see the peak in $R^2$ corresponds to the region around $s_p^{\mathrm{opt}}$ (just after $s_p=0.4$). Each data point is obtained from 10 000 anneals with five choices of gauge, with $t_a=1\mu \mathrm{s}$, and $t_p=100\mu \mathrm{s}$.

Figure 19

Box plot of the difference between the pause point for which the maximal $R^2$ value is found $s_{R^2}^{\max }$ (i.e., the closest to a Boltzmann distribution), and the optimal pause point $s_p^{\mathrm{opt}}$, with problem size. The problems are defined on square subgraphs of the full D-Wave chimera with side length SL. Each SL contains at least 55 instances. Plotted in the box is median, lower ($q_1$), and upper ($q_3$) quartiles. Whiskers are minimum and maximum values across the entire data set, excluding outliers. Outliers are red crosses, determined by being larger (smaller) than $q_3+1.5(q_3-q_1)$ [$q_1-1.5(q_3-q_1)$]. To collect our data we used 10 000 anneals with five choices of gauge, with $t_a=1\mu \mathrm{s}$, and $t_p=100\mu \mathrm{s}$, for each problem.

Figure 20

Comparison between results from the experimental D-Wave annealer (top), and a closed-system Schrödinger evolution (bottom) for a single 12-qubit problem instance (${\mathcal{I}}_{12}^0$). Both plots show the success probability $P_0$ against the pause point, for two different pause lengths ($t_p=10,1000\mu \mathrm{s}$) as shown by the legend. The annealer data is from 10 000 annealing runs, using five different gauges. Each plot contains 1000 data points evenly distributed in $s_p\in [0,1]$. Both have an annealing time of $t_a=1\mu \mathrm{s}$ (in addition to the pause time). The simulation uses 1000 time steps in the Trotterization of the evolution operator.

Figure 21

Spectrum (lowest ten energy levels) of the problem considered in Figs. 7, 8, 12, 20 (${\mathcal{I}}_{12}^0$). This problem has a small, well-defined minimum gap of 0.15 GHz located at $s=0.44$. The units are defined with $h=1$.

Figure 22

Same as Fig. 20, but with both data sets on the same plot. Both data sets correspond to $t_p=1000\mu \mathrm{s}$, and $t_a=1\mu \mathrm{s}$.

Figure 23

The D-Wave 2000Q ‘chimera’ graph, which we conducted our experiments on (the machine is housed at NASA Ames Research Center). There are $16\times 16$ unit cells each containing eight qubits. Dead (malfunctioning) qubits are not shown on the graph. Top left bordered in red is an example of a square subgraph of side length $\mathrm{SL}=4$.

Figure 24

Effect of changing the total annealing time (not including the pause time), $t_a$, for a 501-qubit-planted problem instance (${\mathcal{I}}_{501}^1$). The heat map color corresponds to the average energy, $⟨E⟩-E_0$ (arbitrary units) returned from the annealer. From top to bottom, the total anneal time $t_a=1,10,100,1000\mu \mathrm{s}$ (see legend). In the bottom figure, with longest anneal time, the pause has little to no effect. Each data point is averaged from 5000 anneals with five different choices of gauge.

Figure 25

Comparison of default annealing schedule against schedule with pause at optimal pause point, for the planted problems of Fig. 9. We use a pause of $t_p=5.5\mu \mathrm{s}$ inserted into a schedule otherwise with a total anneal time $t_a=5.5\mu \mathrm{s}$ (total execution time $11\mu \mathrm{s}$). The default schedule is run with $t_a=11\mu \mathrm{s}$, and no pause. Data for each point is an average over 50 000 anneals, with 50 gauges. Top: comparison of average energy (arbitrary units) returned by the device. We see the schedule with a pause consistently returns samples with lower average energies. Bottom: comparison of success probability. Note, those instances on the vertical axis are not solved once by the default schedule. Instances not solved by either machine are not included in the plot. We see the schedule with a pause returns samples with greater success probability.

Figure 26

Success probability $P_0$ (under the default annealing schedule with $t_a=1\mu \mathrm{s}$) as a function of minimum gap ${\mathrm{\Delta }}_{\min }$ for the 100 problem instances of size 12 qubits reported on in the main text. We also plot the operating temperature of the annealer (black-dashed line). The units are defined with $h=1$. The data is from 10 000 anneals with ten choices of gauge.

Figure 27

(Top) Spectrum of one of the ‘outliers’ ${\mathcal{I}}_{12}^{10}$ discussed in Sec. 2 2d, which has a minimum gap late in the anneal ($s_{\mathrm{gap}}=0.77$), as shown in the figure. Also notice that the first excited energy level remains very close the ground state all the way until $s=1$. Note, the blue line, which approaches $E_0$ around $s=0.4$, is a ground state of $H_p$ (doubly degenerate ground state). (Bottom) Corresponding success probability plot for the same instance where a pause of length $t_p=1000\mu \mathrm{s}$ is inserted into the anneal at point $s_p$. We see there is no clear peak (i.e., no optimal pause point), and in fact if one pauses around the location of the minimum gap there is a reduction in success probability, most likely due to excitations, which do not have time to relax back down due to the gap occurring so late in the anneal. 10 000 anneals, ten gauges.

Figure 28

Changing of the spectral properties upon rescaling the problem. This is the same 12-qubit problem studied in Fig. 29 (${\mathcal{I}}_{12}^0$). The location of the minimum gap changes as $s_{\mathrm{gap}}=[0.438,0.508,0.558,0.608]$, and the minimum gap itself changes accordingly as ${\mathrm{\Delta }}_{\min }=[0.15,0.10,0.06,0.03]$ GHz, when the problem Hamiltonian is rescaled by $[1,2,4,8]$, respectively (see legend). Energy units defined via $h=1$.

Figure 29

Success probability $P_0$ heat map for a single 12-qubit instance (${\mathcal{I}}_{12}^0$) where the annealing schedule has a pause of length $t_p$ inserted at $s_p$, where from top to bottom the problem Hamiltonian $H_p$ has been rescaled by a factor of 1,2,4,8 (that is, $H_p\to H_p/C$, where $C=1,2,4,8$). See Fig. 28 for the corresponding minimum gap plot. Each data point is an average from 10 000 anneals with five gauges. Notice the change in the color-bar scale between the different images.