Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing

The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. A more modest goal is to demonstrate a scaling advantage over a class of classical algorithms for a computational problem running on quantum hardware. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here, we overcome this obstacle using a class of problem instances constructed by systematically combining many-spin frustrated loops with few-qubit gadgets exhibiting a tunneling event—a combination that we find to promote the presence of tunneling energy barriers in the relevant semiclassical energy landscape of the full problem—and we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to more than 2000 qubits. We identify the gadgets as being responsible for the optimal annealing time, whose existence allows us to perform an optimal time-to-solution benchmarking analysis. We perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing (SQA), and establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing. Namely, we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: SQA exhibits the best scaling for annealing algorithms by a significant margin. This is a finding of independent interest, since we associate SQA’s advantage with its ability to transverse energy barriers in the semiclassical energy landscape by mimicking tunneling. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes based on a similar principle of promoting the presence of energy barriers that can be overcome more efficiently using quantum rather than thermal fluctuations, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.

Popular Summary

Quantum computers offer the promise of much faster performance compared to their digital counterparts, but observations of such a speedup remain elusive. The largest quantum information processing devices currently available are commercial quantum annealers manufactured by D-Wave Systems. Despite several years of extensive testing, a complete determination of their scaling performance with problem size has not been possible. Here, we overcome the main technical obstacle of this assessment and establish the first example of a scaling advantage for a quantum annealer over classical simulated annealing.

The D-Wave devices specialize primarily in solving combinatorial optimization problems and are designed to represent physical implementations of quantum annealing. The main technical obstacle to benchmarking their performance has been the inability to verify an optimal annealing time, without which no definitive conclusion about scaling can be drawn. By using a specially designed class of problems, we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to 2000 quantum bits.

While we find that the D-Wave device scales better than simulated annealing, we do not find evidence for a quantum speedup. Simulated quantum annealing exhibits the best scaling. This is a finding of independent interest since we associate simulated quantum annealing’s advantage with its ability to traverse energy barriers in the semiclassical energy landscape by mimicking tunneling.

Our approach paves the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.

Figure 1

Optimal annealing time and optimal TTS. Result shown are for the “logical-planted” instance class. (a) TTS (blue solid line) and $p_S$ (red dashed line) for a representative problem instance at size $L=16$. A clear minimum in the TTS is visible at $t^{*}=50\mu \mathrm{s}$, thus demonstrating the existence of an optimal annealing time for this particular instance (but not by itself for the problem class). Note that the decreasing or increasing TTS is associated with $p_S$ growing sufficiently fast or too slowly, respectively, with increasing $t_f$. (b) Median TTS as a function of annealing time for $L\ge 12$, from 1000 instances. Dotted curves represent best-fit quadratic curves to the data (see Appendix pp7 for the scaling of $t^{*}$ with $L$, and Appendix pp11 for details on the fitting procedure). The position of the minimum of these curves gives $t^{*}$. The position of $⟨\mathrm{TTS}{⟩}^{*}$ shifts to larger $t_f$ as the system size increases. An optimum could not be established for $L<12$ for this instance class; i.e., it appears that $t^{*}<5\mu \mathrm{s}$ when $L<12$. (c) The distribution of per-instance optimal annealing times $t_i^{*}$ for different system sizes, as inferred directly from the positions of the minima as shown in (a). It is evident that the number of instances with higher optimal annealing times increases along with the system size, in agreement with (b).

Figure 2

Scaling of the optimal TTS with problem size. Result shown are for the logical-planted instance class. The data points represent the DW2KQ (blue circles) and three classical solvers: SA (red diamonds), SVMC (purple left triangles), and SQA (green right triangles) algorithms. The dashed and dotted curves correspond, respectively, to exponential and polynomial best fits with parameters shown in Fig. 3 (also given in table format in Table 3 in the Appendix). Panels (a)–(c) correspond to the 25th quantile, median, and 75th quantile, respectively. SVMC and SQA were run with $\beta =2.5$ here. Additional simulation parameters for SA, SVMC, and SQA algorithms are given in Appendix pp3. The data symbols obscure the error bars, representing the 95% confidence interval for each optimal TTS data point [computed from the fit of $\ln ⟨\mathrm{TTS}⟩$ to a quadratic function, as explained in Appendix pp11].

Figure 3

Scaling coefficients for the logical-planted instances. The data shown are for the coefficient $b$ in fits to (a) $a\exp (bL)$ and (b) $a{L}^b$ for the logical-planted instances using $L\in [12,16]$ for different quantiles and different solvers. Results are shown for the DW2KQ, SA (with a final inverse temperature of $\beta =5$), SVMC, and SQA for two different inverse temperatures. The value $\beta =0.51$ corresponds to the operating temperature of the DW2KQ of 15 mK.

Figure 4

Expectation values of the Hamming weight operator. Shown are the ground state and first excited state expectation values of $\mathrm{HW}=\frac{1}{2}\sum _{i=1}^n(1-{\sigma }_i^z)$ for the 8-qubit gadget using the DW2KQ annealing schedule. Inset: The ground state energy gap to the first excited state, as calculated using the DW2KQ annealing schedule. The dotted line corresponds to the operating temperature of the device.

Figure 5

The 8-qubit gadget used in the instance construction. The qubits (green circles) are arranged in a complete bipartite graph. Blue (red) lines correspond to ferromagnetic (antiferromagnetic) Ising couplers with magnitude 1. The value of the local fields on the qubits are given inside the circles, with a negative value indicating a spin-up preference.

Figure 6

Probability of reaching the ground state (GS) at the end of the anneal using SVMC and SQA for different simulation inverse temperatures $\beta$. (a) Simulation results for the 8-qubit gadget only. SQA’s success probability increases over a wide range of decreasing temperatures, whereas the SVMC algorithm rapidly deteriorates as the temperature decreases. Inset: Expectation values of the Hamming weight operator $\mathrm{HW}=\frac{1}{2}\sum _{i=1}^n(1-{\sigma }_i^z)$ for the 8-qubit gadget for SVMC and SQA using $\beta =2.5$. Compare to the behavior of the ground state and first excited state shown in Fig. 4. For the SVMC algorithm, to compute the expectation value of the Hamming weight operator at intermediate $s$ values, we can either project the state to the computational basis (shown) or use the spin-coherent state; the results are almost indistinguishable. For SQA, we average over the Hamming weight of the configurations in the imaginary-time direction. (b),(c) Probability of reaching the ground state at the end of the anneal using SVMC and SQA for different simulation inverse temperatures $\beta$ using two different instances, with and without the 8-qubit gadget, at the largest available size $L=16$. (b) An instance that exhibits a clear signature of a tunneling energy barrier when the gadget is introduced. (c) An instance that does not exhibit a signature for a tunneling energy barrier even with the gadget. In all panels, SVMC and SQA simulations used 8 M and 3 M sweeps, respectively, and both algorithms use the DW2KQ annealing schedule. The drop in success probability at large $\beta$ for SQA is because spin updates become less efficient at high $\beta$ and more spin updates are required to maintain the high success probability.

Figure 7

Empirical scaling behavior with and without the gadget. Shown is the distribution of the power-law scaling coefficient $a$ obtained after fitting $\ln p_S$ to $a\ln t_f+b$ for 100 instances at $L=16$, run on the DW2KQ processor. We choose $t_f\in [5,50]\mu \mathrm{s}$ since this is the range over which the TTS decreases, as seen in Fig. 1. The instances with the gadget typically exhibit a larger scaling coefficient, which leads to the observation of an optimal annealing time. In (a) and (b) error bars represent 95% confidence intervals ($2\sigma$) calculated using 1000 bootstraps of 100 gauge transformations [17].

Figure 8

Overlap of the instances that fall below the median TTS for the classical solvers and the DW2KQ. We calculate the TTS for 1000 instances with each solver’s respective optimal annealing time for the median at a given size $L$, and check which instances fall below the median TTS. Shown is the (normalized) fraction of the overlap of the instances between the solvers. Further details are given in Appendix pp9. Error bars represent 95% confidence intervals ($2\sigma$) calculated using 1000 bootstraps of 1000 instances.

Figure 9

Annealing schedules for (a) the DW2KQ and (b) the DW2X. The units are such that $\hslash =1$. As a reference, we include the operating temperatures of the devices, corresponding to 14.1 mK for the DW2KQ and 12.5 mK for the DW2X. Note the different vertical axis scales.

Figure 10

Hardware and logical graphs for instance generation. (a) DW2KQ hardware graph, (b) DW2X hardware graph, (c) DW2KQ logical graph, (d) DW2X logical graph. For DW2KQ (DW2X) subgraphs of size $L\le 16$ ($L\le 12$) were chosen starting from the lower right-hand corner. (a),(b) Available qubits are shown in green, and unavailable qubits are shown in red. Programmable couplers are shown as black lines connecting qubits. (c),(d) Complete unit cells are shown in green, and incomplete ones are shown in red. Logical couplers are shown as black lines between the unit cells. The unit cells are numbered from 0, starting from the top left-hand corner and moving across rows to the right.

Figure 11

Performance of SQA as we vary the number of Trotter slices. Shown are CPU simulation results for the success probability for a single logical-planted instance, using 32, 64, 128, and 256 Trotter slices. The success probability is maximized for 64 slices. Error bars give the 95% confidence interval generated by performing 1000 bootstraps.

Figure 12

Median scaling for SA on the logical-planted instances with three different annealing schedules. We compare the median TTS for SA using three different annealing schedules, $0.132B(s)$, where $B(s)$ is from the DW2X annealing schedule in Fig. 9, $0.396B(s)$, and a linear schedule. The dashed lines correspond to the exponential fits $\exp (a+bL)$ with $a=12.457\pm 0.332$, $b=0.996\pm 0.24$ and $a=12.489\pm 0.888$, $b=1.037\pm 0.064$ for the DW2X schedules and $a=13.321\pm 0.934$, $b=1.002\pm 0.066$ for the linear schedule. Inset: The annealing schedules in the inverse temperature $\beta$ as a function of the dimensionless parameter $s$.

Figure 13

Median quantile of ratios for the logical-planted instances. We show the ratio of the different classical solvers $C=\{\mathrm{SA},\mathrm{SQA},\mathrm{SVMC}\}$ to the DW2KQ. A positive slope, as for SA and SVMC algorithms, indicates a scaling advantage for the DW2KQ, while a negative slope, as for SQA, indicates a slowdown. The data symbols obscure the error bars representing the 95% confidence intervals ($2\sigma$) calculated using 1000 bootstraps of 1000 instances.

Figure 14

Results for the 8-qubit gadget on the DW2KQ and DW2X. (a) The gadget on four different unit cells of the DW2X. (b) The gadget on four different unit cells of the DW2KQ. On both devices we used 1000 gauges with 1000 anneals per gauge. Error bars on the data points are $2\sigma$ calculated using 1000 bootstraps of each gauge.

Figure 15

Optimal annealing time and optimal TTS for the hardware-planted instance class on the DW2KQ. (a) TTS (blue solid line) and $p_S$ (red dashed line) for a representative problem instance at size $L=16$. A clear minimum in the TTS is visible at $t^{*}\approx 550\mu \mathrm{s}$, thus demonstrating the existence of an optimal annealing time for this instance. (b) Median TTS as a function of annealing time for $L\ge 8$. Dotted curves represent best-fit quadratic curves to the data (see Appendix pp11 for details). The position of $⟨\mathrm{TTS}{⟩}^{*}$ shifts to larger $t_f$ as the system size increases. An optimum could not be established for $L<8$ for this instance class; i.e., it appears that $t^{*}<5\mu \mathrm{s}$ when $L<8$. (c) The distribution of instance optimal annealing times for different system sizes, as inferred directly from the positions of the minima as shown in (a). It is evident that the number of instances with higher optimal annealing times increases along with the system size, in agreement with (b). In (a) and (b) error bars represent 95% confidence intervals ($2\sigma$) calculated using 1000 bootstraps of 100 gauge transformations [17].

Figure 16

Scaling of $t^{*}$ with problem size for the two problem classes. Error bars represent the 95% confidence interval for the location of $t^{*}$ by fitting to a quadratic function as described in Appendix pp11.

Figure 17

Scaling of the optimal TTS with problem size for hardware-planted instances. The data points represent the DW2KQ (blue circles) and three classical solvers, SA (red diamonds), SVMC (purple left triangle), and SQA (green right triangle). The dashed and dotted curves correspond, respectively, to exponential and polynomial best fits with parameters given in Table 2. Panels (a)–(c) correspond to the 25th quantile, median, and 75th quantile, respectively. Simulation parameters for SA, SVMC, and SQA are given in Appendix pp3. The data symbols obscure the error bars, representing the 95% confidence interval for each optimal TTS data point (computed from the fit of $\ln ⟨\mathrm{TTS}⟩$ to a quadratic function as explained in Appendix pp11).

Figure 18

Correlating the SQA and SVMC algorithm success probabilities. Shown is a scatter plot correlating the highest ground state probability for SQA (up to 2 M sweeps) and SVMC (up to 8 M sweeps) algorithms. For the results shown here both algorithms use the DW2X annealing schedule with an inverse temperature of $\beta =2.5$.

Figure 19

Fits of the success probability to a power law. (a) The data points represent the DW2KQ $\ln (p_S)$ results for the logical-planted instances with (red circles) or without (blue crosses) the gadget over the range $t_f\in [5,50]\mu \mathrm{s}$. The solid lines correspond to the linear best fits $a\ln (t_f)+b$, where $a=1.546\pm 0.015$, $b=-8.348\pm 0.052$ (with the gadget), and $a=0.367\pm 0.007$, $b=-1.918\pm 0.019$ (without the gadget). The $2\sigma$ error bars are not visible as they are smaller than the data marker size. (b) The ratio of the $2\sigma$ error to the best-fit value of the linear coefficient (shown in Fig. 7 of the main text) for 100 instances of the logical-planted instances without (blue) and with (red) the gadget.

Figure 20

Scaling of the median optimal TTS with problem size for DW2KQ versus HFS and SAC. The data points represent the DW2KQ (blue circles), HFS (yellow left triangle), and SAC (green right triangle). The dashed and dotted curves correspond, respectively, to exponential and polynomial best fits with parameters given in Table 3. (a) Hardware-planted instances. (b) Logical-planted instances. The data symbols obscure the error bars, representing the 95% confidence interval for each optimal TTS data point [computed from the fit of $\ln ⟨\mathrm{TTS}⟩$ to a quadratic function as explained in Appendix pp11].

Figure 21

Success probability for MWPM on the logical-planted instances. The data symbols correspond to the average success probability calculated using 1000 bootstraps of 100 instances for $L<12$ and of 1000 instances for $L\ge 12$, and the error bars represent the 95% confidence intervals ($2\sigma$) calculated from the same bootstrap.

Figure 22

Median TTS as a function of annealing time for hardware-planted instances on the DW2X. Unlike the DW2KQ, the optimal annealing time for $L=8$ appears to be smaller than $5\mu \mathrm{s}$; for $L\ge 9$ the optimal annealing time $t^{*}$ lies within the range of achievable annealing times for the DW2X device. Furthermore, for the same problem size, the DW2X optimal annealing times are consistently smaller than those of the DW2KQ [compare to Fig. 15 and recall Fig. 16]. While the difference in the hardware graph may play a role in this, it is likely that the intrinsic differences between the two devices is responsible (see Appendix pp7-s1 for additional comparisons).