Experimental investigation of performance differences between coherent Ising machines and a quantum annealer
© 2019 by the Authors. 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 measurementfeedback coherent Ising machines (CIMs) based on optical paramet...
| Main Authors: | , , , , , , , , , , , , , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Association for the Advancement of Science (AAAS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136189 |
| _version_ | 1826202474366631936 |
|---|---|
| author | 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 |
| author_facet | 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 |
| author_sort | Hamerly, Ryan |
| collection | MIT |
| description | © 2019 by the Authors. 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 measurementfeedback 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(-aDWN2)] relative to CIMs [exp(-aCIMN)] 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. |
| first_indexed | 2024-09-23T12:08:02Z |
| format | Article |
| id | mit-1721.1/136189 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:08:02Z |
| publishDate | 2021 |
| publisher | American Association for the Advancement of Science (AAAS) |
| record_format | dspace |
| spelling | mit-1721.1/1361892022-03-30T14:46:46Z Experimental investigation of performance differences between coherent Ising machines and a quantum annealer 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 © 2019 by the Authors. 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 measurementfeedback 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(-aDWN2)] relative to CIMs [exp(-aCIMN)] 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. 2021-10-27T20:34:10Z 2021-10-27T20:34:10Z 2019 2019-06-14T15:29:49Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136189 en 10.1126/sciadv.aau0823 Science Advances Creative Commons Attribution NonCommercial License 4.0 https://creativecommons.org/licenses/by-nc/4.0/ application/pdf American Association for the Advancement of Science (AAAS) Science Advances |
| spellingShingle | 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 Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title | Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title_full | Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title_fullStr | Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title_full_unstemmed | Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title_short | Experimental investigation of performance differences between coherent Ising machines and a quantum annealer |
| title_sort | experimental investigation of performance differences between coherent ising machines and a quantum annealer |
| url | https://hdl.handle.net/1721.1/136189 |
| work_keys_str_mv | AT hamerlyryan experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT inagakitakahiro experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT mcmahonpeterl experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT venturellidavide experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT marandialireza experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT onoderatatsuhiro experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT ngedwin experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT langrockcarsten experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT inabakensuke experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT honjotoshimori experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT enbutsukoji experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT umekitakeshi experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT kasahararyoichi experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT utsunomiyashoko experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT kakosatoshi experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT kawarabayashikenichi experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT byerrobertl experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT fejermartinm experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT mabuchihideo experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT englunddirk experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT rieffeleleanor experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT takesuehiroki experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer AT yamamotoyoshihisa experimentalinvestigationofperformancedifferencesbetweencoherentisingmachinesandaquantumannealer |