Solid State Technology and Devices Seminar: Quantum vs. Optical Annealing: Benchmarking the Coherent Ising > Machine and D-Wave

Seminar | July 12 | 1-2 p.m. | Cory Hall, The Hogan Room, 521

 Ryan Hamerly, Postdoctoral Fellow, Massachusetts Institute of Technology

 Electrical Engineering and Computer Sciences (EECS)

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.

 dadevera@berkeley.edu, 510-642-3214