|
1
|
Hamerly R, Inagaki T, McMahon PL, Venturelli D, Marandi A, Onodera T, Ng E, Langrock C, Inaba K, Honjo T, Enbutsu K, Umeki T, Kasahara R, Utsunomiya S, Kako S, Kawarabayashi KI, Byer RL, Fejer MM, Mabuchi H, Englund D, Rieffel E, Takesue H, Yamamoto Y. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Sci Adv 2019; 5:eaau0823. [PMID: 31139743 PMCID: PMC6534389 DOI: 10.1126/sciadv.aau0823] [Citation(s) in RCA: 42] [Impact Index Per Article: 8.4] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/04/2018] [Accepted: 04/17/2019] [Indexed: 05/05/2023]
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 2)] 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.
Collapse
Affiliation(s)
- Ryan Hamerly
- Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Takahiro Inagaki
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Peter L. McMahon
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- School of Applied and Engineering Physics, Cornell University, Ithaca, NY 14853, USA
- Corresponding author. (R.H.); (T.I.); (P.L.M.)
| | - Davide Venturelli
- NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, CA 94035, USA
- USRA Research Institute for Advanced Computer Science (RIACS), 615 National Avenue, Mountain View, CA 94035, USA
| | - Alireza Marandi
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- California Institute of Technology, Pasadena, CA 91125, USA
| | - Tatsuhiro Onodera
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Edwin Ng
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Carsten Langrock
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Kensuke Inaba
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Toshimori Honjo
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Koji Enbutsu
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Takeshi Umeki
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Ryoichi Kasahara
- NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Shoko Utsunomiya
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Satoshi Kako
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Ken-ichi Kawarabayashi
- National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan
| | - Robert L. Byer
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Martin M. Fejer
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Hideo Mabuchi
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
| | - Dirk Englund
- Research Laboratory of Electronics, Massachusetts Institute of Technology, 50 Vassar Street, Cambridge, MA 02139, USA
| | - Eleanor Rieffel
- NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, CA 94035, USA
| | - Hiroki Takesue
- NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
| | - Yoshihisa Yamamoto
- E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA
- ImPACT Program, Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan
| |
Collapse
|