Quantum vs. Optical Annealing

With Ryan Hamerly (MIT)

Quantum vs. Optical Annealing: Benchmarking the Coherent Ising Machine and D-Wave

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

Add to your calendar or Include in your list

How can mathematics help us to understand the behaviour of ants? Read more about the fanscinating work being carri… https://t.co/iCODvvxqE6 View on Twitter