Physics (Internal)

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

This event is part of the Physics Department Colloquia Series.

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 universal 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 annealing 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 traditional computing architectures. Here, I present reasons why this might be the case: The benchmarks used to test the D-Wave machine are encoded in the restrictive Chimera topology dictated by fabrication constraints of the device. 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 quantum, as well as vanilla classical optimization methods, i.e., not a measure of sufficient rigor to detect quantum speedup. Our results thus show that a careful design of the hardware architecture and benchmark problems is key when building quantum annealing machines and we present alternative benchmark strategies in the quest for detecting quantum speedup.

Work done in collaboration with R. Andrist, F. Hamze, A. Ochoa and Z. Zhu.