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

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]