A Caltech Library Service

Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs. D-Wave 2000Q

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 Rieffel, Eleanor and Takesue, Hiroki and Yamamoto, Yoshihisa (2018) Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs. D-Wave 2000Q. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Physical annealing systems provide a heuristic approach to solve NP-hard Ising optimization problems. It is believed that the connectivity between spins in such annealers significantly impacts the machine's computational effectiveness. In this paper we study the performance of two types of annealing machines that have very different connectivity -- a commercially available quantum annealer built by D-wave Systems, which has sparse connectivity, and coherent Ising machines based on optical parametric oscillator networks, which have all-to-all connectivity. We demonstrate an exponential (e^(−O(N^2))) penalty in performance for the D-wave quantum annealer relative to coherent Ising machines when solving Ising problems on dense graphs, which is attributable to the differences in internal connectivity between the machines. This leads to a several-orders-of-magnitude time-to-solution difference between coherent Ising machines and the D-wave system for problems with over 50 vertices. Our results provide strong experimental support to efforts to increase the connectivity of physical annealers.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
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
Takesue, Hiroki0000-0003-1253-9049
Yamamoto, Yoshihisa0000-0002-4150-6804
Additional Information: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 PHY-1648807. Y.Y., P.L.M. and E.R. proposed the project. R.H. wrote the manuscript and performed D-Wave experiments and data analysis. 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. built the Stanford CIM, and T.O. and E.N. helped with theory. K.I., T.H., K.E., T.U., R.K., and H.T. built the NTT CIM. D.V., P.L.M., T.I., Y.Y., and A.M. assisted with preparation of the manuscript. S.U., S.K., and K.K. assisted with interpretation of the results. The authors declare that they have no competing financial interests.
Funding AgencyGrant Number
Council of Science, Technology and Innovation (Japan)UNSPECIFIED
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Stanford UniversityUNSPECIFIED
Record Number:CaltechAUTHORS:20180611-132901932
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:86965
Deposited By: Tony Diaz
Deposited On:11 Jun 2018 20:41
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page