Direct comparison of stochastic-driven nonlinear dynamical systems for combinatorial optimization

Junpeng Hou, Amin Barzegar, Helmut G. Katzgraber · 2025

Read Direct comparison of stochastic-driven nonlinear dynamical systems for combinatorial optimization by Junpeng Hou, Amin Barzegar, Helmut G. Katzgraber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15427.txt.

Introduction

Junpeng Hou, Amin Barzegar, and Helmut Katzgraber published a paper in 2025 that tests physics-based solvers for hard optimization problems side by side. Many such problems can be cast as a search for the ground state of an Ising model. New tools, from quantum simulators to coherent Ising machines, promise faster answers. The team sets several of these dynamical solvers head to head.

The set of rivals includes the Ising machines just named, a gain-dissipative method, simulated bifurcation machines, and Hopfield networks. All of them run on one software stack, on random problems with planted solutions, with simulated annealing as the baseline. The study also tests how integration choices and graph wiring change the scores. The authors give a broad view of this new family of solvers.

Catalog record

CREATORJunpeng Hou, Amin Barzegar, Helmut G. Katzgraber
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-15427

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Direct comparison of stochastic-driven nonlinear dynamical systems for combinatorial optimization Junpeng Hou, Amin Barzegar, Helmut G. Katzgraber Abstract Combinatorial optimization problems are ubiquitous in industrial applications. However, finding optimal or close-to-optimal solutions can often be extremely hard. Because some of these problems can be mapped to the ground-state search of the Ising model, tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms such as quantum simulators and coherent Ising machines to tackle hard optimization problems. Here, we examine and benchmark several physics-inspired optimization algorithms, including coherent Ising machines, gain-dissipative algorithms, simulated bifurcation machines, and Hopfield neural networks, which we collectively refer to as stochastic-driven nonlinear dynamical systems. Most importantly, we benchmark these algorithms against random Ising problems with planted solutions and compare them to simulated annealing as a baseline leveraging the same software stack for all solvers. We further study how different numerical integration techniques and graph connectivity affect performance. This work provides an overview of a diverse set of new optimization paradigms. I Introduction The ever-growing need for computing has surged over the past few decades as we are facing unprecedentedly complex problems in modern society, industry, and science. Among them, combinatorial optimization problems stand out for being notoriously difficult to solve as a result of the so-called combinatorial explosion [ 1 ] , meaning that their solution space grows exponentially with increasing number of variables. Consequently, many combinatorial optimization problems are known to be nondeterministic polynomial (NP)-hard or NP-complete. Naturally, these problems have attracted considerable attention from various fields such as computational science [ 2 ] and operations research [ 3 ] . From a physical perspective, it is known that many combinatorial optimization problems can be mapped to the problem of finding the ground states of the Ising model, and such mapping can be achieved using polynomial resources [ 4 ] . Note, however, that the overhead can be sizable in some cases. Several examples, such as the mapping for the traveling salesperson problem, the knapsack problem, or maximum independent set problem can be found in Ref. [ 5 ] . Moreover, the binary variables \sigma_{l}=\pm 1 can be modeled through a plethora of physical systems including classical and quantum spins [ 6 , 7 , 8 , 9 , 10 , 11 , 12 ] , optical fields [ 13 , 14 , 15 , 16 , 17 ] , solid-state circuits [ 18 , 19 , 20 , 21 , 22 , 23 ] , and nonequilibrium condensates [ 24 , 25 ] . These algorithms are heuristics that start from a random initial state. The probability to find the ground state (or the lowest-energy state) depends highly on whether or not the system’s dynamics can escape from local minima effectively. The energy landscape of many combinatorial optimization problems is generally rather rough with exponentially many metastable states [ 12 ] . Therefore, the resources required by heuristics to reach the low-lying states scale nonpolynomially with the problem size. More recently, various new computing paradigms have been proposed and realized in different physical systems to more effectively traverse energy landscapes by allowing the original binary variable \sigma_{l}=\pm 1 to relax to a continuous variable of either real x_{l}\in\mathbb{R} or complex \Psi_{l}\in\mathbb{C} type. In these algorithms, optimization is achieved by mapping local minima to fixed points through bifurcation processes which are usually created by tuning a set of gain/dissipative strengths (or equivalently, proper driven effects) in the system [ 26 ] . Throughout this work, we refer to these physical systems as stochastic-driven nonlinear dynamical systems (SDNDSs), because the name highlights their three common key features, namely, stochastic noise terms, driven or gain/dissipative effects, and nonlinearity. In fact, similar ideas can be traced back to early work on Hopfield neural networks in which the continuous variable of each neuron is mapped to a binary variable via an activation function [ 27 ] . It has also been shown that reducing the gain or the steepness of the activation function could lead to an exponential decrease in the number of local minima, and therefore, improve the solution quality [ 28 , 29 , 30 ] . Despite early skepticism [ 31 ] , more recent studies have argued that such algorithms might outperform state-of-the-art heuristics or perform equally well at the very least [ 32 , 12 ] . To address this outstanding debate and to gain a more comprehensive understanding of SDNDSs, in this work we examine some representative systems and algorithms using the same code base, including coherent Ising machines (CIMs), gain-dissipative (GD) platforms, oscillator-based Ising machines (OIM), simulated bifurcation machines (SBM), as well as classical Hopfield neural networks. We benchmark these algorithms using Ising problems with planted solutions and compare their performances to that of simulated annealing (SA) [ 6 ] , which is currently a popular and efficient heuristic for binary combinatorial optimization problems [ 33 ] . Furthermore, we conduct a range of experiments to deeper investigate the performance of these heuristics. First, because the dynamical systems studied here are simulated by numerically solving the associated equations of motion (EoM) which are usually ordinary differential equations (ODEs), we study how using different numerical integration methods—e.g., Runge–Kutta (RK)—affect performance. To better understand how graph connectivity affects performance, we systematically dilute a fully-connected Sherrington-Kirkpatrick model [ 34 ] to a Viana-Bray model [ 35 ] . To this end, we compare the performance of SA against the SBM. Table 1: List of different stochastic-driven nonlinear dynamical systems studied in this work. The artificial spin is denoted by either x_{l} (real field) or \Psi_{l} (complex field). Other common parameters include the pumping/driving strength \alpha , global Ising coupling \beta , and the nonlinear activation function \phi(\bullet) . For other model-specific parameters, please refer to the relevant subsections in Sec. II . Algorithm Equations of motion OPO-CIM \dot{x}_{l}=\alpha x_{l}-\frac{2}{3}x_{l}^{3}+\beta\sum\limits_{m}J_{lm}x_{m}+g_{l} Sim-CIM x_{l}\leftarrow\phi\left((\alpha+1)x_{l}+\beta\sum\limits_{m}J_{lm}x_{m}\right)+g_{l} OEO-CIM x_{l}\leftarrow\cos^{2}(\alpha x_{l}+\beta\sum\limits_{m}J_{lm}x_{m}-\frac{\pi}{4})+g_{l}-\frac{1}{2} OIM \dot{x}_{l}=-\alpha\sin(2x_{l})-\beta\sum\limits_{m}J_{lm}\sin(x_{l}-x_{m})+g_{l} Hopfield \dot{x}_{l}=-\alpha x_{l}+\beta\sum\limits_{m}J_{lm}\phi\left(x_{m}\right)+g_{l} GD \begin{cases}\dot{\Psi}_{l}=\Psi_{l}\left(\alpha_{l}-\alpha_{c0}-|\Psi_{l}|^{2}\right)\\ \hskip 22.76228pt+\sum\limits_{m}\beta_{lm}K_{lm}\Psi_{m}+\sum\limits_{q=1}^{2}h_{ql}\Psi_{l}^{*}+g_{l},\\ \dot{\alpha}_{l}=\epsilon\left(\rho_{\text{th}}-|\Psi_{l}|^{2}\right),\vskip 2.84526pt\\ \dot{K}_{lm}=\epsilon^{\prime}\left(J_{lm}-\beta_{lm}K_{lm}\right)\end{cases} SBM \begin{cases}\dot{x}_{l}=\Delta y_{l},\vskip 5.69054pt\\ \dot{y}_{l}=-\left(Kx_{l}^{2}-\alpha(t)+\Delta\right)x_{l}+\beta\sum\limits_{m}J_{lm}x_{m}\end{cases} II Overview of physical models In this section, we give a brief overview of the SDNDSs studied. We present the underlying physics of these algorithms and make comparisons between them. Besides the recently proposed SDNDSs, such as different Ising machines and gain-dissipative methods, we also discuss the Hopfield neural network, which is intrinsically a nonlinear dynamical system. For the convenience of the reader, we have summarized all the SDNDSs studied here in Table 1 . Throughout this work, we adopt a consistent notation for the corresponding EoMs. All the SDNDSs are designed to optimize Ising-like Hamiltonians (which are related to quadratic-unconstrained binary optimization problems) given by the following Hamiltonian: H=-\frac{1}{2}\sum_{l,m}J_{lm}\sigma_{l}\sigma_{m}-\sum_{l}h_{l}\sigma_{l}\,. (1) Here, the spin-spin interaction matrix J is self-adjoint, namely, J^{*}_{lm}=J_{ml} (because Hamiltonian dynamics are hermitian) and h_{l} is a real onsite magnetic field. For practical purposes, we assume that the interaction matrix is real and therefore symmetric. Moreover, without loss of generality, we consider only the Ising model with no magnetic field, i.e. h_{l}=0 , because an N -spin Ising model with a magnetic field can be mapped to an (N+1) -spin

Read the complete text