Experimental investigation of performance differences between coherent Ising machines and a quantum annealer

Ryan Hamerly; Takahiro Inagaki; Peter L McMahon; Davide Venturelli; Alireza Marandi; Tatsuhiro Onodera; Edwin Ng; Carsten Langrock; Kensuke Inaba; Toshimori Honjo; Koji Enbutsu; Takeshi Umeki; Ryoichi Kasahara; Shoko Utsunomiya; Satoshi Kako; Ken-Ichi Kawarabayashi; Robert L Byer; Martin M Fejer; Hideo Mabuchi; Dirk Englund; Eleanor Rieffel; Hiroki Takesue; Yoshihisa Yamamoto

doi:10.1126/sciadv.aau0823

Experimental investigation of performance differences between coherent Ising machines and a quantum annealer

Sci Adv. 2019 May 24;5(5):eaau0823. doi: 10.1126/sciadv.aau0823. eCollection 2019 May.

Authors

Ryan Hamerly^{1

2}, Takahiro Inagaki³, Peter L McMahon^{2

4

5}, Davide Venturelli^{6

7}, Alireza Marandi^{4

8}, Tatsuhiro Onodera⁴, Edwin Ng⁴, Carsten Langrock⁴, Kensuke Inaba³, Toshimori Honjo³, Koji Enbutsu⁹, Takeshi Umeki⁹, Ryoichi Kasahara⁹, Shoko Utsunomiya², Satoshi Kako², Ken-Ichi Kawarabayashi², Robert L Byer⁴, Martin M Fejer⁴, Hideo Mabuchi⁴, Dirk Englund¹, Eleanor Rieffel⁶, Hiroki Takesue³, Yoshihisa Yamamoto^{4

10}

Affiliations

¹ Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA.
² National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
³ NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
⁴ E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA.
⁵ School of Applied and Engineering Physics, Cornell University, Ithaca, NY 14853, USA.
⁶ NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, CA 94035, USA.
⁷ USRA Research Institute for Advanced Computer Science (RIACS), 615 National Avenue, Mountain View, CA 94035, USA.
⁸ California Institute of Technology, Pasadena, CA 91125, USA.
⁹ NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
¹⁰ ImPACT Program, Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan.

Abstract

Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines-a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators-on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(-α_DW N ²)] relative to CIMs [exp(-α_CIM N)] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal-annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.