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

Abstract

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.

Alternate abstract:

Plain Language 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.