CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20180611-132901932

[img] PDF - Submitted Version
See Usage Policy.

1870Kb

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

Abstract

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
https://arxiv.org/abs/1805.05217arXivDiscussion Paper
ORCID:
AuthorORCID
Marandi, Alireza0000-0002-0470-0050
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.
Funders:
Funding AgencyGrant Number
Council of Science, Technology and Innovation (Japan)UNSPECIFIED
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Stanford UniversityUNSPECIFIED
NASANNA16BD14C
NSFPHY-1648807
Record Number:CaltechAUTHORS:20180611-132901932
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180611-132901932
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:86965
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:11 Jun 2018 20:41
Last Modified:03 Oct 2019 19:50

Repository Staff Only: item control page