Glassy Chimeras Could Be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines

Recently, a programmable quantum annealing machine has been built that minimizes the cost function of hard optimization problems by, in principle, adiabatically quenching quantum fluctuations. Tests performed by different research teams have shown that, indeed, the machine seems to exploit quantum effects. However, experiments on a class of random-bond instances have not yet demonstrated an advantage over classical optimization algorithms on traditional computer hardware. Here, we present evidence as to why this might be the case. These engineered quantum annealing machines effectively operate coupled to a decohering thermal bath. Therefore, we study the finite-temperature critical behavior of the standard benchmark problem used to assess the computational capabilities of these complex machines. We simulate both random-bond Ising models and spin glasses with bimodal and Gaussian disorder on the D-Wave Chimera topology. Our results show that while the worst-case complexity of finding a ground state of an Ising spin glass on the Chimera graph is not polynomial, the finite-temperature phase space is likely rather simple because spin glasses on Chimera have only a zero-temperature transition. This means that benchmarking optimization methods using spin glasses on the Chimera graph might not be the best benchmark problems to test quantum speedup. We propose alternative benchmarks by embedding potentially harder problems on the Chimera topology. Finally, we also study the (reentrant) disorder-temperature phase diagram of the random-bond Ising model on the Chimera graph and show that a finite-temperature ferromagnetic phase is stable up to 19.85(15)% antiferromagnetic bonds. Beyond this threshold, the system only displays a zero-temperature spin-glass phase. Our results therefore show that a careful design of the hardware architecture and benchmark problems is key when building quantum annealing machines.

Popular Summary

Can quantum computers indeed meet the promise of doing complex calculations faster than classical computers based on transistor technologies? While the holy grail of a programmable quantum computer will probably still take decades to reach, one can already begin to answer this question by testing programmable quantum “annealing” machines that are currently being built. These machines, such as D-Wave 2, use a non-mainstream method known as adiabatic quantum computing to perform optimization tasks. Very recently, tests performed by different research teams on the D-Wave 2 machine using spin glasses as a benchmark have shown that, although the machine indeed appears to tap into quantum effects, it shows no speedup over standard desktop computers when performing certain optimization tasks. In this theoretical paper, we present an understanding of why this might be the case.

To date, all benchmarks to test the computational capabilities of the D-Wave-type quantum annealing machines have been performed using the archetypal optimization problem of finding a ground state of an Ising spin glass. The ground-state spin configuration of such a system cannot be calculated analytically and can typically only be determined through computational searches that have to traverse a generally highly rugged energy landscape. The complexity of that landscape depends on the lattice structure. The complexity of the computational search depends, therefore, on that of the landscape as well as on the initial starting point.

The optimization algorithm used by D-Wave-type quantum machines puts the individual classical problems mapped onto spins on a so-called Chimera lattice, dictated by the machines’ underlying hardware architecture. Our finding is that, for the standard benchmark Ising spin glass on the Chimera lattice, its energy landscape is actually rather simple. This means that searching for a ground state of an Ising spin glass on the Chimera lattice is an easier exercise in optimization for both classical and quantum optimization methods, which is likely not adequate as a test of sufficient rigor to evaluate the computational speedup of quantum annealing machines.

Our results thus show that a careful design of the hardware architecture and benchmark problems is key when building quantum annealing machines.

Figure 1

Example Chimera graph with $k^2=16$ blocks of 8 qubits (black dots). This means the system has $N=128$ qubits and an effective linear size $L=\sqrt{N}=\sqrt{128}$. The high connectivity between the spins within each block effectively renders the model quasi–two dimensional. Note that the graph is not planar.

Figure 2

Top panel: Finite-size scaling of the Binder parameter $g_{\mathrm{q}}$ as a function of $T(\sqrt{N}{)}^{1/{\nu }_{\mathrm{q}}}$ for both Gaussian (full symbols) and bimodal (open symbols) disorder on the Chimera topology. The data scale very well for $T_c^{\mathrm{q}}=0$ and ${\nu }_{\mathrm{q}}=4$ in both cases. Bottom panel: Finite-size scaling of the spin-glass susceptibility ${\chi }_{\mathrm{q}}$ for both Gaussian and bimodal disorder. Plotted are ${\chi }_{\mathrm{q}}/(\sqrt{N}{)}^{2-{\eta }_{\mathrm{q}}}$ vs $T(\sqrt{N}{)}^{1/{\nu }_{\mathrm{q}}}$. The data scale very well for $T_c^{\mathrm{q}}=0$, ${\nu }_{\mathrm{q}}=4$, and ${\eta }_{\mathrm{q}}=0$. Note that there is no universality violation. Error bars are smaller than the symbols.

Figure 3

Top panel: Finite-size scaling of the ferromagnetic Binder parameter $g_{\mathrm{m}}$ as a function of $(\sqrt{N}{)}^{1/{\nu }_{\mathrm{m}}}(T-T_c^{\mathrm{m}})$ and $p=0$ (pure ferromagnet) on the Chimera topology. The data scale very well for $T_c^{\mathrm{m}}=4.1618(3)$ and ${\nu }_{\mathrm{m}}=1$. Bottom panel: Finite-size scaling of the ferromagnetic susceptibility ${\chi }_{\mathrm{m}}$. Plotted are ${\chi }_{\mathrm{m}}/(\sqrt{N}{)}^{2-{\eta }_{\mathrm{m}}}$ vs $(\sqrt{N}{)}^{1/{\nu }_{\mathrm{m}}}(T-T_c^{\mathrm{m}})$. The data scale very well for $T_c^{\mathrm{m}}\approx 4.1618(3)$, ${\nu }_{\mathrm{m}}=1$, and ${\eta }_{\mathrm{m}}=2/5$. Error bars are smaller than the symbols.

Figure 4

The disorder $p$ vs temperature $T=T_c^{\mathrm{m}}$ phase diagram for the random-bond Ising model defined on the Chimera graph. The (blue) dotted line represents the Nishimori line. The red (solid) line is a guide to the eye. Under the solid curve, the system orders ferromagnetically (FM). For $p\ge p_c\approx 0.1985(15)$, ferromagnetic order is lost and the system is paramagnetic (PM). For $p\gtrsim p_c$ and $T=0$, there is a zero-temperature spin-glass state [37].

Figure 5

Sketch of the (coarse-grained) energy landscape for a system with a zero-temperature transition [panel (a), top] and a finite-temperature transition [panel (b), bottom] to a spin-glass state. For high enough temperatures, i.e., above the critical temperature $T_c$, the energy landscape is simple, with one clear minimum that dominates and some “bumps along the way.” For a system that has a finite-temperature transition and for temperatures $T<T_c$, the energy landscape becomes rough, with clear barriers that render any classical annealing schedule inefficient because the system can easily be trapped in a metastable state for decreasing temperature. These barriers grow with increasing system size $N$ and decreasing temperature $T$ until they form a rough energy landscape for $T=0$ (ground state of the system). For a system where $T_c=0$, such as spin glasses on the Chimera topology, the energy landscape is typically simpler up until the ground state is reached. This means that for such a system, a classical annealing schedule like simulated annealing should perform better in comparison to quantum annealing, which excels when the energy landscape exhibits barriers [41].