Source-linked AI summary
Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
Ryan Hamerly, Takahiro Inagaki, Peter L. McMahon, Davide Venturelli, Alireza Marandi, Tatsuhiro Onodera, Edwin Ng, Carsten Langrock, Kensuke Inaba, Toshimori Honjo, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Shoko Utsunomiya, Satoshi Kako, Ken-ichi Kawarabayashi, Robert L. Byer, Martin M. Fejer, Hideo Mabuchi, Dirk Englund, Eleanor Rieffel, Hiroki Takesue, Yoshihisa Yamamoto
TL;DR
The paper asks how two physical annealing platforms perform on NP-hard Ising optimization problems. It directly benchmarks a D-Wave quantum annealer and measurement-feedback CIMs on SK and MAX-CUT instances, finding that performance depends strongly on problem connectivity and supporting efforts to increase quantum-annealer connectivity.
Problem
NP-hard Ising optimization problems remain costly, while limited connectivity in many analog solvers adds embedding overhead and can degrade time-to-solution.
Method
The study directly compares the D-Wave 2000Q quantum annealer with measurement-feedback CIMs on SK and MAX-CUT problems.
Results
Performance is problem-dependent: D-Wave has an absolute advantage on cubic MAX-CUT, while CIMs show a scaling advantage on dense problems at measured sizes.
Takeaways & Limitations
The observed performance differences provide strong experimental justification for developing quantum annealers with higher internal connectivity.
Takeaways & Limitations
Optimal-annealing-time data are accessible only over limited problem-size ranges, and the noisy lower-envelope data support multiple curve shapes, cautioning against naive extrapolation.
Abstract
from arXiv · showhide
Physical annealing systems provide heuristic approaches to solving NP-hard Ising optimization problems. Here, we study the performance of two types of annealing machines--a commercially available quantum annealer built by D-Wave Systems, and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillator networks--on two classes of problems, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on regular graphs of degree 3. On denser problems, however, we observe an exponential penalty for the quantum annealer ($\exp(-α_\textrm{DW} N^2)$) relative to CIMs ($\exp(-α_\textrm{CIM} N)$) for fixed anneal times, on both the SK model and on 50%-edge-density MAX-CUT, where the coefficients $α_\textrm{CIM}$ and $α_\textrm{DW}$ are problem-class-dependent. On instances with over $50$ vertices, a several-orders-of-magnitude time-to-solution difference exists between CIMs and the D-Wave annealer. An optimal-annealing-time analysis is also consistent with a significant projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the measurement-feedback facilitated all-to-all connectivity of the CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
Introduction
The paper introduces a direct comparison of D-Wave quantum annealing and coherent Ising machines for classical Ising optimization, emphasizing connectivity as a central distinction. It explains how each system represents spins and handles couplings in solving NP-hard problems.
- Motivation: NP-hard optimization problems can require computation time that scales exponentially with problem size, motivating alternative physical solver architectures.The motivation includes scheduling, resource allocation, route planning, and community detection.
- Connectivity: Limited connectivity forces many analog optimization systems to embed problems, adding computational cost and potentially degrading time-to-solution.Embedding can require multiple physical pseudo-spins for each logical spin variable.
- Study scope: The study performs a direct comparison between the D-Wave 2000Q quantum annealer and measurement-feedback coherent Ising machines on classical Ising optimization.The benchmark focuses on unweighted MAX-CUT and the Sherrington-Kirkpatrick spin-glass model.
- CIM operation: CIMs represent spins with degenerate optical parametric oscillators whose two stable phase states encode σ_i = +1 or −1.Time multiplexing generates many identical OPOs in a single cavity, with each circulating pulse representing one OPO.
- CIM operation: Measurement-feedback CIMs achieve intrinsic all-to-all connectivity by using electronic memory to calculate and re-inject coupling signals.The feedback signal is converted back to light and re-injected into the optical cavity.
- D-Wave architecture: The D-Wave 2000Q uses a sparse Chimera coupling graph, so dense or fully connected problems require minor embedding into Chimera subgraphs.Native clique embeddings assign each logical qubit to an L-shaped ferromagnetic chain of physical qubits.
Results
The D-Wave annealer and CIMs show sharply different performance scaling across SK and MAX-CUT instances. D-Wave performs best on sparse cubic MAX-CUT, while CIMs increasingly outperform it on dense problems, with embedding overhead and connectivity central to the comparison.
- Sherrington-Kirkpatrick (SK) spin-glass: The D-Wave success probability for SK scales with N^2 in the exponential, whereas CIM performance scales exponentially with N.This produces a dramatic success-probability difference for N ≥ 60.
- MAX-CUT: Dense MAX-CUT shows the same square-exponential D-Wave trend, while CIM success probabilities are orders of magnitude higher for N ≥ 40.The dense MAX-CUT instances were tested up to N = 61 on D-Wave and N ≤ 150 on CIM.
- Graph Density and Performance: CIM performance depends weakly on edge density, whereas D-Wave performance worsens as graph degree increases because embeddings become less compact.For D-Wave, the minimum chain length is ℓ = ⌈(d−2)/4⌉, and denser graphs weaken logical couplings in the embedded problem.
- Time to Solution and Optimal Annealing Time: Optimal-time analysis suggests CIM time to solution scales as exp(O(N^1/2)) versus exp(O(N)) for D-Wave, but the projected scaling conclusion is not conclusive.Only 25 ≤ N ≤ 50 provides accessible optimal annealing times for D-Wave, and noisy data permit alternative fits.
- MAX-CUT: D-Wave outperforms CIM by 10–100× on cubic MAX-CUT, but CIM dominates for most higher-degree or denser graphs.The reported region where D-Wave matches or outperforms CIM is narrow, centered on degrees d = 3 and 4.
- Time to Solution and Optimal Annealing Time: At N = 55, the dense MAX-CUT time-to-solution factor reaches 10^7, and extrapolation to N = 100 exceeds 10^20 in favor of CIM.These comparisons use experimentally accessible annealing-time choices, with D-Wave annealing times optimized over 1–1000 µs and CIM fixed at 1000 round trips.
Discussion
The benchmarks show that machine merits depend strongly on problem connectivity: sparse problems can perform similarly, while dense problems incur substantial embedding overhead on D-Wave. These results support increasing quantum-annealer connectivity, although broader practical evaluation remains necessary.
- Connectivity appears central to performance differences: sparse problems can be embedded in D-Wave with little or no overhead, whereas dense SK embeddings require O(N^2) physical qubits.The conclusion links this embedding overhead to decreased quantum-annealer performance on dense problems.
- Overall machine merits are highly problem-dependent across MAX-CUT and Sherrington-Kirkpatrick spin-glass benchmarks.
- Comprehensive practical comparisons should include wall-clock time, read-in and read-out, classical processing, and energy usage.These quantities were described as currently in flux for both machine types.
- The results provide strong experimental justification for efforts to increase connectivity in quantum annealers.
Methods
The study constructs random fully connected and regular graph instances, uses precomputed embeddings and empirically optimized D-Wave parameters, and benchmarks them on D-Wave and CIM platforms. Ground states are obtained with exact or high-confidence heuristic procedures, while CIM phase stabilization remains imperfect and requires post-selection.
- Instance generation: 20 random fully connected SK and dense MAX-CUT instances were created for each D-Wave size N = 2, 3, ..., 61, with overlapping and larger sizes tested on CIMs.CIM-only instances extended through N = 150.
- Instance generation: Regular sparse graphs were generated for N = 2, 4, ..., 300 and degrees d = 3, 4, ..., 20, using 20 instances per size-degree pair.Variable-density graphs used d = 1, 2, ..., (N −2) for N = 20, 30, 40, 50, 60, also with 20 instances per pair.
- Reference solutions: Exact SK ground states were obtained with Spin Glass Server using BiqMac, while MAX-CUT ground states relied on brute force for smaller instances and BLS thereafter.For N > 100 SK instances, the solver timed out before exhausting all branches; BLS solutions through N = 150 were treated as high-confidence ground states.
- Machine benchmarking: Precomputed heuristic and native-clique embeddings kept embeddings consistent across D-Wave conditions, while optimal Jc values were found by sweeping over problem size.The optimal Jc was reported as independent of annealing time.
- Machine benchmarking: D-Wave experiments used the DW2Q, while CIM experiments used Stanford 100-OPO and NTT 2048-OPO systems with computation times reported as annealing times.Read-in and read-out transfer times were excluded from the reported CIM computation times.
- Experimental caveat: Imperfect CIM phase stabilization required post-selection of both Stanford and NTT experimental data.
S1 D-Wave embeddings and Jc optimization
D-Wave performance depends strongly on embedding choice and the constraint coupling Jc. Native clique embeddings serve dense problems, while heuristic embeddings serve sparse graphs; optimal Jc varies with problem structure and must balance chain integrity against hardware limitations.
- Embedding strategy: Native clique embeddings are used for SK and dense MAX-CUT, while sparse graphs use the heuristic embedding of Cai et al.Clique embeddings are precomputed; sparse-instance embeddings are generated through the D-Wave API heuristic.
- Dense-problem optimization: Jc scales roughly as N^1/2 for SK and N^3/2 for 50%-edge-density MAX-CUT.The relations used in the main-text figures are Jc = 1.1N^1/2 for SK and Jc = 0.047N^3/2 for dense MAX-CUT.
- Variable-density optimization: For variable-density graphs, the optimal Jc scales as d at fixed N and is extrapolated using Jc = 9.5(N/20)^3/2x.The relation was also tested on N = 30 variable-edge-density graphs and found to give the optimal Jc.
- Chain constraints: Dense MAX-CUT performance is maximized near Nbr ≈ 0.7, where Nbr is the number of broken chains.This optimum lies in a narrow Jc range centered around Jc = 0.047N^3/2.
- Chain constraints: Jc must be neither too weak nor too strong: weak coupling leaves constraints unenforced, while excessive coupling degrades the physical implementation.Excessive Jc can reduce the physical spectral gap and expose finite-bit-precision and hardware-imperfection effects.
- Sparse-graph evaluation: Heuristic sparse-graph embeddings are evaluated by embedding success probability, embedding time, physical-qubit count, and average chain length.The study attempts 10 embeddings per sparse instance with a 60-second timeout.
S2 CIM data and post-selection
CIM data are filtered for optical phase stability before estimating success probabilities, while the NTT architecture uses parallel problem frames and the Stanford system uses a fixed annealing time. Post-selection improves estimates only by a bounded factor and does not account for the reported performance advantage.
- Data filtering: NTT CIM frames partition 2,048 spins into a 16-spin header, 32-spin phase-check graph, and 2,000-spin problem region.The block-diagonal coupling matrix enables approximately 2000/N problems to be solved in parallel per frame.
- Data filtering: Phase-check Hamiltonian values identify out-of-phase runs because incorrect optical phase produces HPC > 0, whereas in-phase operation drives HPC negative.The phase-check signal is computed after each run and serves as a proxy for optical phase.
- Post-selection: Selecting the best batch of 1,000 consecutive trials yields the success probability expected from a well-engineered, phase-stable CIM.Filtering removes low-success trials from periods when the machine is out of phase or marginally stable.
- Post-selection: Post-selection improves success probabilities by only a constant factor, never more than an order of magnitude, so the CIM advantage is not attributed to cherry-picking.The best-batch method is used for the CIM data reported in the main text.
- Post-selection: Post-selected success probabilities are on average only 5× higher than unfiltered probabilities.The paper therefore estimates that pessimistic phase-stability assumptions would reduce reported Stanford-CIM probabilities by at most this factor.
- CIM comparison: Stanford and NTT CIMs agree within a factor of 5 on the same SK and 50%-edge-density MAX-CUT instances for N ≤ 100.Both machines use 1,000 round trips, while the NTT annealing time is approximately Tann = (2.5N) µs and Stanford uses Tann = 1.6 ms.
- Annealing time: The CIM solution-time comparison uses a strict minimum annealing time based on pulse spacing, problem size N, and round trips R, assuming perfect parallelization.Dummy spins and feedback-electronics delays make the actual annealing time longer than this minimum.
S3 C-SDE Simulations of CIM
C-SDE simulations model the measurement-feedback CIM as a time-multiplexed OPO network and reproduce the broad experimental behavior. They show exponential asymptotic scaling and a tradeoff between annealing time and success probability, while the inferred CIM scaling remains suggestive rather than conclusive.
- Model: The CIM is modeled with truncated-Wigner theory, yielding classical stochastic differential equations for a weakly coupled, time-multiplexed OPO network.The model includes the main loop, measurement and feedback delay line, and optical noise processes.
- Model: The c-SDE pipeline represents optical loss and detection with beamsplitter and homodyne processes, processes the measured signal in an FPGA, and applies PSA gain.Only the real parts of the optical fields are retained in the classical model.
- Simulation parameters: The simulations use problem-dependent Fmax choices of 3.0N^-1/2 for SK and dense MAX-CUT and 0.35 for cubic MAX-CUT.For sparse MAX-CUT, Fmax is constant.
- Validation: Using optimal Fmax, c-SDE simulations roughly match experimental CIM performance, although the model is strictly applicable only to the Stanford CIM.The two experimental machines nevertheless show similar performance in the comparison.
- Scaling: Success probability shows clear asymptotic exponential behavior, especially for short annealing times, while time-to-solution rises exponentially at large N.The success-probability curves are fit with a logistic form intersecting the origin.
- Scaling: The optimal time to solution is the lower envelope of annealing-time curves, exposing a tradeoff between success probability and annealing time.A rough fit suggests, but does not conclusively prove, scaling of the form exp(O(N^1/2)) for CIM time to solution.
S4 Optimal Anneal-Time Analysis
The D-Wave analysis optimizes time to solution over annealing time and compares the resulting lower envelope with CIM performance. The data support a substantial CIM advantage in the tested regime, but the optimal-anneal extrapolation is not uniquely determined.
- D-Wave scaling: For SK and dense MAX-CUT, fixed-anneal success probability follows P = exp(-(N/N0)^2), with N0 varying logarithmically with annealing time.Within Tann ∈ [1, 2000] µs, N0 ≈ α + β log10(Tann/µs), with problem-dependent α and β.
- Optimization: The optimal D-Wave annealing time is found by minimizing Tsoln over the experimentally admissible annealing-time range.For each fixed problem size, the top panels visualize this optimum.
- Scope: Although the data are consistent with an exponential lower envelope, they are also consistent with many other curves, so naive extrapolation is cautioned against.The fit is stated only over the tested annealing-time range.
- Comparison: The D-Wave lower envelope is approximated as Tsoln = Ae^BN and plotted against the optimal CIM time-to-solution.The CIM comparison uses the NTT round-trip time accounting for parallelization, (2.5N) ns.
- Scope: The experimentally accessible optimal-anneal regime covers only N ∈ [40, 60] for SK and N ∈ [30, 50] for dense MAX-CUT.This limited overlap makes the precise shape of the lower envelope difficult to estimate.
S5 Performance of Parallel Tempering
The paper compares the parallel CIM with parallel tempering implemented in UFO. The CIM approaches PT@UFO on SK instances and on mid-sized MAX-CUT instances, but diverges at larger sizes.
- Comparison setup: Parallel tempering is implemented in the NASA/TAMU Unified Framework for Optimization (UFO) as PT@UFO.The PT@UFO error bars represent the minimum and maximum time-to-solution values for each size; runs used an Intel Xeon E5-1650 v2 CPU.
- SK performance: NTT’s parallel CIM comes close to PT@UFO on SK problem instances across the considered size range.
- MAX-CUT performance: NTT’s parallel CIM remains close to PT@UFO on MAX-CUT through the middle range of problem sizes, then diverges for larger instances.