Quantum annealing correction for random Ising problems

We demonstrate that the performance of a quantum annealer on hard random Ising optimization problems can be substantially improved using quantum annealing correction (QAC). Our error correction strategy is tailored to the D-Wave Two device. We find that QAC provides a statistically significant enhancement in the performance of the device over a classical repetition code, improving as a function of problem size as well as hardness. Moreover, QAC provides a mechanism for overcoming the precision limit of the device, in addition to correcting calibration errors. Performance is robust even to missing qubits. We present evidence for a constructive role played by quantum effects in our experiments by contrasting the experimental results with the predictions of a classical model of the device. Our work demonstrates the importance of error correction in appropriately determining the performance of quantum annealers.

Figure 1

Embedding of the C and QAC strategies on the D-Wave processor. (a) C strategy, (b) QAC strategy. The basic unit cell of the D-Wave processor includes eight qubits (shown as circles), with the qubits on the left side coupling to adjacent unit cells up and down, and those on the right side coupling left and right. Panel (a) shows how four parallel copies of the problem for the C strategy are embedded, each with the same problem couplings $J_{ij}$ (black lines). Panel (b) shows how two logical qubits (red and blue) for the QAC strategy are embedded within a unit cell; the problem qubits $i_{1,2,3}$ are coupled using the same problem couplings $J_{ij}$ (black lines), and the penalty qubit $i_P$ couples ferromagnetically to the problem qubits with magnitude $\beta$ (light blue lines).

Figure 2

Physical and logical qubit connectivity graphs. (a) The physical connectivity graph consists of $8\times 8$ unit cells of eight qubits (denoted by circles), connected by programmable inductive couplers (lines). The 503 green (red) circles denote functional (inactive) qubits. In the ideal case, where all qubits are functional and all couplers are present, one obtains the nonplanar, degree-6 “Chimera” connectivity graph. (b) The complete degree-3 logical connectivity graph, with perfect (imperfect) logical qubits and their couplers shown in green and black (orange and red) respectively. (c) The actual logical connectivity graph. Imperfect qubits and their couplings are not shown as these were not used. We generated random problems over each of the regions shown in the rectangles of increasing sizes $\overline{N}\in \{46,66,86,112\}$ in (c). These problem sizes were chosen because they consist of square blocks of unit cells, and the tree width of a planar square lattice grows as a function of the smallest dimension of any rectangular region chosen [48].

Figure 3

Correlation plot of the success probability for the QAC and C strategies for DW2. The case of $\overline{N}=112$ logical qubits is shown. Above the diagonal line, QAC performs better, while below it C performs better. The color scale indicates the optimal $\beta$ for each instance. The QAC strategy uses both problem group decoding and logical group decoding, while the C strategy only uses problem group decoding, as discussed in Appendix pp1. QAC outperforms C for the overwhelming majority of instances. The few instances in which C outperforms QAC are those with low-lying undecodable energy states due to logical qubits with $<3$ (and weak) problem couplings to neighbors, arising from holes in the logical connectivity graph (see Appendix pp2).

Figure 4

Problem size dependence of the expected number of annealing runs $R$ for the QAC and C strategies. (a) For $\alpha =1$. (b) For $\alpha =0.5$. Various percentiles of problem hardness are included, as shown in the legend. The QAC strategy uses both problem group decoding and logical group decoding, while the C strategy only uses problem group decoding, as discussed in Appendix pp1. We observe better performance for the QAC strategy at all percentiles for the largest problem size. (c) Scaling of the ratio of $R$ values for $\alpha =0.5$ and 1. The performance of the QAC strategy decreases by a factor of less than 3 at the hardest percentile and the largest problem size, whereas the C strategy's performance decreases by a factor of close to 20. (d) Scaling of QAC for the SSSV model without coupling noise. Solid lines use an optimized number of sweeps $N_{\mathrm{SW}}$ for each problem instance, i.e., $N_{\mathrm{SW}}$ is chosen to minimize the expected number of annealing runs $N_{\mathrm{SW}}R$, while the dashed lines in the inset show the scaling for a fixed $N_{\mathrm{SW}}={10}^5$.

Figure 5

Robustness of QAC to missing penalty qubits. Effect of missing penalty qubits for $\alpha =1$ on the $95\mathrm{th}$ percentile for (a) ${\beta }_{\mathrm{opt}}$ held constant at its original QAC value, and (b) $\beta$ optimized for the number of missing qubits. The C strategy (solid red) and QAC strategy (solid yellow) lines are the same data that were displayed in Fig. 4. The new dash-dotted green, dotted blue, and dashed purple series show the effects of randomly removing $30\%,60\%$, and $90\%$ of the penalty qubits, respectively. For (a), QAC with $30\%$ loss continues to outperform C, but not at the higher percentages. For (b), performance at $30\%$ and $60\%$ loss tracks the original QAC closely, suggesting the code is highly resilient to penalty qubit loss if the penalty magnitude is adjusted accordingly. (c) The histogram displays the optimized $\beta$ values from the trial set $\{0.1,0.2,0.3,0.4,0.5\}$ for 1000 instances. The true optimal $\beta$ for the perfect QAC scheme lies between $0.1$ and $0.2$, but for $30\%$ of penalty qubits missing the optimum shifts to $0.2$, for $60\%$ missing between $0.2$ and $0.3$, and for $90\%$ missing to the maximum allowed value.

Figure 6

Optimal $\beta$ in an open quantum system model. The main figure shows the final physical ground-state probability $P_{\mathrm{GS}}$ and the post-decoding (majority vote with random tie-breaker) success probability $P_{\mathrm{S}}$ of the logical ground state, computed using the adiabatic master equation [49] for quantum annealing using the Hamiltonian (6) with $d=4$, with linear annealing schedules $A\left(t\right)=A_0(1-t/t_f)$ and $B\left(t\right)=A_{0}t/t_f$. Both probabilities exhibit an optimal $\beta$ value. The inset shows the numerically computed minimum gap between the ground and first excited state as a function of $\beta$. The peak in $P_{\mathrm{S}}$ and the minimum gap align as expected since a larger minimum gap means fewer transitions out of the ground state. However, the peak in $P_{\mathrm{GS}}$ occurs earlier, maximizing the population in all decodable states and not just the ground state. Simulation parameters are as follows: $A_0=33.84$ GHz, $t_f=100$ ns, $h=0.01$, and system bath coupling $g^2\eta /{\hslash }^2=1.2732\times {10}^{-3}$ [see Eq. (15) in Ref. 34].

Figure 7

Quantumness test by comparison to the classical SSSV model. Shown are the success probability correlations for the physical or logical ground state of the DW2 vs SSSV results for $N=448$ physical or $\overline{N}=112$ logical qubits. (a) QAC, physical, without calibration noise on the couplings $\left(\sigma =0\right)$; (b) QAC, physical, with noise $\left(\sigma =0.085\right)$; (c) C, logical, with noise $\left(\sigma =0.085\right)$; (d) QAC, logical, with noise $\left(\sigma =0.085\right)$. The instances are color-coded according to their ${\beta }_{\mathrm{opt}}$ as used in the QAC strategy [note that in (c), there is no $\beta$ but we still color-coded the instances by their QAC-optimal $\beta$ values]. For QAC with ${\beta }_{\mathrm{opt}}=0$, the ${\beta }_{\mathrm{opt}}$ value was shifted to $0.1$ to differentiate them from C. SSSV simulation parameters are as follows: temperature $T=10.56$ mK and $1\times {10}^5$ Monte Carlo sweeps. Gaussian noise with standard deviation $\sigma$ was added to the Ising couplings and local fields.

Figure 8

DW2 annealing schedule. The functions $A$ and $B$ are the ones appearing in Eq. (2). The solid horizontal black line is the operating temperature $\left(17\mathrm{mK}\right)$.

Figure 9

Decodability of observed states. Shown are the energy and Hamming distance relative to the ground state of all observed states in 1000 annealing cycles of one problem instance with $\overline{N}=112$ that lies near the $95\mathrm{th}$ percentile in terms of the time to solution. States colored red are decodable by both logical group and problem group decoding, and they tend to be low in Hamming distance. States colored light blue (yellow) are decodable by logical (problem) group only, and they occupy higher Hamming distances, with logical group decodable states generally higher in energy than problem group decodable states. Dark blue states are undecodable, and they cluster in groups that represent sets of logical qubits flipping together (see Appendix pp2).

Figure 10

Decodability of observed states for a problem instance in which C outperforms QAC. States are colored by decodability as in Fig. 9. Note the large cluster of undecodable (dark blue) states at relatively low energy but at high Hamming distance from the ground state. Here ${\beta }_{\mathrm{opt}}=0.1$.

Figure 11

Examples of error types and decodability. All states shown are experimentally observed examples. Green circles are correct logical qubits, i.e., with all their physical qubits aligned with the ground state; blue, orange, and red circles are logical qubits with, respectively, one, two, and three bit flip errors. The magnitude (though not the sign) of the problem couplings is color-coded: pink lines indicate $|J_{ij}|=\frac{1}{6}$, and the shade of the line darkens through gradations to indigo for $|J_{ij}|=1$. (a) A state decodable by both logical group decoding and problem group decoding. In this typical example, we observe two logical qubits with a single bit flip error each (blue circles) among otherwise correct logical qubits (green circles). The state is logical group decodable because single bit flips are majority-vote correctable. It is also problem group decodable because there are only two bit flips, which is not enough to ruin all three copies of the problem embedded within the QAC scheme. (b) A logical group decodable state. The six single bit flips are all decodable via majority vote, so the state is logical group decodable, but the state is not problem group decodable because each problem group is corrupted by at least one bit flip. (c) A problem group decodable state. This state has two logical qubits in the upper right-hand corner (orange circles) that are loosely coupled to the rest of the problem (pink line, $|J_{ij}|=\frac{1}{6}$) and which each have two physical problem qubits flipped from the ground-state values. The problem qubits that flipped are correlated between the two logical qubits; they belong to the same copy of the problem because the problem coupling is strong between counterpart problem qubits (purple line). This leaves one copy of the problem fully intact, and the state can be decoded using problem group decoding. (d) An undecodable state. There is a cluster of logical qubit flips (red circles) in the lower right-hand corner. That region is loosely coupled to the rest of the problem; all links going out of it are weak (pink) couplings. This means that the state with these logical qubits flipped together is a low-lying final excited state of the logical Ising problem, which has been suppressed via the repetition energy scale enhancement portion of QAC but is still observable in the problem instance's output statistics. This state belongs to the cluster observable near Hamming weight 20 in Fig. 9 in the main text.

Figure 12

Additional percentiles supplementing Fig. 5 of the main text showing the effect of missing penalty qubits. Effect of missing penalty qubits for $\alpha =1$ on the $50\mathrm{th}$ and $75\mathrm{th}$ percentiles for $\beta$ optimized for the number of missing qubits. The C strategy (solid red) and QAC strategy (solid yellow) lines are the same data that were displayed in Fig. 4. The dash-dotted green, dotted blue, and dashed purple series show the effects of randomly removing $30\%,60\%$, and $90\%$ of the penalty qubits, respectively. The performance at $30\%$ and $60\%$ loss tracks the original QAC closely, suggesting the code is highly resilient to penalty qubit loss if the penalty magnitude is adjusted accordingly.

Figure 13

Correlation of different $\alpha =0.5,\overline{N}=86$ data sets. (a) The U case, i.e., a single copy of the problem without any error correction. (b) The C strategy. (c) The QAC strategy. In all cases, the correlation is excellent, with the corresponding Pearson correlation coefficients being $\rho =0.942$ for U, $\rho =0.969$ for C, and $\rho =0.941$ for QAC.

Figure 14

Correlation between actual C and theoretical C. The plot shows the probabilities for 1000 random Ising instances with $\overline{N}=112$ perfect logical qubits, computed using the C strategy and from a single unprotected copy (U), i.e., $p_{\mathrm{C},i}$ vs $p_{\mathrm{U},i}$ for each instance $i$. A strong correlation is observed, with Pearson correlation coefficient of $0.968$.