Source-linked AI summary
OIM: Oscillator-based Ising Machines for Solving Combinatorial Optimisation Problems
Tianshi Wang, Jaijeet Roychowdhury
TL;DR
The paper addresses how to build practical hardware for difficult Ising optimisation problems. It develops coupled oscillator networks whose SHIL-controlled phase dynamics follow an Ising-related Lyapunov function, then evaluates them on MAX-CUT and graph colouring. The method improves previously published results on several G-set problems and supports CMOS prototypes, though stochastic runs do not guarantee global optima.
Problem
General Ising optimisation is difficult, motivating specialised machines that can minimise Hamiltonians for problems such as MAX-CUT and graph colouring.
Method
The paper uses coupled self-sustaining oscillators with subharmonic injection locking, noise, and smoothly controlled locking to drive binary phases toward Ising solutions.
Results
The method finds better-than-previously-published results for 17 of 54 G-set MAX-CUT problems and produces working CMOS oscillator prototypes.
Takeaways & Limitations
Oscillator-based Ising machines provide a classical approach compatible with conventional CMOS electronics and practical hardware implementation.
Takeaways & Limitations
Random initial conditions and stochastic dynamics provide no guarantee that every run reaches the global optimum.
Abstract
from arXiv · showhide
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 sub-harmonic 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 sub-harmonic 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.
1 Introduction
The paper introduces oscillator-based Ising machines as a classical alternative for difficult combinatorial optimisation, demonstrating strong MAX-CUT results and practical CMOS prototypes.
- The method also matches the best-known previous results on many of the 54 benchmark problems.
- The approach uses coupled self-sustaining oscillators to solve Ising formulations of combinatorial optimisation problems.It is implemented as a purely classical scheme rather than relying on quantum phenomena or novel nano-devices.
- 17 of 54 standard G-set MAX-CUT problems receive better results than seem to have been previously published.
- Small prototypes using up to 32 CMOS oscillators function perfectly on breadboards.The paper presents these prototypes as evidence that practical hardware implementations can be built easily.
- Conventional CMOS electronics offer scalability, miniaturisability, established design processes, and very low-power operation.
2 The Ising problem and existing Ising machine approaches
The Ising model encodes optimisation problems as spin assignments that minimise a weighted Hamiltonian, motivating specialised hardware despite the problem’s general difficulty.
- The Ising model assigns each graph vertex a binary spin ±1 and seeks the assignment minimising a graph-weighted scalar Hamiltonian.
- Solving the general Ising problem is very difficult, while many hard optimisation problems can be mapped to it through suitable coefficients.
- Ising machines directly minimise the Hamiltonian, making them attractive for difficult optimisation problems.
- D-Wave machines use Josephson junctions and require temperatures below 80mK, creating a large footprint for cooling.
- The Coherent Ising Machine represents spins with time-multiplexed optical parametric oscillators coupled through FPGA-based measurement and feedback over long fibres.The passage notes that miniaturisation and integration remain unclear because of the long fibres.
3 Oscillator-based Ising Machines
Coupled self-sustaining oscillators can implement Ising machines because subharmonic injection locking binarises phases while the network’s Lyapunov dynamics track the Ising objective. The method addresses analog-phase failure, tolerates moderate variability, and supports practical oscillator hardware.
- 3.1 Injection locking in oscillators: Subharmonic injection locking creates two stable phase-locked states, binarising each oscillator’s phase for Ising computation.A perturbation near twice the oscillator frequency produces a π-periodic phase response with stable locked states.
- 3.2 Global Lyapunov function: The coupled-network phase dynamics are governed by a global Lyapunov function that the system naturally minimises over time.The model extends the Gen-Adler equation to coupled oscillators and yields an energy-like objective.
- 3.2 Global Lyapunov function: Without SHIL, networks commonly settle at analog phases, so rounding them produces very poor Ising solutions compared with the proposed scheme.SHIL changes the energy landscape and dynamics rather than merely post-processing continuous phases.
- 3.3 Network of coupled oscillators under SHIL and its global Lyapunov function: At binary phase values, choosing K = 1/2 makes the Lyapunov function equivalent to the Ising Hamiltonian up to a constant offset.The mapping is φi = 0 to si = +1 and φi = π to si = −1.
- 3.3 Network of coupled oscillators under SHIL and its global Lyapunov function: Noise and smoothly turning SHIL on and off help the network escape local minima and find better Ising solutions, although global optimality is not guaranteed.The Lyapunov function generally has many local minima.
- 3.4 Coupled oscillator networks with frequency variations: Small frequency variability mainly perturbs minima, while larger variability can eliminate minima; increasing K reduces its effect, and calibration can remove frequency spread.The variability contribution is a linear tilt of an otherwise essentially unchanged energy landscape.
4 Examples
The paper evaluates oscillator-based Ising machines on MAX-CUT, hardware prototypes, benchmark instances, and graph colouring. Across these examples, simulations and CMOS implementations produce optimal or low-energy solutions, while larger benchmarks show strong solution quality and encouraging scaling behavior.
- Small MAX-CUT Problems: The oscillator-based machine maps MAX-CUT to Ising minimisation, where minimising the Hamiltonian maximises the graph cut.Vertices are divided between two sets and represented by spins ±1; coupling coefficients are chosen from edge weights.
- Small MAX-CUT Problems: For the size-8 cubic MAX-CUT example, deterministic and stochastic simulations both produced global optimal spin assignments.The reported solutions are {+1,−1,+1,−1,−1,+1,−1,+1} and {−1,+1,+1,−1,+1,−1,−1,+1}.
- Small MAX-CUT Problems: 20µs: SPICE-level simulations synchronised eight coupled oscillators and reliably returned optimal solutions for the size-8 MAX-CUT problem.The oscillators were tuned to 5MHz, corresponding to about 100 cycles before synchronisation.
- Small MAX-CUT Problems: The size-32 CMOS prototype achieved energies below zero and sometimes reached the global minimum across hardware runs.Because random solutions average around zero energy for random coupling polarities, the measured results indicate nonrandom optimisation performance.
- MAX-CUT Benchmark Problems: 38 of 54 G-set problems reached best-known cut values, including 17 with results better than previously reported literature values.The experiments used one annealing schedule and 200 random instances per problem, with sizes ranging from 800 to 3000.
- MAX-CUT Benchmark Problems: The preliminary scaling study found that solution values settled at an almost constant speed as problem size increased, although equal-time global convergence was not established.The authors state that hardware size scales linearly with the number of spins and may not require much more time to reach a solution.
- A Graph Colouring Example: For graph colouring, the Hamiltonian reaches zero exactly when every vertex receives one colour and adjacent vertices do not share a colour.Four spins encode each vertex’s colour choice, with one +1 and three −1 values required per vertex.
- A Graph Colouring Example: Subharmonic injection locking binarises oscillator phases, while noise and smoothly controlled locking help the network find excellent Ising solutions.The scheme is supported by theoretical analysis, simulations, and CMOS oscillator hardware prototypes.
Appendix A. Phase-based Macromodels of Oscillators and Oscillator-based Ising Machines
The appendix derives phase macromodels for self-sustaining oscillators from low-level oscillator equations and uses them to model oscillator-based Ising machines. It establishes how periodic perturbations, subharmonic locking, coupling, noise, and Lyapunov dynamics enter the model.
- Oscillator modeling: A self-sustaining oscillator is modeled as a differential-algebraic system with a nonconstant periodic solution.
- Phase response: The Perturbation Projection Vector captures an oscillator’s phase response to small external inputs and can be derived analytically or numerically from its equations.
- Phase macromodel: Averaging the multi-time formulation over the fast oscillation produces a one-dimensional approximation for the slowly evolving phase.
- Injection locking: Periodic perturbations determine the phase-coupling function: ordinary waveform coupling recovers Adler’s equation, while second-order perturbations yield π-periodic dynamics.
- Ising-machine dynamics: In the oscillator-based Ising machine, inter-oscillator, reference, and second-order SYNC perturbations jointly determine each oscillator’s phase dynamics.
- Noise analysis: Noise is modeled as Gaussian white noise in oscillator frequencies, and its magnitude corresponds to the statistical-mechanical noise scale kT.
- Noise analysis: Because the energy difference between configurations is proportional to coupling strength, increasing coupling makes higher-energy states less probable and favors lower-energy states.
- Lyapunov analysis: Under symmetric coupling and the stated skew-symmetry assumption, the phase dynamics admit a global Lyapunov function.
Appendix D. MATLAB R ⃝SDE Simulation Code for MAX-CUT Problems
The appendix provides MATLAB SDE code for simulating MAX-CUT dynamics with oscillator phases, coupling terms, and two alternative nonlinear phase interactions.
- Simulation dynamics: The simulation computes each oscillator’s phase derivative from a self term and coupling to the other oscillators.
- Visualization: The code plots oscillator phases over time in cycles, with the vertical axis expressed in units of π.
- Alternative interaction: A second simulation replaces sine interactions with tanh-transformed sine terms for both self and coupling contributions.
- Visualization: The plotting configuration enables grid and box display for the simulated phase trajectories.