CaltechAUTHORS
  A Caltech Library Service

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

Hamerly, Ryan and Inagaki, Takahiro and McMahon, Peter L. and Venturelli, Davide and Marandi, Alireza and Onodera, Tatsuhiro and Ng, Edwin and Langrock, Carsten and Inaba, Kensuke and Honjo, Toshimori and Enbutsu, Koji and Umeki, Takeshi and Kasahara, Ryoichi and Utsunomiya, Shoko and Kako, Satoshi and Kawarabayashi, Ken-ichi and Byer, Robert L. and Fejer, Martin M. and Mabuchi, Hideo and Englund, Dirk and Rieffel, Eleanor and Takesue, Hiroki and Yamamoto, Yoshihisa (2019) Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Science Advances, 5 (5). Art. No. eaau0823. ISSN 2375-2548. PMCID PMC6534389. https://resolver.caltech.edu/CaltechAUTHORS:20190530-083242065

[img] PDF - Published Version
Creative Commons Attribution Non-commercial.

1645Kb
[img] PDF - Supplemental Material
Creative Commons Attribution Non-commercial.

1122Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190530-083242065

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^2)] 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1126/sciadv.aau0823DOIArticle
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6534389PubMed CentralArticle
https://advances.sciencemag.org/cgi/content/full/5/5/eaau0823/DC1PublisherSupplementary Materials
ORCID:
AuthorORCID
Hamerly, Ryan0000-0003-4976-2236
Inagaki, Takahiro0000-0003-1322-8744
McMahon, Peter L.0000-0002-1177-9887
Venturelli, Davide0000-0003-0452-7603
Marandi, Alireza0000-0002-0470-0050
Ng, Edwin0000-0002-3695-1698
Langrock, Carsten0000-0002-2947-5312
Inaba, Kensuke0000-0003-1182-4198
Honjo, Toshimori0000-0002-2176-9842
Enbutsu, Koji0000-0003-2462-0987
Umeki, Takeshi0000-0002-5787-5911
Utsunomiya, Shoko0000-0003-3667-1642
Kako, Satoshi0000-0001-7905-9424
Kawarabayashi, Ken-ichi0000-0001-6056-4287
Byer, Robert L.0000-0003-1331-0318
Fejer, Martin M.0000-0002-5512-1905
Mabuchi, Hideo0000-0002-5156-7678
Englund, Dirk0000-0002-1043-3489
Takesue, Hiroki0000-0003-1253-9049
Yamamoto, Yoshihisa0000-0002-4150-6804
Additional Information:© 2019 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC). Submitted 4 May 2018; Accepted 17 April 2019; Published 24 May 2019. We acknowledge S. Mandrà for useful discussions and parallel-tempering simulation results and D. Lidar, A. King, and C. McGeoch for helpful correspondence. Funding: This research was funded by the Impulsing Paradigm Change through Disruptive Technologies (ImPACT) Program of the Council of Science, Technology and Innovation (Cabinet Office, Government of Japan). R.H. is supported by an IC Postdoctoral Research Fellowship at MIT, administered by ORISE through U.S. DOE and ODNI. P.L.M. was partially supported by a Stanford Nano- and Quantum Science and Engineering Postdoctoral Fellowship. D.V. acknowledges funding from NASA Academic Mission Services contract no. NNA16BD14C. H.M., E.N., and T.O. acknowledge funding from NSF award no. PHY-1648807. D.E. acknowledges support from the U.S. ARO through the ISN at MIT (no. W911NF-18-2-0048) and the SRC-NSF E2CDA program. Author contributions: Y.Y., P.L.M., and E.R. proposed the project. R.H. performed D-Wave experiments and data analysis and prepared the figures. R.H., P.L.M., D.V., and T.I. wrote the manuscript. T.I. and P.L.M. performed NTT and Stanford CIM experiments, respectively. D.V. helped with D-Wave experiments and data analysis. A.M., C.L., R.L.B., M.M.F., and H.M. contributed to building the Stanford CIM. K.I., T.H., K.E., T.U., R.K., and H.T. contributed to building the NTT CIM. R.H. performed simulations of the CIM, adapting code from P.L.M., E.N., and T.O. E.R., Y.Y., and A.M. assisted with preparation of the manuscript. S.U., S.K., K.-i.K., and D.E. assisted with interpretation of the results. Competing interests: T.I., H.T., T.H., S.U., Y.Y. are inventors on patent JP6429346 awarded in November 2018 to National Institute of Informatics (NII), NTT, and Osaka University that covers an OPO pulse sequence for calculation and stabilization of CIM. A.M., Y.Y., R.L.B., and S.U. are inventors on patent US9830555 awarded in November 2017 to Stanford University that covers a CIM based on a network of OPOs. S.U., Y.Y., and H.T. are inventors on patent US10140580 awarded in November 2018 to NII and NTT that covers a CIM using measurement feedback. T.I., K.I., H.T., and T.H. are inventors on patent application PCT/JP2018/038994 submitted by NTT that covers a phase checking scheme for the CIM. T.U. and K.E. are inventors on patent JP5856083 awarded in February 2016 to NTT that covers phase-sensitive amplifiers based on periodically poled lithium niobate waveguides. P.L.M. is an advisor to QC Ware Corp. The authors declare no other competing interests. Data and materials availability: All data needed to evaluate the conclusions in the paper are present in the paper and/or the Supplementary Materials. Additional data related to this paper may be requested from the authors.
Funders:
Funding AgencyGrant Number
Council of Science, Technology and Innovation (Japan)UNSPECIFIED
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Stanford UniversityUNSPECIFIED
NASANNA16BD14C
NSFPHY-1648807
Army Research Office (ARO)W911NF-18-2-0048
Issue or Number:5
PubMed Central ID:PMC6534389
Record Number:CaltechAUTHORS:20190530-083242065
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190530-083242065
Official Citation:Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. BY 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. SCIENCE ADVANCES 24 MAY 2019 : EAAU0823; DOI: 10.1126/SCIADV.AAU0823
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:95951
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 May 2019 16:19
Last Modified:03 Oct 2019 21:18

Repository Staff Only: item control page