Title | ||
---|---|---|
Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs. D-Wave 2000Q. |
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 machineu0027s 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. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Quantum Physics | Statistical physics,Spins,Discrete mathematics,Quantum,Heuristic,Exponential function,Vertex (geometry),Ising model,Scaling,Optimization problem,Mathematics |
DocType | Volume | Citations |
Journal | abs/1805.05217 | 1 |
PageRank | References | Authors |
0.37 | 10 | 22 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ryan Hamerly | 1 | 2 | 1.06 |
Takahiro Inagaki | 2 | 1 | 0.37 |
Peter L. McMahon | 3 | 27 | 2.65 |
Davide Venturelli | 4 | 90 | 9.06 |
Alireza Marandi | 5 | 15 | 1.56 |
Tatsuhiro Onodera | 6 | 1 | 0.37 |
Edwin Ng | 7 | 1 | 0.70 |
Carsten Langrock | 8 | 3 | 3.89 |
Kensuke Inaba | 9 | 1 | 0.37 |
Toshimori Honjo | 10 | 14 | 2.16 |
Koji Enbutsu | 11 | 1 | 2.06 |
takeshi umeki | 12 | 1 | 3.75 |
Ryoichi Kasahara | 13 | 1 | 4.08 |
Shoko Utsunomiya | 14 | 4 | 1.24 |
Satoshi Kako | 15 | 1 | 0.37 |
Ken-ichi Kawarabayashi | 16 | 1731 | 149.16 |
Robert L. Byer | 17 | 3 | 1.17 |
Martin M. Fejer | 18 | 1 | 0.70 |
Hideo Mabuchi | 19 | 87 | 22.07 |
Eleanor Rieffel | 20 | 488 | 48.71 |
Hiroki Takesue | 21 | 1 | 1.38 |
Yoshihisa Yamamoto | 22 | 4 | 1.92 |