Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer

Abstract

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 (-{\alpha }_{\text{DW}}{N}^2)$) relative to CIMs ($\exp (-{\alpha }_{\text{CIM}}N)$) for fixed anneal times, on both the SK model and on 50%-edge-density MAX-CUT, where the coefficients ${\alpha }_{\text{CIM}}$ and ${\alpha }_{\text{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.

12 pages, 5 figures, 1 table (main text); 14 pages, 12 figures, 2 tables (supplementary)

References in corpus (24)

• Deep Learning with Coherent Nanophotonic Circuits
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Neuromorphic Silicon Photonic Networks
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Defining and detecting quantum speedup
• Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Large-scale Ising spin network based on degenerate optical parametric oscillators
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Intrinsic optimization using stochastic nanomagnets
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Speedup by Quantum Annealing
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
• A deceptive step towards quantum speedup detection
• Truncated Wigner function theory of coherent Ising machines based on degenerate optical parametric oscillator network
• Gaussian Optical Ising Machines
• Topological defect formation in 1D and 2D spin chains realized by network of optical parametric oscillators
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)

Cited by in corpus (92)

• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Heuristic Recurrent Algorithms for Photonic Ising Machines
• Nanophotonic spin-glass for realization of a coherent Ising machine
• Traffic Signal Optimization on a Square Lattice with Quantum Annealing
• Coherent and dissipative dynamics at quantum phase transitions
• Advances in silicon quantum photonics
• Noise-enhanced spatial-photonic Ising machine
• Coherent Ising machines -- Quantum optics and neural network perspectives
• Autonomous Probabilistic Coprocessing with Petaflips per Second
• Persistent coherent beating in coupled parametric oscillators
• Scalable spin-glass optical simulator
• Enhancing associative memory recall and storage capacity using confocal cavity QED
• Collective and synchronous dynamics of photonic spiking neurons
• Parallel Quantum Annealing
• A quantum annealer with fully programmable all-to-all coupling via Floquet engineering
• Large-scale Ising Emulation with Four-Body Interaction and All-to-All Connection
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Spectral Phase Transitions in Optical Parametric Oscillators
• Ising Machines' Dynamics and Regularization for Near-Optimal Large and Massive MIMO Detection
• Can nonlinear parametric oscillators solve random Ising models?
• A Ferroelectric Compute-in-Memory Annealer for Combinatorial Optimization Problems
• Theory of coupled parametric oscillators beyond coupled Ising spins
• Coherent Ising machines with error correction feedback
• All-optical scalable spatial coherent Ising machine
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
• Multidimensional hyperspin machine
• Antiferromagnetic spatial photonic Ising machine through optoelectronic correlation computing
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Wavelength-division multiplexing optical Ising simulator enabling fully programmable spin couplings and external magnetic fields
• Evaluating spintronics-compatible implementations of Ising machines
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Integrated probabilistic computer using voltage-controlled magnetic tunnel junctions as its entropy source
• Coherent dynamics in frustrated coupled parametric oscillators
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm
• Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Computational hardness of spin-glass problems with tile-planted solutions
• Hyperscaling in the coherent hyperspin machine
• Not-so-adiabatic quantum computation for the shortest vector problem
• Tuneable spin-glass optical simulator based on multiple light scattering
• Quantum-Inspired Hierarchy for Rank-Constrained Optimization
• Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
• Observing a Phase Transition in a Coherent Ising Machine
• Quantum Correlations in the Kerr Ising Model
• Energy landscapes of combinatorial optimization in Ising machines
• Discrete Polynomial Optimization with Coherent Networks of Condensates and Complex Coupling Switching
• Observation of Distinct Phase Transitions in a Nonlinear Optical Ising Machine
• On computational capabilities of Ising machines based on nonlinear oscillators,
• ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
• Solving the max-3-cut problem using synchronized dissipative networks
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Combinatorial optimization solving by coherent Ising machines based on spiking neural networks
• A Josephson Parametric Oscillator-Based Ising Machine
• Uplink MIMO Detection using Ising Machines: A Multi-Stage Ising Approach
• Effective implementation of $l_0$-Regularised Compressed Sensing with Chaotic-Amplitude-Controlled Coherent Ising Machines
• Mean-field Coherent Ising Machines with artificial Zeeman terms
• Qudit Machine Learning
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Programmable 200 GOPS Hopfield-inspired photonic Ising machine
• Benchmarking Quantum Computers: Towards a Standard Performance Evaluation Approach
• Highly Versatile FPGA-Implemented Cyber Coherent Ising Machine
• Frustration Elimination and Excited State Search in Coherent Ising Machines
• Phase-space simulations of feedback coherent Ising machines
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All
• Emergent Equilibrium in All-Optical Single Quantum-Trajectory Ising Machines
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• Quantum annealing in the NISQ era: railway conflict management
• An optical Ising spin glass simulator with tuneable short range couplings
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Analysis of the Hopfield Model with Discrete Coupling
• Requirements on bit resolution in optical Ising machine implementations
• Solving Large Break Minimization Problems in a Mirrored Double Round-robin Tournament Using Quantum Annealing
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Self-induced manipulation of biphoton entanglement in topologically distinct modes
• Minor embedding with Stuart-Landau oscillator networks
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization
• Hamiltonian formulations of centroid-based clustering
• Scalable almost-linear dynamical Ising machines
• Investigating Lipkin-Meshkov-Glick Model and Criticality-Enhanced Metrology in a Coherent Ising Machine
• Charge-Density-Wave Oscillator Networks for Solving Combinatorial Optimization Problems
• 2022 Roadmap on Neuromorphic Computing and Engineering
• Quantum batteries in coherent Ising machine
• Multi-tasking through quantum annealing
• Curve fitting on a quantum annealer for an advanced navigation method
• Observation of binary phase states of time-multiplexed degenerate optical parametric oscillator pulses generated using a nonlinear fiber Sagnac loop
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning