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]

–

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