Abstract

Physical annealing machines are promising tools for combinatorial optimization problems. This talk presents a comparison between two types of annealing machines—a quantum annealer (QA) built by D-Wave Systems and coherent Ising machines (CIMs) based on optical parametric oscillators—on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX -CUT. Performance is strongly dependent on both the edge density of the benchmark problems and the intrinsic connectivity of the physical machine. For MAX -CUT problems on cubic graphs, the QA outperforms the CIMs by a small factor. For dense-graph MAX -CUT and SK instances, we notice an exponential performance penalty for the QA [exp(-O(N²))] relative to CIMs [exp(-O(N))]. This leads to a several-orders-of-magnitude time-to-solution difference for instances of even moderate size (N > 50). We propose that the performance penalty stems from the sparse connectivity of the QA and the resulting embedding overhead, which provides strong experimental support for efforts to increase the connectivity of quantum annealers