Experimental investigation of performance differences between coherent Ising machines and a quantum annealer
- Creators
-
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
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.
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.Attached Files
Published - aau0823.pdf
Submitted - 1805.05217.pdf
Supplemental Material - aau0823_SM.pdf
Files
Additional details
- Alternative title
- Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs. D-Wave 2000Q
- PMCID
- PMC6534389
- Eprint ID
- 86965
- Resolver ID
- CaltechAUTHORS:20180611-132901932
- Council of Science, Technology and Innovation (Japan)
- Massachusetts Institute of Technology (MIT)
- Stanford University
- NNA16BD14C
- NASA
- PHY-1648807
- NSF
- W911NF-18-2-0048
- Army Research Office (ARO)
- Created
-
2018-06-11Created from EPrint's datestamp field
- Updated
-
2021-04-29Created from EPrint's last_modified field