Degeneracy, degree, and heavy tails in quantum annealing

Both simulated quantum annealing and physical quantum annealing have shown the emergence of “heavy tails” in their performance as optimizers: The total time needed to solve a set of random input instances is dominated by a small number of very hard instances. Classical simulated annealing, in contrast, does not show such heavy tails. Here we explore the origin of these heavy tails, which appear for inputs with high local degeneracy—large isoenergetic clusters of states in Hamming space. This category includes the low-precision Chimera-structured problems studied in recent benchmarking work comparing the D-Wave Two quantum annealing processor with simulated annealing. On similar inputs designed to suppress local degeneracy, performance of a quantum annealing processor on hard instances improves by orders of magnitude at the 512-qubit scale, while classical performance remains relatively unchanged. Simulations indicate that perturbative crossings are the primary factor contributing to these heavy tails, while sensitivity to Hamiltonian misspecification error plays a less significant role in this particular setting.

Figure 1

Example subgraphs of a Chimera graph with varying degrees. Points indicate qubits and lines indicate couplers. Top left is a section of a full Chimera graph, with maximum degree 6. We can disable couplers in order to change the degree, and therefore floppiness, of the qubits. Shown are reductions to target degrees 5 (top right), 4 (bottom left), and 3 (bottom right).

Figure 2

A qubit $s_i$ is floppy in a state $\vec{s}$ if there is zero effective field on the qubit, i.e., $h_i^{\mathrm{eff}}\left(\vec{s}\right)=0$. In this case changing ${\sigma }_i^z$ incurs no change in energy. In the configurations shown, all couplings are ferromagnetic with value $-1$. In $\pm 1$ problems, only qubits with even degree can be floppy (indicated with dashed outline).

Figure 3

Distribution of hardness for odd-parity $U_1^3$ and even-parity $U_1^4$ instances on 127 qubits (${\mathcal{C}}_4$). (Top) Results for $U_1^3$ instances show comparable tails at large $R$ (low success probability) for DW2X and SA. For $U_1^4$ instances, the DW2X results show the same characteristic heavy tail seen for SQA in Ref. [12], whereas SA ($2^{10}$ sweeps, chosen to give comparable results to DW2X) shows no such tail. (Bottom) We visualize these data with $R$ on the $y$ axis. DW2X performance is highly dependent on degree. For $U_1^4$ instances, DW2X and SA cross near the median, while for $U_1^3$ instances, DW2X dominates throughout the distribution.

Figure 4

(Top) Data from Fig. 3 rearranged with a linear $x$ axis. Performance of DW2X relative to SA on hard instances is far better on $U_1^3$ and $U_1^5$ instances, where qubits with zero effective field are rare, than on the $U_1^6$ instances studied in recent work [2, 9, 12]. Data points and error bars represent 95% confidence intervals from bootstrap samples. (Bottom) Corresponding plots for ${\mathcal{C}}_8$ instances, using 498 available qubits of 512.

Figure 5

Estimates of mean-field crossing time $s_{\mathrm{SV}}^{*}$ for 1000 127-qubit ${\mathcal{C}}_4$ instances of $U_1^k$ for $k\in \{3,4,5,6\}$. Instances for which no crossing was found are shown at $s=0.10$. (Top) Empirical cumulative distribution function of $s_{\mathrm{SV}}^{*}$ shows the prominence of heavy tails for $U_1^4$ and $U_1^6$ instances. (Bottom) DW2X success probability correlates well with $s_{\mathrm{SV}}^{*}$. Hard instances have late crossing, suggesting the presence of perturbative crossings. The “heavy tail” of hard instances, seen primarily for $U_1^4$ and $U_1^6$ instances, corresponds roughly to instances with $s_{\mathrm{SV}}^{*}>0.35$; transverse field is effectively off by $s=0.7$ (see Fig. 8).

Figure 6

Tail shapes for SA (top) and DW2X (bottom) on ${\mathcal{C}}_4$ 127-qubit $U_1^3, U_1^4, U_4^3$, and $U_4^4$ instances. SA is run for $2^{10}$ sweeps per sample. The problem Hamiltonian ${\mathcal{H}}_P$ is multiplied by a prefactor ranging from $0.2$ to 1. Running at $0.2$ energy scale reduces the running time of DW2X by more than 100 times on the hardest $U_1^4$ problems, while having no positive effect on $U_1^3$ problems. Instances in $U_4$ react similarly to changes in energy scale for both SA and DW2X.

Figure 7

(Top) Varying DW2X performance on $U_1^3$ and $U_1^4 {\mathcal{C}}_4$ instances; each instance is run using 10 spin-reversal transformations, each of which is repeated 10 times for a total of 100 experiments per instance. The experiment quantiles are then sorted by hardness as measured by $R$. The middle line, for example, indicates the median of 100 experiments for each of 1000 instances. $U_1^4$ results show a heavy tail at each experiment quantile, in contrast with $U_1^3$ results. (Bottom) Results for each quantile are divided by median performance $R_{\text{median}}$ and plotted against $R_{\text{median}}$. Bottom plots for $U_1^3$ and $U_1^4$ are restricted to the mutual domain. Percentiles increase bottom to top.

Figure 8

Annealing schedule of the D-Wave 2X (DW2X) processor used in this work. $\mathrm{\Delta }\left(s\right)/2$ and $\varepsilon \left(s\right)/2$ represent the prefactors on the transverse and longitudinal Hamiltonians, respectively. Operating temperature of 12 mK is shown.

Figure 9

Mean-field spectrum of a ${\mathcal{C}}_4 U_1^5$ instance with crossing time $s_{\mathrm{SV}}^{*}=0.262$. Excitation of $L_t\left(\vec{\theta }\right)$ from instantaneous spin-vector ground-state energy is shown for choices of $\vec{\theta }$ representing a selection of classical ground and excited states.

Figure 10

(Top) Varying DW2X performance on $U_1^3$ and $U_1^4$ instances; each instance is run using 10 spin-reversal transformations, each of which is repeated 10 times for a total of 100 experiments per instance. (Bottom) Results for each quantile are divided by median performance $R_{\text{median}}$ and plotted against $R_{\text{median}}$. Bottom plots for $U_1^3$ and $U_1^4$ are restricted to the mutual domain.

Figure 11

(Top) Varying noisy SA (noise $\sigma =0.03$) performance on $U_1^3$ and $U_1^4$ instances; each instance is run using 10 spin-reversal transformations, each of which is repeated 10 times for a total of 100 experiments per instance. The experiment quantiles are then sorted by hardness as measured by $R$. (Bottom) Results for each quantile are divided by the median quantile performance $R_{\text{median}}$ and plotted against $R_{\text{median}}$. Bottom plots for $U_1^3$ and $U_1^4$ are restricted to the mutual domain.

Figure 12

Hardness, as seen by QA (DW2X) and noisy SA, versus error sensitivity, as seen by QA and noisy SA. As in Figs. 7 and 10, we run 100 experiments on each of 1000 $U_1^3$ instances and 1000 $U_1^4$ instances at the ${\mathcal{C}}_4$ scale. We then sort each of the 100 quantiles by hardness, use the entrywise ratio of the 75th and 25th percentiles (the spread of quantiles) as a measure of error sensitivity and plot against the median. Close agreement between $U_1^3$ and $U_1^4$ data indicates a close relationship between error sensitivity as seen by a particular solver and hardness as seen by a particular solver, regardless of input parameters. Here we see very close agreement between DW2X error sensitivity and DW2X hardness and agreement between noisy SA error sensitivity and noisy SA hardness.

Figure 13

Time to solution for SA (top) and DW2X (bottom) on $U_1^d$ instances with sizes from ${\mathcal{C}}_3$ to ${\mathcal{C}}_{10}$. SA uses an optimized number of Monte Carlo sweeps. DW2X performance on high percentiles indicates the relative absence of heavy tails in $U_1^3$ instances and, to a lesser extent, $U_1^5$ instances. SA performance indicates that this difference cannot be explained by $U_1^3$ instances being fundamentally easier.