Ferromagnetically Shifting the Power of Pausing

We study the interplay between quantum annealing parameters in embedded problems, providing both deeper insights into the physics of these devices and pragmatic recommendations to improve performance on optimization problems. We choose as our test case the class of bounded-degree minimum-spanning-tree problems. Through runs on a D-Wave quantum annealer, we demonstrate that pausing in a specific time window in the anneal provides improvement in the probability of success and in the time to solution for these problems. The time window is consistent across problem instances and its location is within the region suggested by prior theory and seen in previous results on native problems. An approach to enable gauge transformations for problems with the qubit coupling strength $J$ in an asymmetric range is presented and shown to significantly improve performance. We also confirm that the optimal pause location exhibits a shift with the magnitude of the ferromagnetic coupling, $|J_F|$, between physical qubits representing the same logical one. We extend the theoretical picture for pausing and thermalization in quantum annealing to the embedded case. This picture, along with perturbation-theory analysis and exact numerical results on small problems, confirms that the effective pause region moves earlier in the anneal as $|J_F|$ increases. It also suggests why pausing, while still providing significant benefit, has a less pronounced effect on embedded problems.

Figure 1

The optimal $|J_F|$ for the baseline. $T_S$ for an ensemble of 45 instances as $|J_F|$ varies. A 1-$\mu \mathrm{s}$ anneal is used. The best performance is observed at $|J_F^{\ast }|=1.6$.

Figure 2

The improvement of $p_{\mathrm{success}}$ with a pause. Top: The probability of success for an ensemble of 42 instances. $|J_F|=1.6$ and a 1-$\mu \mathrm{s}$ anneal are used. The pause duration is $100\mu \mathrm{s}$. The horizontal line shows the baseline, i.e., the no-pause results. Each data point represents the results when introducing a pause at location $s_p$. At the optimal pause locations, an improvement of about an order of magnitude in $p_{\mathrm{success}}$ is obtained. Bottom: The improvement in $p_{\mathrm{success}}$ due to the 101-$\mu \mathrm{s}$ anneal time (a 1-$\mu \mathrm{s}$ anneal plus a 100-$\mu \mathrm{s}$ pause) is not sufficient to overcome the extra time incurred when it comes to $T_S$, which becomes worse in this case. To improve $T_S$, we need to optimize the pause duration and location.

Figure 3

The effect of the pause duration on $T_S$. Left: With pause durations of $\{0.25,0.5,0.75,1,2\}\mu \mathrm{s}$, and $|J_F|$=1.8, the median $T_S$ for an ensemble of 45 instances is shown for pause locations $s_p=0.3$ and $s_p=0.32$. The reference (horizontal line and band for median and 35 and 65 percentiles, respectively) is the no-pausing case with parameters optimal for $T_S$: $t_a=1\mu \mathrm{s}$ and $|J_F|=1.6$. The data points show the median, with error bars at the 35th and 65th percentiles, after performing ${10}^5$ bootstraps over the set of instances. Center: The instance-wise absolute improvement in $T_S$ (in $\mu \mathrm{s}$). $\mathrm{\Delta }{T}_S$ represents the reduction in $T_S$ accomplished by introducing a short pause at an optimal location $s_p$. A positive $\mathrm{\Delta }{T}_S$ indicates that the $T_S$ is reduced (improved) by the introduction of the pause. $\mathrm{\Delta }{T}_S$ is calculated by subtracting the $T_S$ for the pause case with $|J_F|=1.8$ from that of the no-pause case with $|J_F|=1.6$ (the optimal $|J_F|$ for each case). The data points are the median and the error bars are 35th and 65th percentiles obtained from ${10}^5$ bootstraps over 45 instances. Right: The instance-wise improvement ratio $\mathrm{\Delta }{T}_S/T_S$. The data points are staggered along the $s_p$ axis for readability. The error bars are chosen to showcase where most of the data lie. They represent the 35th and 65th percentiles of the bootstrap samples, instead of the median value of the 35th and 65th percentiles in the instance ensemble.

Figure 4

The shift of the optimal pause location with $|J_F|$. Top left: The probability of success versus the annealing pause location for the demonstration instance. The anneal is performed with a 1-$\mu \mathrm{s}$ anneal time and a 100-$\mu \mathrm{s}$ pause. A monotonic shift in the peak location with $|J_F|$ is observed. The horizontal curve corresponds to no pause, $|J_F|=1.6$, and an anneal time of $1\mu \mathrm{s}$. The reason for lower probability of success for $|J_F|=1.2$ is detailed in Sec. 4c. Top right: The graph of the demonstration instance. The dashed red edges represent the minimum spanning tree of degree 2. Bottom: The probability of success for an ensemble of nine instances of $n=5$ with a pause duration $t_p=100\mu \mathrm{s}$ and $t_a=1\mu \mathrm{s}$. The horizontal lines (for the median) and the bands (for the 35th to 65th percentiles) are baseline results with no pause, $|J_F|=1.6$: Blue (lower) line or band, $t_a=1\mu \mathrm{s}$; orange (lower) line or band, $t_a=101\mu \mathrm{s}$.

Figure 5

The effect of partial gauges. Top: Partial gauges help to boost the average probability of success for an ensemble of instances (54 instances without gauges and 42 with gauges). $|J_F|=1.6$ is used for all of the data shown. The baseline case without pausing is shown for reference: the median is shown as the horizontal lines and the 35th and 65th percentiles are shown as half-transparent bands. The blue (lower) band is for no gauges and orange (upper) band is for 100 gauges applied. Middle: The effect of $|J_F|$ on $P_{\mathrm{succ}}$ for a single instance. $t_a=1\mu \mathrm{s}$ and a pause of duration $100\mu \mathrm{s}$ is applied. No gauge transformations are performed. Bottom: The same instance and parameters as in the middle panel, but with 100 partial gauges applied. The partial gauges help to suppress the variance and reveal the peak shift with $|J_F|$.

Figure 6

A sketch of the three regimes. Colored in purple, the left and rightmost regions are the adiabatic regimes I and III (which extend further to the left and right as indicated by the arrows). Regime II is further subdivided into three regions, a, b, and c, as in the main text, which are determined by the instantaneous gap $\mathrm{\Delta }$ and the temperature $T$. In region IIa, we expect the system to stop behaving strictly adiabatically and in region IIb approximate instantaneous thermalization may occur if the relaxation time scale is small enough, as well as nonadiabatic transitions. In region IIc, a pause may help to repopulate the GS. This should be thought of as an approximate picture of what occurs, to aid the reader. In reality, the transitions between these regions will, of course, not be sharp and defined by a single point during the evolution.

Figure 7

The shift of the minimal gap with $|J_F|$. The energy gap between the ground and the first excited states for the instantaneous quantum Hamiltonian during annealing for a toy problem. The logical problem is a disordered Ising problem with local fields ($J_{ij},h_i\in [-1,1]$) of a complete graph of size 3 (triangle), embedded to four physical qubits (square) on chimera connectivity. The gap is computed exactly by diagonalizing the instantaneous Hamiltonian. As $|J_F|$ increases, the instantaneous gap closes and the minimum gap shifts to earlier in the anneal.

Figure 8

The energy-level shift with $|J_F|$. The individual energy levels show an increase in energy upon decreasing the ferromagnetic strength (i.e., the case in which $\lambda >0$ in our perturbation theory) for the problem in Fig. 7.

Figure 9

An embedding comparison between current and future architectures. Embedding for the complete graphs for problem size $n=4$-$10$ with default embedding parameters and 10–20 instances drawn for each graph. Chimera embedding performed with D-Wave’s SAPI2 find_embedding routine with the D-Wave 2000Q hardware adjacency graph. Pegasus embedding performed with the Ocean minorminer find_embedding routine. The median number of physical qubits as a function of the number of logical qubits with error bars are at the 35th and 65th percentiles after bootstrapping over the ensemble of instances.

Figure 10

The shift of the optimal pause location for an instance with $\mathrm{\Delta }=3$ probability of success versus the annealing pause location for the $n=5$, “m5ver5” [$m=5$, $K_{1,4}+e$, $g6$: DiS], 14-instance weight set using embedding number 20 with $\mathrm{\Delta }$=3, $1\mu \mathrm{s}$ anneal, 100-$\mu \mathrm{s}$ pause, 50 000 reads and zero partial gauges. Pause location ranging from 0.2 to 0.5 and $J_{\mathrm{ferro}}$ varied from $-1.2$ to $-2.0$. The peak in $p_{\mathrm{success}}$ shifts from $s_p=0.42$ at $J_{\mathrm{ferro}}=-1.2$; to $s_p=0.36$ for $J_{\mathrm{ferro}}=-1.5$; and $s_p=0.32$ for $J_{\mathrm{ferro}}=-2.0$. Note that $\mathrm{\Delta }$=3 is the minimum delta that can be used to obtain a minimum-weight spanning tree.

Figure 11

The shift of the optimal pause location with $|J_F|$ (for multiple instances). The shifting of the optimal pause location with $|J_F|$ for multiple instances with a 100-$\mu \mathrm{s}$ pause. Note that the scale of the $y$ axis is different across instances.

Figure 12

The shift of the optimal pause location with $|J_F|$ (ensemble). The probability of success for an ensemble of nine instances of $n=5$ with a pause duration $t_p=100\mu \mathrm{s}$, and $t_a=1\mu \mathrm{s}$.

Figure 13

The improvement of the probability of success with partial gauges. The effect of partial gauges on the probability of success for ten of $n=4$ instances with varying $|J_F|$ and a no-pause schedule.

Figure 14

The effect of the pause duration on the probability of success corresponding to $T_S$ shown in Fig. 3 in Sec. B. With pause durations of $\{0.25,0.5,0.75,1,2\}\mu \mathrm{s}$ and $|J_F|=1.8$, the probability of success for an ensemble of 45 instances is shown for pause locations $s_p=0.3$ and $s_p=0.32$ (which we find to be optimal during the initial sweep). The reference (horizontal line and band for the median and the 35th and 65th percentiles, respectively) is the no-pausing case with parameters optimal for $T_S$: $t_a=1\mu \mathrm{s}$ and $|J_F|=1.6$. The data points show the median, with error bars at the 35th and 65th percentiles, after performing ${10}^5$ bootstraps over the set of instances.