An official website of the United States government
Abstract The rich non‐linear dynamics of the coupled oscillators (under second harmonic injection) can be leveraged to solve computationally hard problems in combinatorial optimization such as finding the ground state of the Ising Hamiltonian. While prior work on the stability of the so‐called Oscillator Ising Machines (OIMs) has used the linearization method, in this letter, the authors present a complementary method to analyze stability using the second‐order derivative test of the energy/cost function. The authors establish the equivalence between the two methods, thus augmenting the tool kit for the design and implementation of OIMs.
more »
« less
This content will become publicly available on October 1, 2026
General oscillator-based Ising-machine models with phase-amplitude dynamics and polynomial interactions
. We present an oscillator model with both phase and amplitude dynamics for oscillator-based Ising machines (OIMs). The model targets combinatorial optimization problems with polynomial cost functions of arbitrary order and addresses fundamental limitations of previous OIM models through a mathematically rigorous formulation with a well-defined energy function and corresponding dynamics. The model demonstrates monotonic energy decrease and reliable convergence to low-energy states. Empirical evaluations on 3-SAT problems show significant performance improvements over existing phase-amplitude models. Additionally, we propose a flexible, generalizable framework for designing higher-order oscillator interactions, from which we derive a practical method for oscillator binarization without compromising performance. This work strengthens both the theoretical foundation and practical applicability of oscillator-based Ising machines for complex optimization problems.
more »
« less
- PAR ID:
- 10657823
- Publisher / Repository:
- Phys. Rev. Applied
- Date Published:
- Journal Name:
- Physical Review Applied
- Volume:
- 24
- Issue:
- 4
- ISSN:
- 2331-7019
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we report new results on a novel Ising machine technology for solving combinatorial optimization problems using networks of coupled self-sustaining oscillators. Specifically, we present several working hardware prototypes using CMOS electronic oscillators, built on bread-boards/perfboards and PCBs, implementing Ising machines consisting of up to 240 spins with programmable couplings. We also report that, just by simulating the differential equations of such Ising machines of larger sizes, good solutions can be achieved easily on benchmark optimization problems, demonstrating the effectiveness of oscillator-based Ising machines.more » « less
-
Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Booleank-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.more » « less
-
Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms.more » « less
-
Abstract The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, prior work on designing dynamical systems as Ising machines has primarily considered quadratic interactions among the nodes. Dynamical systems and models considering higher order interactions among the Ising spins remain largely unexplored, particularly for applications in computing. Therefore, in this work, we propose Ising spin-based dynamical systems that consider higher order (> 2) interactions among the Ising spins, which subsequently, enables us to develop computational models to directly solve many COPs that entail such higher order interactions (i.e., COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K ≥ 4) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired ‘toolbox’ for solving COPs.more » « less
