Probing for quantum speedup in spin-glass problems with planted solutions

TLDR

Quantum annealing devices with hundreds of qubits have made demonstrating a quantum speedup for optimization problems a coveted yet elusive goal, with the problem set exhibiting SAT‑like hardness peaks. The study introduces a method to generate frustrated Ising‑model optimization problems with tunable hardness. They benchmarked a D‑Wave Two device (up to 503 qubits) on these planted‑solution Ising problems and compared its performance to a suite of classical algorithms, including a highly optimized competitor. The results show no evidence of a quantum speedup on the hardest problems, but leave open the possibility of a speedup on easier instances, and are specific to the studied processor and problem set.

Abstract

The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.