Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly^*

There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses—the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to compare only the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup but might elucidate whether quantum annealing has a “quantum advantage” over corresponding classical algorithms, such as simulated annealing. Our results on a 496-qubit D-Wave Two quantum annealing device are compared to recently used state-of-the-art thermal simulated annealing codes.

Popular Summary

An outstanding question is whether quantum computers can indeed do complex calculations faster than classical computers based on transistor technologies. While the holy grail of a programmable universal quantum computer will still likely require decades of research, one can already begin to answer this question by testing programmable quantum annealing machines that are currently being built. In this study, which lies at the crossroads of statistical physics, computational physics, quantum computing, and big data, we show that a careful design of the hardware architecture, as well as benchmark problems, is key when building quantum annealing machines, and we present alternative benchmark strategies in the quest for detecting quantum speedup.

Whereas classical simulated annealing attempts to find the optima of hard optimization problems by quenching thermal fluctuations, quantum annealing involves quenching quantum fluctuations, and this technique may be able to outperform (classical) annealing approaches.  Programmable quantum annealing machines such as D-Wave Two (with 496 qubits) use a nonmainstream method known as adiabatic quantum annealing to perform optimization tasks. Very recently, tests performed by different research teams on the D-Wave Two machine using random spin glasses as a benchmark have shown that, although the machine indeed appears to tap into quantum effects, it shows no speedup over traditional computing architectures. Here, we compare the change in performance of specific optimization approaches—both classical and quantum—when tuning the difficulty of carefully crafted benchmark instances in order to circumvent the effects of noise and calibration errors typically found in black-box annealing machines. We find that D-Wave Two cannot solve, to optimality, many difficult problems for different types of disorder, which may stem from the machine’s intrinsic parametric noise and/or control errors. Encouragingly, we find that tasks that are designed to be computationally difficult in the quantum regime are also so in the classical regime, whereas tasks that are designed to be easier in the quantum regime remain difficult in the classical regime. Furthermore, the machine may show potential in the generation of approximate solutions.

We expect that the ability to correct for quantum errors will boost the ability of quantum annealing in the future and make it possible to more clearly differentiate between quantum annealing and classical thermal annealing.

Figure 1

Main panel: Overlap distribution $P(q)$ for three characteristic disorder instances. For the hard instances with thick barriers, we choose instances in the central [blue (dark)] box that have features that extend outside this domain. Based on classical simulations, we expect these instances to be on average among the hardest. In (a), we show the expected outcome of experiments with both simulated annealing (SA) and quantum annealing on the DW2 device (QA). Because the barriers are large and thick, we expect both classical and quantum approaches to have difficulties. In (b), we illustrate the expected behavior when the barriers are thin, i.e., double peaks (or more) that protrude from the dark boxes in the region $|q|>0.5$. The features in the energy landscape of these hard instances with thin barriers are still very pronounced, but we expect the barriers to be thinner than in (a). While SA should show little to no advantage when the barriers remain high but are thinner, if the DW2 device has any quantum advantage, it might be able to overcome these barriers. Finally, we study instances that have no features for $|q|<0.75$ (large red box in the main panel) and only have a single peak at $\pm q_{\mathrm{EA}}$. These (hard) instances with small barriers have the simplest energy landscape (c) with mostly only one dominant feature. As such, we expect any annealing approach to efficiently find the optimum of the problem (on average). Note that these are cartoons intended to illustrate the different instance classes and do not represent actual data.

Figure 2

Sorted success probabilities $p$ (after a gauge average) in percent SA (left) and the DW2 device (right) and different instance classes. The instance index $n$ is normalized by the number of instances $N_{\mathrm{sa}}$ per class for better viewing. For both cases, bimodal disorder ($U_1$) is the easiest problem class to solve. Although the shape of these functions is different, the number of sweeps in SA are chosen such that on average the success probabilities for the $U_1$ are similar using SA and the DW2. Using SA, uniform range-4 ($U_4$) instances are comparable to Sidon instances $S_{28}$ with small (“none”) barriers. Furthermore, SA does not distinguish between $S_{28}$ instances with thin and thick barriers. There is a clear progression in complexity for the different instance classes on the DW2 device. In particular, while SA can solve almost all instances studied, this is not the case for the DW2. The median success probability for the hardest instance classes ($S_{28}$) is zero on the DW2 for the number of runs performed; i.e., the machine would need many more runs to be able to find the optimum of hard native problems. Error bars are omitted for better viewing.

Figure 3

Average success probabilities $p_{\mathrm{av}}$ (after a gauge average) for DW2 and SA using different types of disorder. In all Sidon instance classes ($S_{28}$) the classical codes outperform DW2. Furthermore, success probabilities for bimodal disorder ($U_1$) are much larger than for any other instance class, therefore suggesting that the degeneracy produced by bimodal disorder makes this instance class too easy to detect quantum speedup. Note also that the classical codes, on average, do not seem to distinguish between instances with thick and thin barriers. Labels are from left to right.

Figure 4

Ratio between the average success probability for SA and DW2, $p_{\mathrm{av}}(\mathrm{SA})/p_{\mathrm{av}}(\mathrm{DW}2)$, for different disorder classes. In all $S_{28}$ cases, SA outperforms DW2 when the number of SA sweeps is tuned such that $p_{\mathrm{av}}(\mathrm{SA})/p_{\mathrm{av}}(\mathrm{DW}2)\approx 1$ for the bimodal $U_1$ class. Labels are from left to right.

Figure 5

Average success probability increase when reducing the barrier thickness (ratio between the average success probabilities for $S_{28}$ thick and $S_{28}$ thin) and removing the barriers (ratio between the average success probabilities for $S_{28}$ thick and $S_{28}$ none). While in the latter case both classical algorithms and the quantum annealer show a performance boost on average, in the former only the quantum annealer shows improvement.

Figure 6

Average success probabilities $p_{\mathrm{av}}$ (after a gauge average) for both DW2 and SA as a function of the number $k$ of low-lying energy levels above the ground state for different instance classes. The top panel shows data for the $U_1$ and $U_4$ instance classes, whereas the bottom panel shows data for the $S_{28}$ class. Both panels have the same horizontal axis; we split up the data for better viewing. The trend displayed by DW2 compared to the SA codes for the $S_{28}$ class suggests that noise might be the dominant source of the overall poor performance of the DW2 device.

Figure 7

Adjacency matrix of the D-Wave Two chip used in this study. Circles represent the individual qubits and lines the couplers. White circles represent fully functional qubits, whereas light gray circles represent working qubits with missing couplers. Broken qubits are represented by dark circles (16). This means that the total number of working qubits is 496.

Figure 8

Quantum annealing schedules employed by the D-Wave processor, where $s=t/t_f$.