OIM: Oscillator-based Ising Machines for Solving Combinatorial Optimisation Problems

We present a new way to make Ising machines, i.e., using networks of coupled self-sustaining nonlinear oscillators. Our scheme is theoretically rooted in a novel result that establishes that the phase dynamics of coupled oscillator systems, under the influence of subharmonic injection locking, are governed by a Lyapunov function that is closely related to the Ising Hamiltonian of the coupling graph. As a result, the dynamics of such oscillator networks evolve naturally to local minima of the Lyapunov function. Two simple additional steps (i.e., adding noise, and turning subharmonic locking on and off smoothly) enable the network to find excellent solutions of Ising problems. We demonstrate our method on Ising versions of the MAX-CUT and graph colouring problems, showing that it improves on previously published results on several problems in the G benchmark set. Our scheme, which is amenable to realisation using many kinds of oscillators from different physical domains, is particularly well suited for CMOS IC implementation, offering significant practical advantages over previous techniques for making Ising machines. We present working hardware prototypes using CMOS electronic oscillators.

• Publication year

  2019

• Venue

  International Conference on Unconventional Computation and Natural Computation

• Publication date

  2019-03-17

• Fields of study

  Physics, Computer Science

• Identifiers
  DOI 10.1007/978-3-030-19311-9_19arXiv 1903.07163
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Enhancing the Solution Quality of Hardware Ising-Model Solver via Parallel Tempering

  2018cited by this paper
• Area Efficient Annealing Processor for Ising Model without Random Number Generator

  2018cited by this paper
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer

  2018cited by this paper
• A Time-Division Multiplexing Ising Machine on FPGAs

  2017cited by this paper
• A coherent Ising machine for 2000-node optimization problems

  2016cited by this paper
• A 20k-Spin Ising Chip to Solve Combinatorial Optimization Problems With CMOS Annealing

  2016influential reference
• A fully programmable 100-spin coherent Ising machine with all-to-all connections

  2016cited by this paper
• Efficient Analog Circuits for Boolean Satisfiability

  2016cited by this paper
• Stochastic p-bits for Invertible Logic

  2016cited by this paper
• An electromechanical Ising Hamiltonian

  2015cited by this paper
• Solving maximum cut problems by simulated annealing

  2015cited by this paper
• Design tools for oscillator-based computing systems

  2015cited by this paper
• What is the Computational Value of Finite Range Tunneling

  2015cited by this paper
• PHLOGON: PHase-based LOGic using Oscillatory Nano-systems

  2014cited by this paper
• Defining and detecting quantum speedup

  2014cited by this paper
• Network of time-multiplexed optical parametric oscillators as a coherent Ising machine

  2014cited by this paper
• Discrete optimization using quantum annealing on sparse Ising models

  2014influential reference
• Lyapunov function as potential function: A dynamical equivalence *

  2014cited by this paper
• Course in Theoretical Physics

  2013cited by this paper
• Graph Coloring Problems

  2013cited by this paper
• Ising formulations of many NP problems

  2013cited by this paper
• Analysis and design of sub-harmonically injection locked oscillators

  2012influential reference
• Functional Characterization of Water Transport and Cellular Localization of Three Aquaporin Paralogs in the Salmonid Intestine

  2011cited by this paper
• Quantum annealing with manufactured spins

  2011cited by this paper
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction

  2011cited by this paper
• The Ising model : teaching an old problem new tricks

  2010cited by this paper
• Gen-Adler: The generalized Adler's equation for injection locking analysis in oscillators

  2009influential reference
• Advanced Scatter Search for the Max-Cut Problem

  2009cited by this paper
• Experimental demonstration of a robust and scalable flux qubit

  2009cited by this paper
• PPV-HB: Harmonic Balance for Oscillator/PLL Phase Macromodels

  2006cited by this paper
• The Kuramoto model: A simple paradigm for synchronization phenomena

  2005cited by this paper
• Exact analytical equations for predicting nonlinear phase errors and jitter in ring oscillators

  2005cited by this paper
• Randomized heuristics for the Max-Cut problem

  2002cited by this paper
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

  2002cited by this paper
• Multi-Time PDEs for Dynamical System Analysis

  2001cited by this paper
• A Spectral Bundle Method for Semidefinite Programming

  1999cited by this paper
• Phase noise in oscillators: a unifying theory and numerical methods for characterisation

  1998cited by this paper
• Efficiently four-coloring planar graphs

  1996cited by this paper
• The general problem of the stability of motion

  1994cited by this paper
• Graph Coloring Problems

  1994cited by this paper
• Phase transitions in active rotator systems

  1986cited by this paper
• “Neural” computation of decisions in optimization problems

  1985cited by this paper
• Chemical Oscillations, Waves, and Turbulence

  1984cited by this paper
• On the computational complexity of Ising spin glass models

  1982cited by this paper
• Self-entrainment of a population of coupled non-linear oscillators

  1975cited by this paper
• Reducibility Among Combinatorial Problems

  1972influential reference
• Biological rhythms and the behavior of populations of coupled oscillators.

  1967cited by this paper
• History of the Lenz-Ising Model

  1967cited by this paper
• A Study of Locking Phenomena in Oscillators

  1946cited by this paper
• Beitrag zur Theorie des Ferromagnetismus

  1925cited by this paper

• SLAM: Extending the Reach of Ising Machine Advantage

  2026influential citation
• Neural Ising Machines via Unrolling and Zeroth-Order Training

  2026cites this paper
• Control of Oscillator Networks With Mean-Field Measurement: A Hybrid Open/Closed-Loop Approach

  2026cites this paper
• Programmable optoelectronic Ising machine for optimization of real-world problems

  2026cites this paper
• Overcoming quadratic hardware scaling for a fully connected digital oscillatory neural network

  2025cites this paper
• Higher-Order Neuromorphic Ising Machines - Autoencoders and Fowler-Nordheim Annealers are all you need for Scalability

  2025cites this paper
• MMGaP: Multi-User MIMO Detection and Precoding using GPU-assisted Physics-inspired Computation

  2025cites this paper
• Equalized Hyperspin Machine

  2025cites this paper
• Single photon coherent Ising machines for constrained optimization problems

  2025cites this paper
• GPU-Accelerated Simulated Oscillator Ising/Potts Machine Solving Combinatorial Optimization Problems

  2025influential citation
• Efficient optimization accelerator framework for multi-state spin Ising problems

  2025cites this paper
• A Programmable and Reconfigurable CMOS Analog Hopfield Network for NP-Hard Problems

  2025cites this paper
• The Digital Coupled Ring Oscillator Ising Machine

  2025cites this paper
• Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

  2025cites this paper
• Enabling fully connected probabilistic computing through a fast pipelined multi-operand adder

  2025cites this paper
• OscNet: Machine Learning on CMOS Oscillator Networks

  2025cites this paper
• DROID: discrete-time simulation for ring-oscillator-based Ising design

  2025cites this paper
• Spatial QUBO: Convolutional Formulation of Large-Scale Binary Optimization with Dense Interactions

  2025cites this paper
• DS-TIDE: Harnessing Dynamical Systems for Efficient Time-Independent Differential Equation Solving

  2025cites this paper
• Adaptive Ising machine based on phase-locking of an auto-oscillator to a bi-harmonic external driving with noise

  2025cites this paper
• A coupled-oscillator-based Ising chip for combinatorial optimization

  2025cites this paper
• A Variation-Tolerant Continuous-Time Ising Machine With eDRAM-Based Spin Interaction and Leaked Negative Feedback Annealing

  2025cites this paper
• Ising Machine by Dimensional Collapse of Nonlinear Polarization Oscillators.

  2025cites this paper
• Entropy-statistical approach to phase-locking detection of oscillations

  2025cites this paper
• Practical MU-MIMO Detection and LDPC Decoding Through Digital Annealing

  2025cites this paper
• Global Optimization Through Heterogeneous Oscillator Ising Machines

  2025cites this paper
• Training and synchronizing oscillator networks with Equilibrium Propagation

  2025cites this paper
• Efficient Optimization with Encoded Ising Models

  2025cites this paper
• Constraint-Aware Annealing for CMOS-Based Ising Machine LDPC Decoder

  2025cites this paper
• An SRAM-based Stochastic Number Generator for Stochastic Computing

  2025cites this paper
• Design Exploration of CMOS Coupled Oscillator-Based Ising Machines

  2025cites this paper
• All-to-All Connected Oscillator Ising Machines and Their Application as Associative Memory

  2025influential citation
• Charge-Density-Wave Oscillator Networks for Solving Combinatorial Optimization Problems

  2025cites this paper
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization.

  2025cites this paper
• Ising machine based on charge re-distribution

  2025cites this paper
• A Fully Symmetric Oscillator-Based CMOS Ising Machine Architecture With Successive Approximation Sampling and Power Efficient Solution Refinement

  2025cites this paper
• High-TMR SHNO-Based Ising Machines for CMOS-Compatible Unconventional Computing

  2025cites this paper
• Thermodynamics-Inspired Computing with Oscillatory Neural Networks for Inverse Matrix Computation

  2025cites this paper
• A Multi-Stage Potts Machine Based on Coupled CMOS Ring Oscillators

  2025influential citation
• Metrics for spin-based computing

  2025cites this paper
• Efficient Optimization Accelerator Framework for Multistate Ising Problems

  2025cites this paper
• Building a simple oscillator based Ising machine for research and education

  2024cites this paper
• Multi Digit Ising Mapping for Low Precision Ising Solvers

  2024cites this paper
• Thermodynamic Bayesian Inference

  2024cites this paper
• Impact of Frequency Heterogeneity on Mutually Synchronized Spatially Distributed 24 GHz PLLs

  2024cites this paper
• SACHI: A Stationarity-Aware, All-Digital, Near-Memory, Ising Architecture

  2024cites this paper
• Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling

  2024influential citation
• Voltage Controlled Oscillator based Ising Machine for Solving Combinatorial Optimization Problems

  2024cites this paper
• X-ResQ: Reverse Annealing for Quantum MIMO Detection with Flexible Parallelism

  2024cites this paper
• A scalable universal Ising machine based on interaction-centric storage and compute-in-memory

  2024cites this paper
• Natural Induction: Spontaneous Adaptive Organisation without Natural Selection

  2024cites this paper
• An Efficient Simulated Oscillator-Based Ising Machine on FPGAs

  2024influential citation
• A comparison of Oscillatory Ising Machines and Simulated Bifurcation Machines for Solving Maximum Cut Problems

  2024cites this paper
• Optimizing Reconfigurable Antenna MIMO Systems with Coherent Ising Machines

  2024cites this paper
• DS-GL: Advancing Graph Learning via Harnessing Nature’s Power within Scalable Dynamical Systems

  2024cites this paper
• A Review of Ising Machines Implemented in Conventional and Emerging Technologies

  2024cites this paper
• Extending Power of Nature from Binary to Real-Valued Graph Learning in Real World

  2024cites this paper
• Frequency tunable CMOS ring oscillator‐based Ising machine

  2024cites this paper
• Quantum annealing research at CMU: algorithms, hardware, applications

  2024cites this paper
• Noise-augmented chaotic Ising machines for combinatorial optimization and sampling

  2024cites this paper
• An FPGA-based Max-K-Cut Accelerator Exploiting Oscillator Synchronization Model

  2024influential citation
• High-Speed Phase-Based Computing

  2024influential citation
• Improved time complexity for spintronic oscillator ising machines compared to a popular classical optimization algorithm for the Max-Cut problem

  2024influential citation
• High Quality Circuit-Based 3-SAT Mappings for Oscillator Ising Machines

  2024cites this paper
• Oscillator-based optimization: design, emulation, and implementation

  2024cites this paper
• Hopfield vs Ising: A Comparison on the SoC FPAA

  2024cites this paper
• Entropy-statistical approach to phase-locking detection of pulse oscillations: application for the analysis of biosignal synchronization

  2024cites this paper
• Architectural Considerations for Scalable Analog Ising Machines

  2024cites this paper
• Utilizing Multi-Body Interactions in a CMOS-Based Ising Machine for LDPC Decoding

  2024influential citation
• ClassONN: Classification with Oscillatory Neural Networks Using the Kuramoto Model

  2024cites this paper
• A High-Performance Stochastic Simulated Bifurcation Ising Machine

  2024cites this paper
• Thermodynamic Algorithms for Quadratic Programming

  2024cites this paper
• Multi-objective brainstorm optimization algorithm based on Bayesian inference learning automaton for solving CVRP with time windows

  2024cites this paper
• Optimizing Configuration Selection in Reconfigurable-Antenna MIMO Systems: Physics-Inspired Heuristic Solvers

  2024cites this paper
• HETRI: Heterogeneous Ising Multiprocessing

  2024cites this paper
• Programming an Oscillator-Based Ising Machine with Memristive Coupling

  2024cites this paper
• SIMD-enabled Physics-inspired MIMO detector for Uplink Multi-user MIMO

  2024cites this paper
• Optimizing hybrid ferromagnetic metal–ferrimagnetic insulator spin-Hall nano-oscillators: A micromagnetic study

  2024cites this paper
• Multi-Phase Coupled CMOS Ring Oscillator Based Potts Machine

  2024influential citation
• A Quantum-Inspired Bilevel Optimization Algorithm for the First Responder Network Design Problem

  2024cites this paper
• A numerical model for time-multiplexed Ising machines based on delay-line oscillators

  2024cites this paper
• Phase-Binarized Dipole-Coupled Spin Hall Nano Oscillators (SHNOs) as Ising Machines

  2024influential citation
• Entropy-based detection of synchronization of pulse oscillators: a comparative analysis of entropic measures

  2024cites this paper
• Synchronization measurement based on Poincaré’s sphere

  2023cites this paper
• Micro/Nano Circuits and Systems Design and Design Automation: Challenges and Opportunities

  2023cites this paper
• Trip Planning Based on subQUBO Annealing

  2023cites this paper
• Oscillatory neural network learning for pattern recognition: an on-chip learning perspective and implementation

  2023influential citation
• Designing Ising machines with higher order spin interactions and their application in solving combinatorial optimization

  2023influential citation
• A Josephson Parametric Oscillator-Based Ising Machine

  2023cites this paper
• A Dynamical Systems Perspective on Discrete Optimization

  2023influential citation
• Self-contained relaxation-based dynamical Ising machines

  2023cites this paper
• Augmented Electronic Ising Machine as an Effective SAT Solver

  2023cites this paper
• Numerical simulation of probabilistic computing to NP-complete number theory problems

  2023cites this paper
• Beyond zeros and ones – analog computing in the twenty-first century

  2023cites this paper
• Uplink MIMO Detection Using Ising Machines: A Multi-Stage Ising Approach

  2023cites this paper
• Polychronous Oscillatory Cellular Neural Networks for Solving Graph Coloring Problems

  2023cites this paper
• Low-Rank Combinatorial Optimization and Statistical Learning by Spatial Photonic Ising Machine.

  2023cites this paper
• Superior Performance of Phase Binarized Oscillators (PBOs) Compared to Quantum Approximation Optimization Algorithm (QAOA) for Ising Computing (Max-Cut Problem)

  2023influential citation
• Spectral Network Principle for Frequency Synchronization in Repulsive Laser Networks

  2023cites this paper
• Efficient LDPC Decoding using Physical Computation

  2023cites this paper