Benchmarking coherent Ising machines and quantum annealers with MAX-CUT and SK problems

ORAL

Abstract

We benchmark the performance of two types of physical annealing machines -- coherent Ising machines (CIMs) built from coupled optical parametric oscillators, and a commercial quantum annealer (QA) by D-Wave Systems -- on a range of NP-hard Ising problems including MAX-CUT and ground-state computation of Sherrington-Kirkpatrick (SK) spin glasses. Connectivity and embeddability play a central role in the performance differences between the machines, as the QA's connections are defined on a Chimera graph while the CIM is all-to-all. The QA outperforms the CIM for MAX-CUT problems on sparse graphs, while for dense-graph MAX-CUT and SK problems, the QA exhibits an exponential performance penalty relative to the CIM. This performance difference persists in an optimal anneal-time analysis. The strong correlation between hardness and graph edge density when solving problems on the QA, which is absent in the CIM, motivates future work to increase the connectivity in quantum annealers. [arXiv:1805.05217]

*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.

–

Presenters

  • Ryan Hamerly

    • Research Laboratory of Electronics, Massachusetts Institute of Technology
    • Massachusetts Institute of Technology

Authors

  • Ryan Hamerly

    • Research Laboratory of Electronics, Massachusetts Institute of Technology
    • Massachusetts Institute of Technology

  • Takahiro Inagaki

    • NTT Basic Research Laboratories

  • Peter McMahon

    • Stanford University
    • E. L. Ginzton Laboratory, Stanford University

  • Davide Venturelli

    • NASA Ames Research Center
    • Quantum Artificial Intelligence Laboratory, USRA:RIACS and NASA
    • Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center
    • Quantum Artificial Intelligence Laboratory, Universities Space Research Association, NASA Ames Research Center

  • Alireza Marandi

    • E. L. Ginzton Laboratory, Stanford University
    • Stanford University

  • Tatsuhiro Onodera

    • Stanford University
    • E. L. Ginzton Laboratory, Stanford University

  • Edwin Ng

    • Stanford University
    • E. L. Ginzton Laboratory, Stanford University

  • Eleanor Rieffel

    • NASA Ames Research Center
    • Quantum Artificial Intelligence Lab (QuAIL) @ NASA Ames
    • Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center
    • Quantum Artificial Intelligence Laboratory, NASA Ames Research Center

  • Martin Fejer

    • Department of Applied Physics, Ginzton Laboratory, Stanford University, Stanford, CA, USA
    • Stanford University
    • Applied Physics, Stanford University
    • E. L. Ginzton Laboratory, Stanford University
    • Ginzton Laboratory, Stanford University
    • E. L. Ginzton Laboratory, Stanford

  • Hideo Mabuchi

    • Stanford University
    • E. L. Ginzton Laboratory, Stanford University
    • Ginzton Laboratory, Stanford University

  • Shoko Utsunomiya

    • National Institute of Informatics

  • Hiroki Takesue

    • NTT Basic Research Laboratories

  • Yoshihisa Yamamoto

    • E. L. Ginzton Laboratory, Stanford University