학술논문
Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
Document Type
Working Paper
Author
Hamerly, Ryan; Inagaki, Takahiro; McMahon, Peter L.; Venturelli, Davide; Marandi, Alireza; Onodera, Tatsuhiro; Ng, Edwin; Langrock, Carsten; Inaba, Kensuke; Honjo, Toshimori; Enbutsu, Koji; Umeki, Takeshi; Kasahara, Ryoichi; Utsunomiya, Shoko; Kako, Satoshi; Kawarabayashi, Ken-ichi; Byer, Robert L.; Fejer, Martin M.; Mabuchi, Hideo; Englund, Dirk; Rieffel, Eleanor; Takesue, Hiroki; Yamamoto, Yoshihisa
Source
Sci. Adv. 5:eaau0823 (2019)
Subject
Language
Abstract
Physical annealing systems provide heuristic approaches to solving NP-hard Ising optimization problems. Here, we study the performance of two types of annealing machines--a commercially available quantum annealer built by D-Wave Systems, and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillator networks--on two classes of problems, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on regular graphs of degree 3. On denser problems, however, we observe an exponential penalty for the quantum annealer ($\exp(-\alpha_\textrm{DW} N^2)$) relative to CIMs ($\exp(-\alpha_\textrm{CIM} N)$) for fixed anneal times, on both the SK model and on 50%-edge-density MAX-CUT, where the coefficients $\alpha_\textrm{CIM}$ and $\alpha_\textrm{DW}$ are problem-class-dependent. On instances with over $50$ vertices, a several-orders-of-magnitude time-to-solution difference exists between CIMs and the D-Wave annealer. An optimal-annealing-time analysis is also consistent with a significant projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the measurement-feedback facilitated all-to-all connectivity of the CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
Comment: 12 pages, 5 figures, 1 table (main text); 14 pages, 12 figures, 2 tables (supplementary)
Comment: 12 pages, 5 figures, 1 table (main text); 14 pages, 12 figures, 2 tables (supplementary)