betaFeedback

WorksEngineering

Computing with Coupled Oscillator Networks: Optimization, Memory, and Modern AI Primitives

Abstract

We explore how synchronization in coupled oscillator networks may be employed to perform a variety of computing tasks. These systems are becoming more attractive as an alternative to conventional digital computers due to the increasing energy demands of the latter, particularly for large-scale problems in machine learning and artificial intelligence. The ubiquity of coupled oscillator networks means that oscillator-based computing can be thought of as a universal computing paradigm encompassing systems with a diversity of physical realizations, e.g. as analog circuits, neurological systems, spintronic systems. The bridge between the dynamics of coupled oscillator networks and computational primitives they implement is the Ising model, which originates in statistical physics, and when applied to oscillator networks, explains the emergence of globally complex and disordered synchronization patterns from local interactions in the network. We discuss the application of coupled oscillator networks to three fundamental computing operations. First, oscillator networks as specialized hardware solvers of NP-hard combinatorial optimization problems, with the solution encoded in the synchrony patterns. Second, oscillator networks as associative memory systems, enabling storage and retrieval of data represented through phases of oscillations. Finally, oscillator networks as a dynamical implementation of attention, with synchronization providing the mechanism for the alignment of keys to queries. The ability of oscillator networks to implement these computational primitives paves the way for novel realizations of intelligent systems through a variety of physical substrates.

Synchronization of oscillations in networks of interacting components occurs in countless examples of systems in biology, physics, and engineering [1, 2, 3]. Often, synchronous oscillations play a crucial functional role in the settings they emerge from, e.g. carefully choreographed electrical activity of pacemaker cells in cardiac tissue regulates heart rhythm, and animal locomotion is driven by precisely timed phase differences in oscillating nerve cells that control gait (cf. [4], [5]). Though these phenomena are numerous and diverse, they are governed by a set of universal mathematical principles, which capture how patterns of synchrony arise from the complex interplay between the dynamics, local interactions, and network interconnection structure of the system. In this article, we show how these mathematical models also inform the design of oscillator-based computers. Specifically, by emulating neural oscillations underlying human cognition and learning, coupled oscillator networks can perform computing operations that form the basis of artificial intelligence models, eventually enabling the construction of efficient and intelligent devices.

The hegemonic paradigm of computation today is digital, with information encoded through binary-valued variables (called bits), and computation carried out by sequentially performing logical or arithmetic operations on them. Composing these operations in the correct manner, combined with the ability to store and retrieve digitally encoded data, allows digital computers to perform the extremely complex calculations necessary for the modern information age. Although the foundations for this approach were established as early as the 1940s, it nonetheless continues to be followed by nearly all modern-day computers. Two factors explain its persistence. First, the information encoding scheme and fundamental computational primitives are agnostic to hardware implementation. This provides for a theory of computing abstracted away from problems of physics and engineering, as well as the flexibility to translate digital computing architectures to new devices as better technology becomes available, e.g. with transistors and magnetic storage replacing vacuum tubes and punch cards. Second, advances in semiconductor manufacturing in the twentieth century allowed digital computers to continually scale up and meet the increasing computational demands of the last sixty years.

However, digital computing suffers from a number of limitations that are becoming more acute today. Some are theoretical, such as limits on the scalability of digital algorithms established by computational complexity theory. Many of the problems relevant to cryptography, operations research, and data analysis are NP-hard and thus large instances of these problems remain intractable on digital computers. Other limitations are physical in nature. Moore’s law, the observation that the number of transistors on an integrated circuit doubles every two years, began to saturate in the 2010s, while at the same time the growth of AI models – whose parameter counts now exceed the hundreds of billions – is leading to concerns over their increasing energy use.

Despite this, usage of AI models continues to proliferate, due to their remarkable success on reasoning tasks, natural language processing, and computer vision. Such models are often inspired by neurobiological principles. Artificial neural networks are loosely based on how biological neurons send and receive signals through synaptic connections, and many neural network architectures, such as the Hopfield model [6, 7] and the Boltzmann machine [8], analogize models of cognition in the human brain. Nevertheless, the human brain consumes a fraction of the energy required by computers running state-of-the-art models. One reason is the physical mechanism carrying out the computation: AI models run on digital hardware, whereas the human brain is fundamentally analog. Thus, to the extent that they reproduce processes observed in the human brain, they are merely simulating them and are unable to attain the efficiency of the human brain.

This has spurred the search for alternatives to digital computing that are biologically plausible. A growing body of evidence in the neuroscientific literature suggests that many cognitive processes are guided by oscillatory activity in the human brain [9, 10, 11, 12, 13]. Replicating these oscillations in engineered systems may offer a path to building intelligent computing devices. While this is an active area of research, these ideas are also faithful to the aspirations behind many classical brain-inspired architectures such as the Hopfield model, or Boltzmann machines, whose physical operation, when realized through synchronizing oscillator networks, is closer to the processes they intend to capture in the human brain.

Here, we review a paradigm for computing using oscillator networks, where the information encoding scheme is analog, and utilizes the phase of an oscillation. The mechanism that drives computation is the dynamics of the network system, along which phases evolve continuously in time. The ubiquity of oscillator networks in both naturally occurring and engineered settings means that, similar to digital computing, these devices may be realized through a number of physical substrates [14, 15, 16]. Oscillator networks offer a number of advantages over conventional digital computers. First, certain realizations of analog computers achieve greater energy efficiency than digital computers. Second, because information is analog and evolves continuously in time, rather than digital and taking place in discrete increments, these devices are not subject to the same theoretical limitations imposed by computational complexity theory on digital computers.

Oscillator-Based Computing: Then and Now

While digital computers based on the von Neumann architecture are the predominant approach to computing today, analog computing has an equally long history. In fact many of the predecessors to modern-day computers were special-purpose analog devices, for example the tide-predicting machine built by Sir William Thomson which used rotational components to represent the phases of lunar and solar tidal cycles [S1]. Even in the early days of digital computing it was recognized that oscillator-based computers may offer advantages in terms of speed and energy efficiency, with von Neumann himself proposing to replace vacuum tubes with nonlinear electrical components whose oscillatory phases represent bits [S2], [S3]. An example of such a device is the parametron which was used to construct the MUSASINO-1 in 1957 [S4].

Classical examples of oscillator-based computers

Figure S1. Classical examples of oscillator-based computers. (Left) Thomson’s tide-predicting machine (Right) MUSASINO-1 parametron computer

Modern examples of oscillator-based computers

Figure S2. Modern examples of oscillator-based computers (Left) Spin torque oscillator [S11] (Right) Computer based on optical parametric oscillators [S13]

In recent years there has been a resurgence of interest in oscillator-based computers to bypass the limitations of digital computers. Such devices are capable of implementing computational primitives such as solving combinatorial optimization problems, or implementing associative memory, and are realized through a variety of physical mechanisms, including

  1. Conventional electronics: analog circuits such as LC tank circuits [S5] or relaxation oscillators [S6]

  1. Superconducting Josephson junctions: devices using superconducting circuit elements with oscillating voltages [S7], [S8]

  1. Spintronic oscillators: devices which utilize the precession of magnetic moments in materials, such as spin-torque oscillators and spin Hall nano-oscillators [S9]–[S11]

  1. Optoelectronic oscillators: devices such as degenerate optical parametric oscillators (DOPOs), where oscillations are generated using coupled lasers [S12], [S13]

  1. Electromechanical oscillators: devices built from oscillating microelectromechanical (MEMS) or nanoelectromechanical (NEMS) systems [S14]

This is not to say that oscillator-based computing comes without tradeoffs, but rather to motivate the need for a new theory of oscillator-based computing to systematically explore them. Such a theory would consist of the following elements:

  1. An abstract framework for oscillator-based computing expressed independently of any physical realization, within which one can develop computing architectures and reason about their capabilities and limitations.

  1. A set of mathematical tools to relate the physics of real-world oscillatory systems to a simplified and universal representation in terms of the phases alone, allowing computing architectures developed within the aforementioned framework to be implemented on that particular platform.

In this survey we focus mainly on the former, though the latter is equally interesting and crucial to the practical implementation of oscillator-based computers (and we believe it can be addressed using phase reduction theory, though many open questions remain, see Sidebar: “Phase Reductions of Oscillators in Neuroscience, Electronics, and Physics”).

Our approach, illustrated in Figure 1, exploits the fact that many fundamental operations in computing are expressible in terms of minimizing an energy function related to the Ising Hamiltonian in models of spin glasses. Since similar energy functions also characterize the synchrony patterns exhibited by coupled oscillator networks, physical realizations of these networks be used as analog computers implementing those operations. We focus on three computing primitives: (1) coupled oscillator networks as solvers of combinatorial optimization problems, (2) coupled oscillator networks as associative memory systems, which in turn can be used for pattern recognition and generative modeling, and (3) oscillator-based implementations of the attention mechanism.

Overview of relationships between various concepts introduced in this survey

Figure 1. Overview of relationships between various concepts introduced in this survey. Phase reduction theory connects mathematical descriptions of a variety of physical realizations of oscillator networks to universal coupled phase oscillator models. The Ising model provides a bridge between coupled oscillator networks and their computing capabilities.

The Ising Model

We begin by reviewing the Ising model from a mathematical perspective (we refer the reader to [17, 18, 19, 20] for an introduction to spin-glass models, including the Ising model, and their applications to physics). Though it originates in statistical mechanics, and was traditionally proposed to explain the magnetic properties of materials, it has seen wide-ranging applications in chemistry, materials science, neuroscience, and machine learning, and is better understood as a general framework to model systems with both cooperative and competitive local interactions and the global order (or disorder) that emerges from them. The connection between the Ising model and certain fundamental operations in computing enables it to serve as a bridge between coupled oscillator networks and the computational primitives they implement.

Let G=(V,E)\mathcal{G} = (\mathcal{V}, \mathcal{E}) be a graph with NN nodes and signed adjacency matrix J∈RN×NJ \in\mathbb{R}^{N \times N}. Here, nodes represent individual agents, and edges represent the interactions between them. For each node, i∈{1,2,…,N}i \in\{1, 2, \ldots, N\}, we assign a spin denoted by si∈{−1,1}s_i \in\{-1, 1\}. The vector of spins s=(s1,…,sN)s = (s_1, \ldots, s_N) is called a spin configuration, to which we associate an energy given by the value of the Ising Hamiltonian,

H(s)=−12∑i=1N∑j=1NJijsisj−∑i=1Nhisi,(1)H(s) = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} J_{ij}s_i s_j - \sum_{i=1}^{N} h_i s_i, \tag*{(1)}

where h∈RNh \in\mathbb{R}^N is called the external field. We seek to understand the ordering of spin configurations, i.e. the regularity in the alignment of spins in the network (cf. Figure 2 for examples of types of ordering of spin configurations). Systems having spin configurations without any structure or regularity are called disordered. As we show next, the ordering of observed states is determined by the properties of low energy states.

Types of ordering of spin configurations

Figure 2. Types of ordering of spin configurations. Spins are aligned in the same direction in a ferromagnet, aligned in alternating directions in an antiferromagnet, and disordered in a spin glass.

In typical applications, the state occupied by the system is assigned randomly according to the Boltzmann distribution,

p(s)=1Zβexp⁡(−βH(s)).(2)p(s) = \frac{1}{Z_\beta}\exp(-\beta H(s)). \tag*{(2)}

The parameter β≥0\beta\ge0 is called the inverse temperature, and ZβZ_\beta is a normalization constant Zβ=∑s∈{−1,1}e−βH(s)Z_\beta= \sum_{s \in\{-1,1\}} e^{-\beta H(s)}, called the partition function. The likelihood of observing the state ss varies inversely with its energy H(s)H(s), biasing the system toward low energy states. The parameter β\beta determines the level of bias: in the high-temperature limit (β→0+\beta\to0^+), the Boltzmann distribution converges to the uniform distribution, and the spins are almost always disordered. In the low temperature limit (β→∞\beta\to\infty), the distribution concentrates around the global minimizers of (1), called ground states.

To determine the properties of low energy states, it is useful to consider the local interaction energies, −Jijsisj-J_{ij}s_i s_j, between individual pairs of nodes. In the absence of an external field, the Ising Hamiltonian is simply the sum of the local interaction energies. There are two types of interactions, distinguished by the sign of the corresponding edge: if Jij>0J_{ij} > 0, the interaction along (i,j)(i,j) is called ferromagnetic, in which case the local energy is minimized whenever si=sjs_i = s_j. On the other hand, if Jij<0J_{ij} < 0, the interaction is called antiferromagnetic and the local energy is instead minimized when si≠sjs_i \ne s_j. The external field adds an additional bias to each spin: if hi>0h_i > 0 (resp. hi<0h_i < 0) then the ith node is biased toward si=1s_i = 1 (resp. si=−1s_i = -1).

In general, the relationship between the global regularity of spin configurations and local interactions in the network is nontrivial. An important property of many networks is frustration, where no spin configuration exists that simultaneously minimizes all the local interaction energies (cf. Figure 3). One observes a variety of complex behaviors in these systems, including distinct phases with abrupt temperature-dependent phase transitions, and the emergence of spontaneous order. The Ising model is used as a simplified model of a spin glass, a class of magnetic materials exhibiting disorder or irregularity in the alignment of spins even at low temperatures.

Example of a frustrated network with antiferromagnetic interactions

Figure 3. Example of a frustrated network with antiferromagnetic interactions (depicted by dashed lines) between nodes, where for any spin configuration there exists a pair of adjacent nodes with aligned spins.

The Ising model can be generalized to allow spins represented as unit vectors on the (d−1)(d - 1)-sphere, zi∈Sd−1z_i \in S^{d-1} where Sd−1={zi∈Rd∣∥zi∥=1}S^{d-1} = \{z_i \in\mathbb{R}^d \mid\lVert z_i\rVert= 1\} (we denote vector-valued spins by the letter zz to avoid confusion with scalar-valued spins). This model is called the dd-vector model, and the Hamiltonian is

H(z)=−12∑i=1N∑j=1NJijziTzj−∑i=1NhiTzi.(3)H(z) = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}z_i^{\mathsf{T}}z_j-\sum_{i=1}^{N}h_i^{\mathsf{T}}z_i. \tag*{(3)}

When d=1d = 1, (3) reduces to the classical Ising model. Higher-dimensional models exhibit similarly complex behavior and, as we show later, also serve an important role in understanding the attention mechanism.

The Ising Model and Coupled Oscillator Networks

We now discuss the relationship between the Ising model and synchrony patterns exhibited by coupled oscillator networks. Instead of a spin, we associate each node i∈{1,2,…,N}i \in\{1,2,\ldots,N\} to a phase ϕi∈[0,2π]\phi_i \in[0,2\pi], which denotes the phase shift of its oscillation relative to a fixed reference (cf. Figure 4). We say that two nodes are phase synchronized if they have the same phase. Phase synchronization of oscillators in a network admits a similar mathematical description as the alignment of binary-valued spins in the Ising model. This connection may be exploited to describe synchronization patterns via energy functions, analogous

Waveforms and coupled oscillator network

Figure 4. (Left) The blue waveform has phase shift ϕ\phi relative to the reference waveform depicted in black. (Right) Network where each node is associated to a phase shifted oscillation, depicted in blue, relative to the uniform reference in black.

to (1), that encode the tendency of the oscillations of a pair of nodes to synchronize or desynchronize due to their local interaction in the network.

We begin by extending models of spin systems to the space of oscillatory phases. The vector of phases ϕ=(ϕ1,…,ϕN)\phi= (\phi_1,\ldots,\phi_N) is called a phase configuration, and TN:=[0,2π]N\mathbb{T}^N := [0,2\pi]^N consists of all possible phase configurations of the network. The direct analog of the Ising model on TN\mathbb{T}^N uses the energy function E:TN→RE:\mathbb{T}^N \to\mathbb{R} defined as

E(ϕ)=−12∑i=1N∑j=1NJijcos⁡(ϕj−ϕi)−∑i=1Nhicos⁡(ϕi).(4)E(\phi)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}\cos(\phi_j-\phi_i)-\sum_{i=1}^{N}h_i\cos(\phi_i). \tag*{(4)}

In statistical mechanics, the model of spin systems with this energy function is called the XY-model, which is equivalent to the d=2d = 2 case of the dd-vector model (3) (cf. [21] for details on the relationship between the XY-model and coupled phase oscillators). The local interaction energy along the edge (i,j)(i,j) is −Jijcos⁡(ϕj−ϕi)-J_{ij}\cos(\phi_j-\phi_i), and behaves similarly to the corresponding term in the Ising model: when Jij>0J_{ij} > 0, it is minimized when ϕi=ϕj\phi_i = \phi_j i.e. when ii and jj are phase synchronized, and when Jij<0J_{ij} < 0, it is minimized when ϕj−ϕi=π\phi_j-\phi_i=\pi, i.e. when the oscillations are exactly one half cycle out of phase.

Unlike a discrete spin, the phase of an oscillation varies continuously, and we can compute the ground states of the energy (4) using a continuous-time dynamical system. When hi=0h_i = 0 the gradient dynamics, ϕ˙=−∇ϕE(ϕ)\dot{\phi}=-\nabla_\phi E(\phi), is a special case of the celebrated Kuramoto model (see Sidebar: “The Kuramoto Model of Synchronization”),

ϕ˙i=∑j=1NJijsin⁡(ϕj−ϕi)(5)\dot{\phi}_i=\sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i) \tag*{(5)}

We may also consider gradient dynamics that are noisy,

dϕi=∑j=1NJijsin⁡(ϕj−ϕi)dt+2β−1dwi(6)d\phi_i=\sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i)dt+\sqrt{2\beta^{-1}}dw_i \tag*{(6)}

where wiw_i is a Wiener process and β\beta is the inverse temperature. The density of phases at time tt, given by ρt(ϕ)\rho_t(\phi), satisfies

The Kuramoto Model of Synchronization

Synchronization of oscillatory systems is observed in numerous disciplines including physics (e.g. microwave oscillators and superconducting Josephson junctions), chemistry (oscillating chemical reactions), neuroscience (e.g. activity of individual neurons and brain networks), engineering (e.g. electric power distribution networks), ecology (e.g. synchronous flashing of fireflies or chirping crickets), and social networks (e.g. opinion dynamics), see e.g. [S15]–[S19] and references therein.

Despite the sheer breadth of these examples, they are often studied within the common framework of coupled phase dynamics. In this setting, one assumes that the phase of each oscillator, in the absence of coupling, evolves at a constant rate according to a natural frequency ϕ˙i=ωi\dot{\phi}_i = \omega_i. Interactions between nodes are modeled with a coupling function Γ(ϕj−ϕi)\Gamma(\phi_j-\phi_i), resulting in a system generically of the form

ϕ˙i=ωi+∑j=1NJijΓ(θj−θi)(7)\dot{\phi}_i = \omega_i + \sum_{j=1}^{N} J_{ij}\Gamma(\theta_j-\theta_i) \tag*{(7)}

Since Γ\Gamma is periodic, it can be expanded as a Fourier series Γ(ψ)=∑k=−∞∞ckeikψ\Gamma(\psi)=\sum_{k=-\infty}^{\infty}c_k e^{ik\psi}. The Kuramoto model is the special case where the series contains only the first odd harmonic Γ(ψ)=sin⁡(ψ)\Gamma(\psi)=\sin(\psi), resulting in

ϕ˙i=ωi+∑j=1NJijsin⁡(θj−θi).(8)\dot{\phi}_i = \omega_i + \sum_{j=1}^{N} J_{ij}\sin(\theta_j-\theta_i). \tag*{(8)}

Originally introduced in [S20], initial work investigated the setting where the natural frequencies are drawn from the standard normal distribution ωi∼N(0,1)\omega_i \sim\mathcal{N}(0,1), and the coupling is all-to-all: Jij=KNJ_{ij}=\frac{K}{N} for all pairs (i,j)(i,j).

Since its introduction, a multitude of variations of the Kuramoto model have been studied, including

  • Kuramoto models with inertia

mθ¨+bθ˙=ωi+∑j=1NJijsin⁡(θj−θi)m\ddot{\theta}+b\dot{\theta}=\omega_i+\sum_{j=1}^{N}J_{ij}\sin(\theta_j-\theta_i)
  • Kuramoto models with delays

θ˙=ωi+∑j=1NJijsin⁡(θj(t−τij)−θi)\dot{\theta}=\omega_i+\sum_{j=1}^{N}J_{ij}\sin(\theta_j(t-\tau_{ij})-\theta_i)
  • Kuramoto models with biased couplings

θ˙=ωi+∑j=1NJijsin⁡(θj−θi−ψij)\dot{\theta}=\omega_i+\sum_{j=1}^{N}J_{ij}\sin(\theta_j-\theta_i-\psi_{ij})
Single oscillator and coupled oscillator network

Figure S3. (Left) Single oscillator with phase ϕi\phi_i changing at constant rate ωi\omega_i (Right) Coupled oscillator network where evolution of ϕi\phi_i now depends on the interactions with other oscillators.

The appeal of the Kuramoto model is both its many generalizations having a rich repertoire of behaviors, many of which are useful for computing applications, but also its universality. Since these models are expressed only in terms of the phases of oscillations, abstracting away the physical details of any particular instance of an oscillator network, they serve as universal models for computing with oscillatory systems.

ρt→ρ\rho_t \to\rho as t→∞t \to\infty where ρ\rho is the Boltzmann distribution

ρ(θ)=1Zβexp⁡(−βE(θ)).\rho(\theta) = \frac{1}{Z_\beta}\exp(-\beta E(\theta)).

Coupled oscillator networks described by (5) or (6) exhibit a range of complex behaviors, including frustration and disorder analogous to the Ising model. See, e.g., [22, 23, 24] and references therein for further details of disordered synchrony patterns of the Kuramoto model and their connections to spin glasses.

Gradient systems can also identify the ground states of higher dimensional spin models (3), however the standard gradient flow must be replaced by a projected gradient flow in order to enforce the constraint that zi∈Sd−1z_i \in S^{d-1}. In this case, the dynamics are

z˙i=(I−ziziT)∑j=1NJijzj(9)\dot{z}_i = (I-z_i z_i^{\mathsf T})\sum_{j=1}^{N}J_{ij}z_j \tag*{(9)}

where (I−ziziT)(I-z_i z_i^{\mathsf T}) is the orthogonal projection onto the tangent space TziSd−1T_{z_i}S^{d-1}. This system is a generalization of the Kuramoto model and is well-studied in the control community to model swarming behavior and consensus in multi-agent systems on the (d−1)(d-1)-sphere [25, 26, 27, 28, 29], and is also related to models that have been studied in the physics community of synchronization in non-Abelian spaces and quantum mechanical systems [30, 31]. In the special case where d=2d=2, the system reduces to (5).

Our interest in systems of the form (5) and (6) is in their connection to computing. Specifically

» Many computing operations can be reduced to identifying the ground states of an energy function, opening the door to implementation via a physical process that minimizes the energy. Such systems, called energy-based dynamical models, are well-studied and have deep connections to computational neuroscience, machine learning, and physical computing [32, 33].

» Phase oscillator models are universal and admit a diversity of physical realizations, This is because they are expressed entirely in terms of oscillatory phases, abstracting away physical details of any particular realization. The dynamics of a specific instance of an oscillatory system can be reduced to the models considered in this paper using phase reduction theory, see Sidebar: Phase Reductions of Oscillators in Neuroscience, Electronics, and Physics.

To design oscillator-based implementations of computational primitives, we proceed by approximating the Ising Hamiltonian with an energy function similar to (4), so the solution can then be computed with the corresponding gradient flow. In certain applications we will need to add additional penalty terms or higher order harmonics to (4) in order to transform the problem into a form suitable for implementation on coupled oscillator networks. However, once a suitable energy has been identified, if the gradient system can be realized through the dynamics of a physical device, then it can be used as an analog computer implementing that computational primitive.

Combinatorial Optimization with Coupled Oscillator Networks

We now move on to the first computing application of coupled oscillator networks, solving combinatorial optimization problems. Examples include the MAX-CUT problem, the traveling salesman problem, and the Boolean satisfiability problem, and are of importance both in theoretical computer science, as well as practical applications such as operations research, VLSI circuit design, and artificial intelligence [34, 35, 36]. Large instances of such problems are generally intractable on digital computers due to the fact that they are NP-complete or NP-hard.

However, as we show here, coupled oscillator networks are capable of solving these problems efficiently by exploiting the fact that the solutions to many NP problems can be encoded in the ground states of a corresponding Ising Hamiltonian [37] (see, e.g., Sidebar: “Ising Models of NP Problems”). Physical devices that minimize the Hamiltonian, called Ising machines, can be used as hardware solvers of combinatorial optimization problems [38]. Ising machines based on oscillator networks have been proposed to solve a number of NP-hard problems including the graph coloring problem [39, 40, 41], Boolean satisfiability problem [42], and the graph maximum cut problem [43].

Formally, we are interested in solving the problem of minimizing an Ising Hamiltonian

min⁡s∈{−1,1}NH(s)≔−12∑i=1N∑j=1NJijsisj(10)\min_{s\in\{-1,1\}^{N}} H(s) \coloneqq-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}s_i s_j \tag*{(10)}

The system we use to solve (10) is a Kuramoto-like system of coupled phase oscillators introduced in [44], called an Oscillator Ising Machine (OIM), whose dynamics are

ϕ˙i=∑j=1NJijsin⁡(ϕj−ϕi)−μisin⁡(2ϕi)i=1,…,N(11)\dot{\phi}_i=\sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i)-\mu_i\sin(2\phi_i)\qquad i=1,\ldots,N \tag*{(11)}

which is the gradient flow of the energy function

Eμ(ϕ)=−12∑i=1N∑j=1NJijcos⁡(ϕj−ϕi)+∑i=1Nμisin⁡2(ϕi).(12)E_\mu(\phi)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}\cos(\phi_j-\phi_i)+\sum_{i=1}^{N}\mu_i\sin^2(\phi_i). \tag*{(12)}

This system converges to equilibria corresponding to spin configurations of the Ising model through the map ϕ∗:{−1,1}N→TN\phi^*:\{-1,1\}^{N}\to\mathbb{T}^{N}, where

ϕi∗(s)={0si=+1πsi=−1.(13)\phi_i^*(s)= \begin{cases} 0 & s_i=+1\\ \pi& s_i=-1. \end{cases} \tag*{(13)}

Note that (11) may possess equilibria that do not have the form (13), though in general such equilibria are structurally unstable [45].

The forcing term μisin⁡(2ϕi)\mu_i\sin(2\phi_i) is called second harmonic injection locking since in circuit realizations it is generated by an exogenous periodic input whose frequency is twice

Phase Reductions of Oscillators in Neuroscience, Electronics, and Physics

Oscillatory networks are omnipresent in both natural and engineered systems. However, unlike the simplified phase dynamics (5) and (6), models of such systems are generally expressed in terms of variables relevant to their physical operation e.g. voltages and currents in analog circuits, firing rates or ion channel activations in neurodynamics. This raises the question: when do the phase dynamics of real-world oscillators correspond to the models (5) or (6) used for analog computation? The answer can be obtained using a technique called phase reduction [S21], [S22], which rigorously reduces state-space models to a representation involving only the phase of the oscillation.

Phase Reduction of a Single Oscillator

We begin by considering a single oscillator, with an input, whose state encodes physically relevant quantities

x˙=f(x)+ϵu.(14)\dot{x}=f(x)+\epsilon u. \tag*{(14)}

We assume that when u≡0u\equiv0,

  1. There exists an asymptotically stable TT-period limit cycle with basin of attraction B\mathcal{B}, denoted x∗(t)x^*(t).

  2. There exists an asymptotic phase, i.e. a map θ:B→[0,2π]\theta:\mathcal{B}\to[0,2\pi] such that for all initial conditions x0∈Bx_0\in\mathcal{B}, the solution x(t)x(t) satisfies

lim⁡t→∞∣x(t)−x∗(t+T2πθ(x0))∣=0\lim_{t\to\infty}\left\lvert x(t)-x^*\left(t+\frac{T}{2\pi}\theta(x_0)\right)\right\rvert=0

The asymptotic phase can be interpreted as the phase difference between the state and a fixed reference point as it asymptotically converges to the limit cycle. We are interested in characterizing how a weak input affects the phase of the limit cycle oscillation.

If xx is close to the limit cycle, we can approximate xx with the point exactly on the limit cycle having the same phase, x≈x∗(T2πθ(x))x\approx x^*\left(\frac{T}{2\pi}\theta(x)\right). Then θ(x(t))\theta(x(t)) evolves according to

ddtθ(x)=∇θ(x)T(f(x)+ϵu)≈ω+ϵ∇θ(x∗(T2πθ(x)))Tu.\begin{aligned} \frac{d}{dt}\theta(x)=\nabla\theta(x)^{\mathsf{T}}(f(x)+\epsilon u) \\ &\approx\omega+\epsilon\nabla\theta\left(x^*\left(\frac{T}{2\pi}\theta(x)\right)\right)^{\mathsf{T}}u. \end{aligned}

where in the previous expression we used the fact that ∇θ(x∗(t))Tf(x∗(t))=ω\nabla\theta(x^*(t))^{\mathsf{T}}f(x^*(t))=\omega, since along the limit cycle the phase evolves at a constant rate, i.e. ddtθ(x∗(t))=∇θ(x∗(t))Tf(x∗(t))=ω\frac{d}{dt}\theta(x^*(t))=\nabla\theta(x^*(t))^{\mathsf{T}}f(x^*(t))=\omega.

Let Z(⋅)=∇θ(x∗(T2π⋅))Z(\cdot)=\nabla\theta(x^*(\frac{T}{2\pi}\cdot)) be the infinitesimal phase response curve (iPRC). By substituting Z(θ)Z(\theta) into the previous equation, we see that the phase evolution can be modeled with an autonomous dynamical system

θ˙=ω+ϵZ(θ)Tu.(15)\dot{\theta}=\omega+\epsilon Z(\theta)^{\mathsf{T}}u. \tag*{(15)}
Asymptotic phase and infinitesimal phase response curve of the Van der Pol oscillator

Figure S4. Asymptotic phase (left) and infinitesimal phase response curve (right) of the Van der Pol oscillator x˙1=x2\dot{x}_1=x_2, x˙2=μ(1−x12)x2−x1\dot{x}_2=\mu(1-x_1^2)x_2-x_1.

In experimental settings, the iPRC may be obtained by subjecting the system to a small external perturbation and empirically measuring the phase shift of the response [S23], [S24] (this is referred to as the direct method). If a mathematical model of the form (S3) is available, it is also possible to numerically calculate it using the adjoint method [S21], which consists of solving the adjoint equation

dZ(θ)dθ=−∂f(x)∂x∣x=x∗(T2πθ)TZ(θ)(16)\frac{dZ(\theta)}{d\theta}=-\left.\frac{\partial f(x)}{\partial x}\right|_{x=x^*(\frac{T}{2\pi}\theta)}^{\mathsf{T}}Z(\theta) \tag*{(16)}

subject to the conditions that f(x∗(0))TZ(0)=ωf(x^*(0))^{\mathsf{T}}Z(0)=\omega and ZZ is 2π2\pi-periodic. Because the adjoint system is unstable when x∗(t)x^*(t) is stable, it must be integrated backward in time.

When u≡0u\equiv0, the phase evolves at a constant rate θ(t)=ωt\theta(t)=\omega t. We define the phase deviation as the difference between the phase under the forced dynamics with respect to the unforced reference: ϕ=θ−ωt\phi=\theta-\omega t. Then

ϕ˙=ϵZ(ϕ+ωt)Tu(17)\dot{\phi}=\epsilon Z(\phi+\omega t)^{\mathsf{T}}u \tag*{(17)}

Suppose that uu is TT-periodic. When ϵ\epsilon is small, the timescale over which the phase deviation changes is slow relative to the oscillatory frequency of uu. Thus, (S6) may be simplified by averaging the high-frequency oscillations and changing timescale t↦1ϵtt\mapsto\frac{1}{\epsilon}t [S25, Section 9.3], [S26],

ϕ˙≈Ω(ϕ)Ω(ϕ):=1T∫0TZ(ϕ+ωt)Tu(t) dt.(18)\dot{\phi}\approx\Omega(\phi)\qquad\Omega(\phi):=\frac{1}{T}\int_0^T Z(\phi+\omega t)^{\mathsf{T}}u(t)\,dt. \tag*{(18)}

Note that equations similar to (S6) and (S7) can also be derived using Adler’s equation which models injection locking in analog circuits [S27], [S28].

Phase Reduction of Oscillator Networks

We now extend this analysis to networks of limit cycle oscillators. Suppose that we have a network with NN nodes whose adjacency matrix is given by J∈RN×NJ \in\mathbb{R}^{N \times N}. We assume that dynamics are weakly connected, meaning they have the form

x˙i=f(xi)+ϵ(vi+∑j=1NJijg(xi,xj))(19)\dot{x}_i=f(x_i)+\epsilon\left(v_i+\sum_{j=1}^{N}J_{ij}g(x_i,x_j)\right) \tag*{(19)}

The system may be interpreted as NN copies of (S3), where the input to the iith node, ui=vi+∑j=1NJijg(xi,xj)u_i=v_i+\sum_{j=1}^{N}J_{ij}g(x_i,x_j), consists of an input applied directly to the node, as well as its interactions with its neighbors.

Repeating the steps of the derivation in the single oscillator case, and letting Γ\Gamma be the average of the nodes’ interactions,

Γ(Δϕ)=1T∫0TZ(ωt)Tg(x∗(t),x∗(t+T2πΔϕ)) dt\Gamma(\Delta\phi)=\frac{1}{T}\int_{0}^{T}Z(\omega t)^{\mathsf{T}}g\left(x^*(t),x^*\left(t+\frac{T}{2\pi}\Delta\phi\right)\right)\,\mathrm{d}t

we obtain

ϕ˙i=Ω(ϕi)+∑j=1NJijΓ(ϕj−ϕi)(20)\dot{\phi}_i=\Omega(\phi_i)+\sum_{j=1}^{N}J_{ij}\Gamma(\phi_j-\phi_i) \tag*{(20)}

which is a generalized form of (5). Extensions of phase reduction techniques to stochastic oscillators [S29]–[S31] may also be used to obtain models of the form (6)

ϕ˙i=Ω(ϕi)+∑j=1NJijΓ(ϕj−ϕi)+dwi(21)\dot{\phi}_i=\Omega(\phi_i)+\sum_{j=1}^{N}J_{ij}\Gamma(\phi_j-\phi_i)+\mathrm{d}w_i \tag*{(21)}

Models of the form (S9) and (S10) abstract away the physics from real-world instances of coupled oscillator networks, and convert them into forms more suitable for reasoning about their computational capabilities.

the natural frequency of the oscillator at node ii. It serves to penalize phase values ϕi∉{0,π}\phi_i\notin\{0,\pi\} that do not correspond to valid spin configurations. The regularization parameters μi≥0\mu_i\geq0 adjust the degree of penalization. While many analyses of OIMs assume that μ\mu is homogeneous across all nodes, recent work [46] has established that, in many cases, heterogeneity improves convergence to low energy spin configurations.

By definition, Eμ(ϕ∗(s))=H(s)E_\mu(\phi^*(s))=H(s) for all spin configurations ss. Thus minimizing EμE_\mu may serve as a proxy for minimizing the Ising Hamiltonian, and in practice one observes good correspondence between solutions computed by OIMs and ground states of the Ising model. Empirical benchmarks show that OIMs realized as conventional CMOS circuits achieve superior performance and scalability to classical algorithms, such as simulated annealing, as well as non-oscillatory Ising machines such as the D-WAVE quantum Ising machine and laser-based coherent Ising machines [47]. However theoretical guarantees on the performance of OIMs are still lacking. This is because the relationship between solutions of (8) and the stability of equilibria of (9) is highly complex. In particular, s∗s^* being a global optimizer of the Ising Hamiltonian is neither necessary nor sufficient for stability of the corresponding equilibrium ϕ∗(s∗)\phi^*(s^*), as we show in the following example.

Example 1: Consider the frustrated network in Figure 3. We have the following:

  • If μi=0.1\mu_i=0.1 for all ii, then (9) does not have any stable equilibria corresponding to a valid spin configuration, and in particular ϕ∗(s∗)\phi^*(s^*) is unstable for every global minimum s∗s^*.

  • If μi=10\mu_i=10 for all ii, then ϕ∗(s)\phi^*(s) is asymptotically stable for all s∈{−1,1}Ns\in\{-1,1\}^{N}, implying that the equilibrium corresponding to a spin configuration is asymptotically stable regardless of whether it is a minimizer of (8) or not.

  • There exists no μ\mu such that the only stable equilibria of (9) correspond to minimizers of (8).

The previous example illustrates the difficulties related to stability analysis of (9), and in particular, the impact of the choice of μ\mu: if μ\mu is too small, the OIM fails to converge to an equilibrium corresponding to a valid spin configuration of the Ising Hamiltonian, while if μ\mu is too large, the OIM

Ising Models of NP Problems

The Ising model provides a framework to reason about many problems in computing, since these problems are often equivalent to computing the ground states of a certain Ising Hamiltonian. We show here the sense in which minimizing an Ising Hamiltonian can serve as a proxy for “difficult” problems in computer science.

Consider the following combinatorial optimization problem involving an Ising Hamiltonian (1),

min⁡s∈{−1,1}NH(s).(22)\min_{s \in\{-1,1\}^{N}} H(s). \tag*{(22)}

It is useful to distinguish between two types of problems related to minimizing the Ising Hamiltonian [19]:

  1. Ising Decision Problem: Given a value H0∈RH_0 \in\mathbb{R}, establish whether there exists a spin configuration s∈{−1,1}Ns \in\{-1,1\}^{N} such that H(s)<H0H(s) < H_0.

  1. Ising Optimization Problem: Identify a spin configuration s∗∈{−1,1}Ns^{*} \in\{-1,1\}^{N} solving (S11)

Given a “difficult” problem QQ, the formulation of the Ising problem one uses as a proxy depends on the form of QQ: if QQ is a decision problem, i.e. it can be posed as a question requiring a “yes” or “no” answer, the Ising Decision problem is the natural proxy, whereas if QQ is naturally formulated as a search problem, one may instead use the optimization formulation. In either case, an Ising machine solves the Ising Optimization problem, though its solution can be used to solve the Ising Decision Problem.

Computing problems are sorted into complexity classes based on how the effort required to solve them scales asymptotically as N→∞N \to\infty. A decision problem belongs to class P if it can be solved in polynomial time, i.e. the number of steps needed to solve it is polynomial in NN. It belongs to class NP if there exists a certificate one can use to validate the solution in polynomial time. Any problem in class P is also in class NP, but whether the reverse inclusion holds is still an open problem in theoretical computer science.

Following the convention in [37], we delineate two additional complexity classes that correspond to the most difficult computing problems, and the formulation of the Ising problem that serves as a proxy:

  • NP-complete: A problem QQ is called NP-complete if QQ is in class NP and any other NP problem can be reduced to QQ in polynomial time. Thus if one can efficiently solve QQ, any other NP problem can also be solved quickly. NP-complete problems are equivalent to the Ising Decision Problem given a corresponding Hamiltonian, such as the Boolean satisfiability problem.

  • NP-hard: A problem QQ is called NP-hard if any other NP problem can be reduced to QQ in polynomial time, though QQ does not necessarily need to belong to class NP. Many NP-hard problems are equivalent to the Ising Optimization Problem given a corresponding Hamiltonian, such as the graph partitioning problem.

The relationship between these complexity classes is illustrated in Figure S5. We refer the reader to [37] for a comprehensive survey of Ising formulations of common NP-complete and NP-hard problems.

Relationship between computational complexity classes

Figure S5. Relationship between computational complexity classes in the cases where P≠NPP \ne NP (left) and P=NPP = NP (right).

also stabilizes spin configurations1 that are suboptimal. As we show later, this challenge is intrinsically related to the presence of frustration in the network, which together with the combinatorial explosion in the number of equilibria of large networks (in a network with NN nodes, there are 2N2^N spin configurations), means characterizing precisely the relationship between the stability and optimality of a given spin configuration is a nontrivial problem.

In the subsequent section we introduce a framework to analyze the stability and optimality of spin configurations using methods from the theory of signed graphs. Given a fixed network, our approach associates each spin configuration, ss, to a signed graph, G(s)\mathcal{G}(s), where both stability and optimality of ϕ∗(s)\phi^*(s) are encoded in the eigenvalues of its corresponding Laplacian matrix. Thus, by analyzing the spectra of these Laplacians, we can characterize the sense in which low energy spin configurations are “more stable”, as well as the effect of the regularization parameters. For frustration-free networks we obtain exact stability results, and for frustrated networks we establish this relationship probabilistically. This formalism also allows us to investigate the role of heterogeneity on stability properties, and in particular, show that heterogeneous networks preferentially stabilize low energy spin configurations.

Signed Graphs of the Ising Model

Here we introduce a framework to analyze the stability of (9) using methods from the theory of signed graphs, originally proposed in [46]. Let JJ be a fixed adjacency matrix encoding interactions between nodes. For all s∈{−1,1}Ns \in\{-1,1\}^N, let G(s)\mathcal{G}(s) be the signed graph with adjacency matrix

Aij(s)=Jijsisj(23)A_{ij}(s) = J_{ij}s_i s_j \tag*{(23)}

In Figure 5, we demonstrate the signed graphs corresponding to the frustrated network from Example 1. By construction, the sign of an edge (i,j)(i,j) obeys the following rule

Signed graphs corresponding to spin configurations of the frustrated network

Figure 5. Signed graphs corresponding to spin configurations of the network J=[0,−1,−1;−1,0,−1;−1,−1,0]J = [0,-1,-1;-1,0,-1;-1,-1,0]. Because the network is frustrated, no configuration results in a signed graph with only positive edges.

sgn⁡(Aij(s))={1local energy (i,j) is minimized−1local energy (i,j) is maximized\operatorname{sgn}(A_{ij}(s)) = \begin{cases} 1 & \text{local energy } (i,j) \text{ is minimized}\\ -1 & \text{local energy } (i,j) \text{ is maximized} \end{cases}

Properties of the Ising model can be recast within this signed graph theoretic framework. A network is frustrated if for all spin configurations s∈{−1,1}Ns \in\{-1,1\}^N the corresponding signed graph G(s)\mathcal{G}(s) contains at least one negative edge, otherwise the network is frustration-free.

The Laplacian of a signed graph is the matrix L(s)=D(s)−A(s)L(s) = D(s) - A(s), where D(s)D(s) is the diagonal matrix consisting of row sums of A(s)A(s). We have

Lij(s)={∑k=1NJiksiski=j−Jijsisji≠j(24)L_{ij}(s) = \begin{cases} \sum_{k=1}^{N} J_{ik}s_i s_k & i=j\\ -J_{ij}s_i s_j & i\ne j \end{cases} \tag*{(24)}

Both optimality and stability of a spin configuration ss are related to the spectral properties of the matrix L(s)L(s). The Ising Hamiltonian satisfies

H(s)=−12trace⁡(L(s))=−12∑i=1Nλi(L(s))H(s) = -\frac{1}{2}\operatorname{trace}(L(s)) = -\frac{1}{2}\sum_{i=1}^{N}\lambda_i(L(s))

where λ1(L(s))≤λ2(L(s))≤⋯≤λN(L(s))\lambda_1(L(s)) \le\lambda_2(L(s)) \le\cdots\le\lambda_N(L(s)) are the eigenvalues of L(s)L(s). Since (9) is the gradient system of the energy function EμE_\mu, stability can be determined from the eigenvalues of the Hessian of EμE_\mu. The spin configuration is asymptotically stable when ∇2Eμ(ϕ∗(s))⪰0\nabla^2 E_\mu(\phi^*(s)) \succeq0, or equivalently, when λ1(∇2Eμ(ϕ∗(s)))>0\lambda_1(\nabla^2 E_\mu(\phi^*(s))) > 0 where λ1\lambda_1 denotes the smallest eigenvalue. By direct computation,

(∇2Eμ)ij={∑k=1NJikcos⁡(ϕk−ϕi)+2μicos⁡(2ϕi)i=j−Jijcos⁡(ϕj−ϕi)i≠j(25)(\nabla^2 E_\mu)_{ij} = \begin{cases} \sum_{k=1}^{N} J_{ik}\cos(\phi_k-\phi_i) + 2\mu_i\cos(2\phi_i) & i=j\\ -J_{ij}\cos(\phi_j-\phi_i) & i\ne j \end{cases} \tag*{(25)}

and evaluating (14) at the equilibrium ϕ∗(s)\phi^*(s) yields

∇2Eμ(ϕ∗(s))=L(s)+2diag⁡(μ1,…,μN).\nabla^2 E_\mu(\phi^*(s)) = L(s) + 2\operatorname{diag}(\mu_1,\ldots,\mu_N).

Thus the connection between the stability of a spin configuration and its energy value corresponds to the relationship between the sum of the eigenvalues of L(s)L(s) and the minimum eigenvalue of the perturbed matrix L(s)+2diag⁡(μ)L(s) + 2\operatorname{diag}(\mu). In the following we characterize this relationship exactly in the frustration-free case, and probabilistically in the frustrated case.

Stability of Frustration-free Networks

We now analyze the stability of the system (11) using the signed graph theoretic framework introduced in the previous section, in the special case where the network JJ is frustration-free, utilizing the notion of structural balancing of signed graphs, which plays an important role in dynamics on signed networks [48, 49].

Let s∈{−1,1}Ns \in\{-1,1\}^{N} be a spin configuration and G(s)\mathcal{G}(s) its corresponding signed graph. We say that G(s)\mathcal{G}(s) is structurally balanced if there exists a partition of the set of nodes V={1,2,…,N}\mathcal{V} = \{1,2,\ldots,N\} into V1⊂V\mathcal{V}_1 \subset\mathcal{V} and V2⊂V\mathcal{V}_2 \subset\mathcal{V} such that edges within V1\mathcal{V}_1 or V2\mathcal{V}_2 are positive, and edges between V1\mathcal{V}_1 and V2\mathcal{V}_2 are negative. The corresponding partition is called balanced. We have the following result.

Lemma 1: Let s∈{−1,1}Ns \in\{-1,1\}^{N} be a spin configuration. Then JJ is frustration-free if and only if G(s)\mathcal{G}(s) is structurally balanced.

Proof: We begin with the forward direction. If JJ is frustration-free, there exists a spin configuration s∗∈{−1,1}Ns^* \in\{-1,1\}^{N} such that Jijsi∗sj∗>0J_{ij}s_i^*s_j^* > 0 for all edges (i,j)(i,j). Letting V1={i∣si=si∗}\mathcal{V}_1 = \{i \mid s_i=s_i^*\} and V2={i∣si≠si∗}\mathcal{V}_2 = \{i \mid s_i \ne s_i^*\}, it follows immediately that this partition is balanced.

To prove the reverse direction, suppose G(s)\mathcal{G}(s) is structurally balanced, and let V1,V2\mathcal{V}_1,\mathcal{V}_2 be the corresponding partition of the node set. If either V1=∅\mathcal{V}_1=\varnothing or V2=∅\mathcal{V}_2=\varnothing, then all edges within the signed graph are positive, and the result follows immediately.

For the case where both sets are nonempty, we introduce an iterative procedure to construct a spin configuration where each interaction energy is simultaneously minimized. Let s~(0)=s\widetilde{s}(0)=s, V~1(0)=V1\widetilde{\mathcal{V}}_1(0)=\mathcal{V}_1, and V~2(0)=V2\widetilde{\mathcal{V}}_2(0)=\mathcal{V}_2. For each iteration k∈Nk \in\mathbb{N}, choose a node ik∈V~2(k)i_k \in\widetilde{\mathcal{V}}_2(k), and let

s~j(k+1)={−sj(k)j≠iksj(k)j=ik.\widetilde{s}_j(k+1)= \begin{cases} -s_j(k) & j \ne i_k\\ s_j(k) & j=i_k. \end{cases}
V~1(k+1)=V~1(k)∪{ik}\widetilde{\mathcal{V}}_1(k+1)=\widetilde{\mathcal{V}}_1(k)\cup\{i_k\}
V~2(k+1)=V~2(k)∖{ik}\widetilde{\mathcal{V}}_2(k+1)=\widetilde{\mathcal{V}}_2(k)\setminus\{i_k\}

The idea is that at each iteration, a new spin configuration is obtained by flipping the spin of node ik∈V~2(k)i_k \in\widetilde{\mathcal{V}}_2(k). Because flipping the spin at node iki_k also flips the signs of all the edges incident to iki_k, we transfer iki_k from V~2\widetilde{\mathcal{V}}_2 to the set V~1\widetilde{\mathcal{V}}_1 in order to maintain balancing. We illustrate this procedure in Figure 6. Since V~2(k)=∅\widetilde{\mathcal{V}}_2(k)=\varnothing at iteration k=∣V~2(0)∣k=|\widetilde{\mathcal{V}}_2(0)|, all edges of G(s~(k))\mathcal{G}(\widetilde{s}(k)) are positive and JJ is frustration-free.

Spin flipping procedure described in proof of Lemma 1

Figure 6. Spin flipping procedure described in proof of Lemma 1. Positive edges are blue and negative edges are red. Edges incident to iki_k are depicted by dashed lines. (Top) Structurally balanced graph partitioned into sets V~1(k)\widetilde{V}_1(k) and V~2(k)\widetilde{V}_2(k). (Bottom) Flipping the spin at iki_k also flips the signs of all of its edges. To maintain balancing of the partition, iki_k is transferred from V~2\widetilde{V}_2 to V~1\widetilde{V}_1 on the (k+1)(k+1)th iteration.

The previous result establishes equivalence between structural balance of the signed graphs G(s)\mathcal{G}(s) and JJ being frustration-free. In the following result, we leverage this connection to analyze the stability of minimizers of the Ising Hamiltonian by applying results on the spectra of Laplacians corresponding to structurally balanced signed graphs. Specifically, we identify conditions on μ\mu such that ϕ∗(s)\phi^*(s) is asymptotically stable if and only if ϕ∗(s)\phi^*(s) is a global minimizer of (10).

Theorem 1: Let JJ be a frustration-free network. If 0<μi<μ∗0<\mu_i<\mu^* for all i=1,…,Ni=1,\ldots,N, where μ∗\mu^* is given by (15), it follows that ϕ∗(s)\phi^*(s) is asymptotically stable if and only if s∈{−1,1}Ns\in\{-1,1\}^{N} is a global minimizer of (10).

Proof: Let s∈{−1,1}Ns\in\{-1,1\}^{N}. If ss is a global minimizer of (10), then ss simultaneously minimizes all local interaction energies, so G(s)\mathcal{G}(s) has only positive edges. Therefore L(s)L(s) corresponds to the Laplacian of an unsigned graph, so L(s)⪰0L(s)\succeq0 (see [50 Chapter 13] or [51 Chapter 6] for details on the spectral properties of the graph Laplacian). Thus for any μ∈RN\mu\in\mathbb{R}^{N}, we have ∇2Eμ(ϕ∗(s))=L(s)+2diag⁡(μ)≻0\nabla^2 E_\mu(\phi^*(s))=L(s)+2\operatorname{diag}(\mu)\succ0 and therefore ϕ∗(s)\phi^*(s) is stable.

If ss is not a global minimizer, then by Lemma 1 it follows that G(s)\mathcal{G}(s) is structurally balanced and has at least one negative edge. By [52 Corollary IV.4], L(s)L(s) is indefinite, thus λ1(L(s))<0\lambda_1(L(s))<0. Letting

μ∗=min⁡s′∈{−1,1}N{−λ1(L(s′))2∣s′ is suboptimal},(26)\mu^*=\min_{s'\in\{-1,1\}^{N}}\left\{-\frac{\lambda_1(L(s'))}{2}\mid s'\text{ is suboptimal}\right\}, \tag*{(26)}

it follows that

λ1(∇2Eμ(ϕ∗(s)))=λ1(L(s)+2diag⁡(μ))<0\lambda_1\left(\nabla^2 E_\mu(\phi^*(s))\right)=\lambda_1\left(L(s)+2\operatorname{diag}(\mu)\right)<0

for any μ∈R>0N\mu\in\mathbb{R}^{N}_{>0} where μi<μ∗\mu_i<\mu^*, and ss is unstable.

Stability of Frustrated Networks

We now move on to the problem of analyzing the stability of (11) when the network JJ is frustrated. In this case, the signed graphs corresponding to spin configurations are not structurally balanced, so analytic results on the spectrum of the graph Laplacian are unavailable. We overcome this challenge by analyzing ensembles of random networks rather than specific instances, and characterizing the relationship between the energy and stability of spin configurations statistically.

For simplicity, we focus on the special case where all edges are antiferromagnetic, though it is straightforward to extend our approach to the setting where ferromagnetic interactions are present as well. In our model, both the network interconnection JJ and the spin configuration ss are sampled randomly. To examine the effect of heterogeneity in the regularization parameters, μ\mu is chosen randomly as well. Let N>0N>0 be the number of nodes in the graph and 0<p<10<p<1. Then

  1. A network JJ is randomly constructed following the Erdős–Rényi model, where for 1≤i<j≤N1\leq i<j\leq N,

Jij={−1with probability p0with probability 1−pJ_{ij} = \begin{cases} -1 & \text{with probability } p\\ 0 & \text{with probability } 1-p \end{cases}
  1. A spin configuration s∈{−1,1}Ns\in\{-1,1\}^{N} is sampled uniformly at random.

  1. The regularization parameters μ1,…,μN\mu_1,\ldots,\mu_N are sampled independently from a distribution M\mathcal{M} supported on [0,∞)[0,\infty) with mean μˉ\bar{\mu} and variance σ2\sigma^2.

Let G(s)\mathcal{G}(s) be the signed graph whose adjacency matrix is (23). Then, the graph Laplacian L(s)L(s), and the Hessian ∇2Eμ(ϕ∗(s))\nabla^2 E_{\mu}(\phi^*(s)) are random matrices, and their eigenvalues can be treated as random variables.

The distribution of eigenvalues of the Laplacian and the Hessian can be derived using methods from random matrix theory [53, 54]. Given a symmetric matrix A∈RN×NA\in\mathbb{R}^{N\times N}, define the empirical spectral density (ESD) of AA as

ρ(λ;A)=1N∑i=1Nδ(λ−λi(A))\rho(\lambda;A)=\frac{1}{N}\sum_{i=1}^{N}\delta(\lambda-\lambda_i(A))

In the case where A(s)A(s) is the adjacency matrix of G(s)\mathcal{G}(s), it follows by classical results in random matrix theory2 that ρ(λ;A(s)/pN)\rho(\lambda;A(s)/\sqrt{pN}) converges almost surely to the semi-circle law ρsc(λ)=12π4−λ2\rho_{\mathrm{sc}}(\lambda)=\frac{1}{2\pi}\sqrt{4-\lambda^2} as N→∞N\to\infty. Recent work has also characterized the limit of the ESD of Laplacian matrices of random graphs [55, 56, 57], however a key assumption in these works is that the entries of the adjacency matrix are independent and identically distributed, which is violated for ensembles corresponding to signed graphs of the Ising model. Nonetheless, numerical experiments show that, consistent with the independent case, ρ(λ;L(s)/pN)\rho(\lambda;L(s)/\sqrt{pN}) converges weakly in distribution to ρsc⊞ρgauss\rho_{\mathrm{sc}}\boxplus\rho_{\mathrm{gauss}} where ρgauss\rho_{\mathrm{gauss}}

Histograms of eigenvalues and density comparisons

Figure 7. (Left) Histogram of eigenvalues of 1pNA(s)\frac{1}{\sqrt{pN}}A(s) where N=1000N=1000 and p=0.05p=0.05 compared against the density of the semi-circle law. (Right) Numerically computed histogram of eigenvalues of 1pNL(s)\frac{1}{\sqrt{pN}}L(s) where N=1000N=1000 and p=0.05p=0.05 compared against the density of the free additive convolution of the semi-circle law with the Gaussian distribution (see [55] for details).

is the density of the standard normal distribution and the ⊞\boxplus symbol denotes the free additive convolution [55].

Within this framework, the relationship between the energy and stability of a given spin configuration can be expressed as the conditional expectation of the minimum eigenvalue λ1(∇2Eμ(ϕ∗(s)))\lambda_1(\nabla^2 E_{\mu}(\phi^*(s))) at the energy level H(s)=hH(s)=h. This quantity can be approximated as

E[λ1(∇2Eμ(ϕ∗(s)))∣H(s)=h]≈−(2N+σ2N(N−1)p)h+2μˉ−2(N−1)p+4σ2log⁡N(27)\mathbb{E}\left[\lambda_1\left(\nabla^2 E_{\mu}(\phi^*(s))\right)\mid H(s)=h\right] \approx-\left(\frac{2}{N}+\frac{\sigma^2}{N(N-1)p}\right)h+2\bar{\mu} -\sqrt{2(N-1)p+4\sigma^2}\log N \tag*{(27)}

see [58] for details. The expression (27) depends inversely on hh, meaning that as the energy of a spin configuration increases, on average the minimum eigenvalue decreases, and therefore it is less likely to be stable. Moreover, we see that increasing heterogeneity of the regularization parameters by raising σ2\sigma^2 both shifts the curve downward and steepens its slope cf. Figure 8(Left). Together, these effects selectively stabilize low energy configurations while destabilizing high energy configurations, cf. Figure 8(Right) where the histogram of Ising Hamiltonian values corresponding to stable spin configurations shifts to the left as σ2\sigma^2 is increased.

Numerical experiment plots

Figure 8. Numerical experiment with N=50N=50, p=0.15p=0.15, and μˉ=4\bar{\mu}=4. (Left) Plot of minimum Hessian eigenvalues vs. Ising Hamiltonian for 10,000 sampled random graphs. The dashed line corresponds to (16). (Right) Histogram of Ising Hamiltonian values corresponding to stable spin configurations.

Associative Memory with Coupled Oscillator Networks

We now discuss the second application of oscillator networks to computing: hardware implementations of associative memory. Associative memory refers to the ability of a system to store a number of memories, and respond to an input stimulus with the memory that most closely resembles it. Mathematical models of associative memory are of interest in cognitive neuroscience, since they provide insight into mechanisms through which memories are formed and recalled in the human brain. Computing applications of associative memory models were recognized early leading to interest in hardware implementations (see e.g. the Associatron [59], a neural network model implemented on hardware in 1972). These include:

  • Pattern Recognition: Associative memory systems may be used for certain supervised and unsupervised learning tasks involving pattern recognition. For example, if the memories correspond to images, then an input image may be classified using the label of the memorized image an associative memory system produces in response.

  • Generative Modeling: Recent work has identified parallels between associative memory models and diffusion-based generative models [60], [61], and demonstrated that certain associative memory models have the capacity to generalize beyond the memories that they store, enabling the retrieval process to generate new samples.

  • Transformer Architecture: The attention mechanism, which forms the core of the transformer architecture upon which modern large language models are based, is equivalent to certain associative memory models with the appropriate choice of activation function [62], [63]. We extend this connection to the setting of oscillator networks in Section: “Attention with Coupled Oscillator Networks”.

The most successful model of associative memory is the Hopfield model [6], [7], which relates the firing activity of a neuron with a spin variable, and encodes memories through the ground states of an Ising Hamiltonian. Memories are retrieved using a dynamical system that minimizes this Hamiltonian. In the original Hopfield model [6], the dynamics correspond to the discrete-time McCulloch-Pitts model of a neuron. Various modifications have been proposed in both discrete-time and continuous-time that generalize the energy function [7], [64]–[67]. To facilitate hardware realizations of associative memory, in this section we consider models of associative memory where the retrieval dynamics take the form of a coupled oscillator network.

The Hopfield Model

We begin by formalizing the associative memory problem and reviewing the Hopfield model (we refer the reader to [68] for a detailed introduction to the Hopfield model and its extensions). Suppose that we have a set of MM memories or patterns represented by spin configurations, denoted by ζ(1),ζ(2),…,ζ(M)∈{−1,1}N\zeta^{(1)},\zeta^{(2)},\ldots,\zeta^{(M)} \in\{-1,1\}^{N}. We wish to design a dynamical system that, when given a new pattern ζ∈{−1,1}N\zeta\in\{-1,1\}^{N} specifying its initial condition, the state converges to the stored memory ζ(i)\zeta^{(i)} that is closest to ζ\zeta.

In the Hopfield model, this problem is solved by choosing the weights JijJ_{ij} of an Ising Hamiltonian (1) (with field hi=0h_i=0) so that its ground states correspond to the memories we would like to store. The weights are chosen according to the Hebbian learning rule,

Jij=1N∑μ=1Mζi(μ)ζj(μ),(28)J_{ij} = \frac{1}{N}\sum_{\mu=1}^{M}\zeta_i^{(\mu)}\zeta_j^{(\mu)}, \tag*{(28)}

which acquires its name from a hypothesis by Hebb [69] that changes in the connection strength between two neurons ii and jj should be proportional to the correlation in their firing activity, which in this case is represented by the product ζi(μ)ζj(μ)\zeta_i^{(\mu)}\zeta_j^{(\mu)}, see also Sidebar: “Hebbian Learning in Oscillator Networks”.

To minimize the Ising Hamiltonian, Hopfield introduces the following dynamics, based on the McCulloch-Pitts model of a neuron [70],

si+=sgn⁡(∑j=1NJijsj).(29)s_i^{+} = \operatorname{sgn}\left(\sum_{j=1}^{N}J_{ij}s_j\right). \tag*{(29)}

It is not necessarily the case that the memories correspond to stable equilibria of (29). If the number of memories is too large, relative to the size of the network, then the learning rule (29) may instead introduce spurious minima unrelated to the desired memories. A central concern in the study of such neural networks is their storage capacity, i.e. the maximum number of memories that can be stored as attractors of (29).

Estimates of the storage capacity differ depending on whether one allows for small errors in the retrieved memories. We consider both cases here. Assume that the memories ζ(1),ζ(2),…,ζ(M)\zeta^{(1)},\zeta^{(2)},\ldots,\zeta^{(M)} are sampled independently and uniformly at random from the set of all possible spin configurations {−1,1}N\{-1,1\}^{N}. Then,

  • If small errors are permitted, then as N→∞N \to\infty, the maximum number of storable memories Mmax⁡M_{\max} satisfies αmax⁡=Mmax⁡N→0.138\alpha_{\max} = \frac{M_{\max}}{N} \to0.138.

  • If errors are not permitted, the maximum number of storable memories is Mmax⁡≈N4log⁡NM_{\max} \approx\frac{N}{4\log N} when NN is large.

Hebbian Learning in Oscillator Networks

Hebbian learning is a class of unsupervised learning rules for neural networks inspired by a theory of learning in neurobiological systems proposed by D. O. Hebb, often stated as the aphorism “neurons that fire together, wire together”. Here, learning can be viewed as a dynamical system governing the evolution of the weights JijJ_{ij} of a network which depends on the oscillatory phases

J˙=f(J;ϕ).(30)\dot{J}=f(J;\phi). \tag*{(30)}

Mathematical formulations of Hebbian learning [S32], [S33] typically require (S12) to satisfy, among other conditions, the following criteria

  1. Locality: The evolution of the weight of the edge (i,j)(i,j) depends only on the states ϕi\phi_i and ϕj\phi_j, J˙ij=fij(Jij,ϕi,ϕj)\dot{J}_{ij}=f_{ij}(J_{ij},\phi_i,\phi_j)

  2. Cooperativity: The weight of an edge JijJ_{ij} increases when the phases of the corresponding nodes, ϕi\phi_i and ϕj\phi_j, are synchronized.

  3. Synaptic Depression: The weight JijJ_{ij} decays in the absence of co-activity of ii and jj.

In the context of oscillator networks, a candidate satisfying these conditions is

fij(Jij,ϕi,ϕj)=−Jij+cos⁡(ϕi−ϕj).f_{ij}(J_{ij},\phi_i,\phi_j)=-J_{ij}+\cos(\phi_i-\phi_j).

The weight assignments for associative memory systems (28) and (34) can be viewed as a steady-state of this rule.

Typically, learning takes place on a slower timescale than that of the phase dynamics of the oscillator network. Thus, the combination of the two is a multiple timescale system

τϕ˙i=ωi+∑j=1NJijsin⁡(ϕj−ϕi)\tau\dot{\phi}_i=\omega_i+\sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i)
J˙ij=fij(Jij;ϕi,ϕj).(31)\dot{J}_{ij}=f_{ij}(J_{ij};\phi_i,\phi_j). \tag*{(31)}

where τ≪1\tau\ll1. Such systems exhibit a rich variety of synchronous behavior and have been extensively studied in [S34]–[S38].

Beyond biological modeling, Hebbian learning rules are also of importance in machine learning. For instance, neural networks are sometimes trained using contrastive Hebbian learning [8], [S40] rules of the form

J˙ij=cos⁡(ϕi−ϕj)−cos⁡(ϕ~i−ϕ~j)(32)\dot{J}_{ij}=\cos(\phi_i-\phi_j)-\cos(\widetilde{\phi}_i-\widetilde{\phi}_j) \tag*{(32)}

where ϕ\phi denotes the phases of the network when evolving freely, and ϕ~\widetilde{\phi} denotes the phases of the network when the outputs are clamped at a target value. Related learning rules arise in training algorithms for energy models such as equilibrium propagation [S41], where a contrastive update, similar to (S14), estimates the gradient of a loss function. Unlike backpropagation, rules of this form are suitable for implementation in hardware since the weight updates can be computed using the dynamics of the oscillator network itself, as demonstrated in [S42]–[S45].

References

Oscillatory Associative Memory

We now discuss an oscillatory associative memory system based on the standard Kuramoto model [71, 72]. This model generalizes beyond binary-valued memory vectors to those represented by continuous phase values, which we denote φ(1),φ(2),…,φ(M)∈TN\varphi^{(1)},\varphi^{(2)},\ldots,\varphi^{(M)} \in\mathbb{T}^{N}. The goal is to design a coupled oscillator network that stores these phase configurations as attractors such that the network converges to the memory nearest its initial phase configuration.

The energy function is

E(ϕ)=−12∑i=1N∑j=1NJijcos⁡(ϕj−ϕi).(33)E(\phi)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}\cos(\phi_j-\phi_i). \tag*{(33)}

As with the Hopfield model, we wish to encode the memories as the minimizers of (19). We accomplish this by applying a learning rule analogous to (17).

Jij=1N∑μ=1Mcos⁡(ϕi(μ)−ϕj(μ)).(34)J_{ij}=\frac{1}{N}\sum_{\mu=1}^{M}\cos\left(\phi_i^{(\mu)}-\phi_j^{(\mu)}\right). \tag*{(34)}

Similar to the standard Hebbian learning rule, the connection strength between nodes ii and jj is equal to the average correlation between their phases, represented by the quantity cos⁡(ϕi(μ)−ϕj(μ))\cos\left(\phi_i^{(\mu)}-\phi_j^{(\mu)}\right).

To compute the ground states of the energy function, we employ the gradient dynamics, which in this case results in the Kuramoto model,

ϕ˙i=∑j=1NJijsin⁡(ϕj−ϕi)(35)\dot{\phi}_i=\sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i) \tag*{(35)}

Certain works [71, 73, 74, 75] have also considered the effect of white noise, delays, and heterogeneity in the natural frequencies of oscillators on storage capacity and retrieval accuracy, but for simplicity we focus on the standard Kuramoto formulation.

We demonstrate the on an example where we would like to encode images in the attractors of (35). Consider a network where each node corresponds to a pixel in a Ngrid×NgridN_{\mathrm{grid}} \times N_{\mathrm{grid}} bitmap, and the value of each pixel is given by the phase of its node. In Figure 9 we demonstrate an example where two images are learned in a network with

Encoding images in the attractors of an associative memory system

Figure 9. Encoding images in the attractors of an associative memory system (21). Each node corresponds to a pixel in a Ngrid×NgridN_{\mathrm{grid}} \times N_{\mathrm{grid}} bitmap, where Ngrid=250N_{\mathrm{grid}} = 250. The color of each pixel is equal to the phase of the corresponding node. (Left) Two memories stored in the network using the Hebbian learning rule (20). (Center) Solution of (21) starting from a corrupted version of the second memory. The system successfully recovers the correct memory. (Right) Spurious attractor of the network.

Ngrid=250N_{\mathrm{grid}} = 250. The solution of (21) starting from a memory corrupted with noise is shown in Figure 9(Center), and we see the system successfully removes the noise and retrieves the correct memory. However, the system also has spurious attractors, shown in Figure 9(Right).

The stability of the memory φ(μ)\varphi^{(\mu)} can be analyzed by introducing a quantity m(μ)∈Cm^{(\mu)} \in\mathbb{C} called the overlap where

mμ=1N∑i=1Nei(ϕi−ϕi(μ))m_{\mu}=\frac{1}{N}\sum_{i=1}^{N}e^{\mathrm{i}(\phi_i-\phi_i^{(\mu)})}

The magnitude Rμ=∣mμ∣R_{\mu}=\lvert m_{\mu}\rvert of the overlap measures the closeness of the state ϕ\phi to the memory φ(μ)\varphi^{(\mu)} up to a constant phase shift ψμ=∠mμ\psi_{\mu}=\angle m_{\mu}. If Rμ=1R_{\mu}=1, then ϕi=ϕi(μ)+ψμ\phi_i=\phi_i^{(\mu)}+\psi_{\mu} for all i=1,2,…,Ni=1,2,\ldots,N, whereas if Rμ≈0R_{\mu}\approx0, then the phases are incoherent and the system has failed to retrieve the memory ϕi(μ)\phi_i^{(\mu)}. Thus the storage capacity and the retrieval accuracy can be estimated by studying the asymptotic behavior of the order parameters when the dynamics (21) are initialized near the memory φ(μ)\varphi^{(\mu)}.

Analysis of the storage capacity of the Kuramoto model was performed in [72]. In the limit as N→∞N \to\infty the storage capacity is αmax⁡=Mmax⁡N→0.042\alpha_{\max}=\frac{M_{\max}}{N}\to0.042, which is approximately 1/3 that of the classical Hopfield model. With the model (21), the retrieval process will inevitably introduce errors, and in fact the exact memory patterns are unstable whenever M>2M > 2. In Figure 10 we plot the average overlap for various values of the memory density α=MN\alpha= \frac{M}{N} on a network with N=2000N = 2000 nodes. We see that the network is capable of accurately retrieving memories whenever α<αmax⁡\alpha< \alpha_{\max}, and the accuracy degrades once α≥αmax⁡\alpha\geq\alpha_{\max}.

Overlap versus memory density for associative memory model

Figure 10. Overlap vs. memory density for associative memory model (21) with N=2000N = 2000 nodes. The dashed line corresponds to the theoretical memory capacity αmax⁡=0.042\alpha_{\max} = 0.042.

Oscillatory Associative Memory with Error-free Retrieval

We now discuss a modification to the Kuramoto associative memory model to allow for error-free retrieval [76, 77]. In this formulation we return to the setting where the memories are binary-valued, and we again denote them by ξ(1),ξ(2),…,ξ(M)∈{−1,1}N\xi^{(1)}, \xi^{(2)}, \ldots, \xi^{(M)} \in\{-1,1\}^{N}.

To derive the error-free dynamics, we consider the following energy function which modifies (19) with an additional all-to-all second order coupling term,

Eϵ(ϕ)=−12∑i=1N∑j=1NJijcos⁡(ϕj−ϕi)−ϵ4N∑i=1N∑j=1Ncos⁡(2(ϕj−ϕi))(36)E_{\epsilon}(\phi) = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}J_{ij}\cos(\phi_j-\phi_i)-\frac{\epsilon}{4N}\sum_{i=1}^{N}\sum_{j=1}^{N}\cos(2(\phi_j-\phi_i)) \tag*{(36)}

The network weights are chosen according to the standard Hebbian learning rule (17). Taking the gradient of (22) results in the retrieval dynamics

ϕ˙i=∑j=1NJijsin⁡(ϕj−ϕi)+ϵN∑j=1Nsin⁡(2(θj−θi))(37)\dot{\phi}_i = \sum_{j=1}^{N}J_{ij}\sin(\phi_j-\phi_i)+\frac{\epsilon}{N}\sum_{j=1}^{N}\sin(2(\theta_j-\theta_i)) \tag*{(37)}

For every spin configuration s∈{−1,1}Ns \in\{-1,1\}^{N}, the system (23) has a unique equilibrium ϕ∗(s)\phi^*(s) with the property that

ϕi∗(s)−ϕj∗(s)={0si=sjπsi≠sj\phi_i^*(s)-\phi_j^*(s)=\begin{cases}0 & s_i=s_j\\ \pi& s_i\ne s_j\end{cases}

As we show next, the sin⁡(2(θj−θi))\sin(2(\theta_j-\theta_i)) coupling term plays a similar role to second harmonic injection locking Oscillator Ising machines, and preferentially stabilizes equilibria corresponding to memories, ϕ∗(ξ(μ))\phi^*(\xi^{(\mu)}), while leaving arbitrary patterns unstable. Since (23) is a gradient system, the stability of an equilibrium ϕ∗(s)\phi^*(s) can be established by inspecting the Hessian of the energy function (22).

∇2Eϵ(ϕ∗(s))=L(s)+2ϵI−2ϵN1N×N\nabla^2 E_{\epsilon}(\phi^*(s)) = L(s) + 2\epsilon I - \frac{2\epsilon}{N}\mathbf{1}_{N\times N}

where L(s)L(s) is the signed graph Laplacian (13), and 1N×N\mathbf{1}_{N\times N} is the N×NN \times N matrix of ones. By [77 Theorem 2] the equilibrium ϕ∗(s)\phi^*(s) is stable if λ1(L(s))>−2ϵ\lambda_1(L(s)) > -2\epsilon, and unstable if λ1(L(s))<−2ϵ\lambda_1(L(s)) < -2\epsilon, where λ1(L(s))\lambda_1(L(s)) denotes the minimum eigenvalue of L(s)L(s).

To characterize the stability of memories and the accuracy of the memories retrieved by the system (23), we sample networks of the form (17) where M=10M = 10 and the memories are chosen uniformly at random. In Figure 11, we plot the histograms of the minimum Laplacian eigenvalues λ1(L(s))\lambda_1(L(s)), where ss is either a memory, a memory with a randomly introduced bit error, or a spin configuration sampled uniformly at random from {−1,1}N\{-1,1\}^{N}. Eigenvalues corresponding to memories are significantly larger than those corresponding to either corrupted memories or arbitrary configurations. If ϵ=0.25\epsilon= 0.25, the set of stable equilibria will consist almost exclusively of memories, in which case the system (23) is capable of nearly error-free retrieval.

Histogram of $\lambda_1(L(s))$ for randomly sampled networks

Figure 11. Histogram of λ1(L(s))\lambda_1(L(s)) for randomly sampled networks with N=1000N = 1000 nodes and M=10M = 10 memories, where ss corresponds to a memory, a memory with a random single bit error, or a spin configuration sampled uniformly at random from {−1,1}N\{-1,1\}^{N}. Only memories satisfy the stability condition λ1(L(s))>−2ϵ\lambda_1(L(s)) > -2\epsilon.

The error-free memory capacity [77 Theorem 5] of this model is Mmax⁡=2ϵ2Nlog⁡NM_{\max} = \frac{2\epsilon^2N}{\log N}. Increasing ϵ\epsilon raises the memory capacity of the network, as well as the stability margin of equilibria that correspond to memories. However, if ϵ\epsilon is too large, this may also stabilize corrupted memories and other arbitrary spin configurations. For constant ϵ\epsilon, the memory capacity scales asymptotically at the same rate as that of the classical Hopfield model.

Attention with Coupled Oscillator Networks

We discuss here the final application of oscillator networks to computing: implementing the attention mechanism, a type of neural network layer that is a fundamental component of the transformer architecture on which modern large language models (LLMs) are based. The attention mechanism operates on sequences by computing a measure of the importance of a position within an input sequence to a position in the output sequence [78, 79]. This correlation measure is expressed in terms of the similarity between encodings of the input sequence called keys and queries. Since the values corresponding to different positions can be be computed in parallel, the transformer replaced recurrent neural network architectures, which are inherently sequential, as the dominant approach to language modeling.

Transformer-based LLMs have proven to be extremely effective, enabling an explosion in artificial intelligence capabilities since their introduction. However, their biggest limitation is the massive amount of computational resources they require due to the enormous scale of AI models. Here we show that the computation performed by the attention mechanism is equivalent to the dynamics of certain higher-dimensional coupled oscillator networks. This paves the way for hardware implementations of the attention mechanism through synchronizing oscillators, a first step in the development of a new class of oscillator-based AI systems.

Self-Attention

We begin by reviewing self-attention in modern transformers. Let x1,x2,…,xT∈Rdinx_1, x_2, \ldots, x_T \in\mathbb{R}^{d_{\mathrm{in}}} be a sequence of vectors, called tokens, each of which encodes a symbol. Given matrices WK∈Rd×dinW_K \in\mathbb{R}^{d \times d_{\mathrm{in}}}, WQ∈Rd×dinW_Q \in\mathbb{R}^{d \times d_{\mathrm{in}}}, and WV∈Rd×doutW_V \in\mathbb{R}^{d \times d_{\mathrm{out}}}, which are learned from data, let ki=WKxik_i = W_Kx_i, qi=WQxiq_i = W_Qx_i, and vi=WVxiv_i = W_Vx_i be the keys, queries, and values respectively.

In the transformer architecture, the self-attention layer computes an output sequence y1,y2,…,yT∈Rdouty_1, y_2, \ldots, y_T \in\mathbb{R}^{d_{\mathrm{out}}} in terms of the values, and matrices of queries Q=[q1⋯qT]Q = [q_1 \cdots q_T] and keys K=[k1⋯kT]K = [k_1 \cdots k_T], where

yi=∑j=1Tαij(Q,K)vji=1,…,Ty_i = \sum_{j=1}^{T} \alpha_{ij}(Q,K)v_j \qquad i=1,\ldots,T

and the matrix A=(αij(Q,K))i,j=1TA = (\alpha_{ij}(Q,K))_{i,j=1}^{T} is called the attention matrix. Over the years, various attention matrices have been proposed, including

» Softmax attention [78], [79]:

αij(Q,K)=exp⁡(qiTkjd)∑ℓ=1Texp⁡(qiTkℓd).\alpha_{ij}(Q,K) = \frac{\exp\left(\frac{q_i^{\mathsf{T}}k_j}{\sqrt{d}}\right)}{\sum_{\ell=1}^{T}\exp\left(\frac{q_i^{\mathsf{T}}k_\ell}{\sqrt{d}}\right)}.

» Sigmoid attention [80]:

αij(Q,K)=11+exp⁡(−qiTkjd).\alpha_{ij}(Q,K) = \frac{1}{1+\exp\left(-\frac{q_i^{\mathsf{T}}k_j}{\sqrt{d}}\right)}.

» Linear attention [81]:

αij(Q,K)=φ(qi)Tφ(kj)∑ℓ=1Tφ(qi)Tφ(kℓ),\alpha_{ij}(Q,K) = \frac{\varphi(q_i)^{\mathsf{T}}\varphi(k_j)}{\sum_{\ell=1}^{T}\varphi(q_i)^{\mathsf{T}}\varphi(k_\ell)},

where φ:Rd→Rd\varphi:\mathbb{R}^{d}\to\mathbb{R}^{d} is a nonlinear feature map.

In each case, the weight αij(Q,K)\alpha_{ij}(Q,K) is interpreted as the importance of the jjth token of the input sequence to the iith token of the output sequence, where the importance corresponds to the relative magnitude of the inner product qiTkjq_i^{\mathsf{T}}k_j. In other words, the more the jjth key is aligned with the iith query, relative to the keys corresponding to other positions in the sequence, the more the jjth input token influences the iith output token.

Self-Attention via Coupled Oscillator Networks

We now discuss an implementation of the attention mechanism as a higher-dimensional coupled oscillator network proposed in [82]. The architecture of the system is shown in Figure 12, and is derived by drawing an analogy between the alignment of keys and queries, and the synchronization of phases in an oscillator network.

Architecture of oscillator-based implementation of the attention mechanism

Figure 12. Architecture of oscillator-based implementation of the attention mechanism. A digital front-end provides the input sequence and weights WijW_{ij}. Once the oscillator network settles to equilibrium, the digital back-end reads the attention matrix (26), and computes the output sequence (27).

Consider a bipartite network with TT free oscillators denoted z1,z2,…,zT∈Sd−1z_1,z_2,\ldots,z_T \in S^{d-1}, and TT anchors denoted r1,r2,…,rT∈Sd−1r_1,r_2,\ldots,r_T \in S^{d-1}. The values of the anchors are considered learned parameters. Let Wij=σ(βqiTkj)W_{ij}=\sigma(\beta q_i^{\mathsf{T}}k_j) denote the weight of the connecting edge between the iith free oscillator and the jjth anchor, where σ:R→R\sigma:\mathbb{R}\to\mathbb{R} is a sigmoid function, and β\beta is an inverse temperature parameter.

In the model, the anchors remain fixed while the free oscillators evolve according to

z˙i=(I−ziziT)∑j=1TWijrj(38)\dot{z}_i = (I-z_i z_i^{\mathsf{T}})\sum_{j=1}^{T}W_{ij}r_j \tag*{(38)}

This system is related to multi-agent formulations of transformers considered in [83]–[86] except that in (38) the weights are static rather than state-dependent, making it more amenable to hardware implementation.

The system (38) is a special case of the high-dimensional Kuramoto model (9), which is the projected gradient flow of the Hamiltonian of the dd-vector spin glass model (3), where the free oscillators are non-interacting, i.e. Jij=0J_{ij}=0, and the external field is

hi=∑j=1TWijrj.(39)h_i = \sum_{j=1}^{T}W_{ij}r_j. \tag*{(39)}

In other words, (38) is of the form z˙i=ΠTziSd−1(−∇ziH(z))\dot{z}_i=\Pi_{T_{z_i}S^{d-1}}(-\nabla_{z_i}H(z)), where ΠTziSd−1=I−ziziT\Pi_{T_{z_i}S^{d-1}}=I-z_i z_i^{\mathsf{T}} denotes the orthogonal projection onto the tangent space TziSd−1T_{z_i}S^{d-1}. The projection ensures that the states of the free oscillators remain on the unit sphere Sd−1S^{d-1} for all time. The system has exactly two equilibria, z∗z^* and −z∗-z^*, where

zi∗=hi∥hi∥.z_i^* = \frac{h_i}{\lVert h_i\rVert}.

Using the Hamiltonian (3) as a Lyapunov function, it can be shown that the only stable equilibrium is zi∗z_i^*, with basin of attraction Sd−1∖{−zi∗}S^{d-1}\setminus\{-z_i^*\}. Thus if the states of (38) are initialized randomly, the system will almost surely converge to the equilibrium z∗z^*.

Once the system has converged to a steady state, the attention matrix is built as

aij=1+(zi∗)Trj1+∑k=1N(zi∗)Trk(40)a_{ij} = \frac{1+(z_i^*)^{\mathsf{T}}r_j}{1+\sum_{k=1}^{N}(z_i^*)^{\mathsf{T}}r_k} \tag*{(40)}

and the output sequence is

yi=∑j=1Taijvj(41)y_i = \sum_{j=1}^{T}a_{ij}v_j \tag*{(41)}

In practical implementations, the quantity (40) is not computed but rather obtained via a measurement of the state using analog hardware. For example, in the special case where d=2d = 2, the states of the free oscillators and anchors can be written as zi∗=[cos⁡(ϕi∗),sin⁡(ϕi∗)]\boldsymbol{z}_i^* = [\cos(\phi_i^*),\sin(\phi_i^*)], and rj=[cos⁡(φj),sin⁡(φj)]\boldsymbol{r}_j = [\cos(\varphi_j),\sin(\varphi_j)], and the inner product can be expressed entirely in terms of the phase difference of oscillations (zi∗⊤rj=cos⁡(ϕi∗−φj)\boldsymbol{z}_i^{* \top}\boldsymbol{r}_j = \cos(\phi_i^*-\varphi_j)), which can be obtained via measurements of the steady-state oscillations.

In benchmark experiments [82], oscillator-based attention achieves similar performance to the standard softmax attention in [78]. Figure 13 compares the accuracy of the oscillator-based attention mechanism to the softmax attention on a keyword spotting task and subject-verb agreement task respectively. Though the classical attention has a slight advantage, experimental results suggest that hardware implementations via oscillator networks are a viable alternative.

Comparison between softmax attention and oscillator-based attention

Figure 13. Comparison between softmax attention and oscillator-based attention with d=32d = 32 on performance on benchmark tasks with different types of positional encoding of input sequences. (Top) Accuracy on keyword spotting task (Bottom) Accuracy of subject-verb agreement of predicted text.

We conclude this section by noting that the system (24) is an interpretation of the attention mechanism as a non-interacting spin glass: (24) is the projected gradient dynamics of the dd-vector Hamiltonian (3) with Jij=0J_{ij}=0, and hih_i given by (25). This motivates extensions where the free oscillators do interact with one another,

z˙i=(I−zizi⊤)(∑j=1TJijzj+∑j=1TWijrj)(42)\dot{\boldsymbol{z}}_i = \left(I-\boldsymbol{z}_i\boldsymbol{z}_i^\top\right)\left(\sum_{j=1}^{T}J_{ij}\boldsymbol{z}_j+\sum_{j=1}^{T}W_{ij}\boldsymbol{r}_j\right) \tag*{(42)}

In the case where the coupling between nodes ii and jj is ferromagnetic, i.e. Jij>0J_{ij}>0, the degree to which the output token yky_k attends to the input token xix_i is correlated with the degree it attends to the input token xjx_j, whereas if Jij<0J_{ij}<0, the levels of attention are anticorrelated. Such models of cooperative attention were studied from a statistical physics perspective in [87], where the sampling was performed using a Boltzmann machine rather than an oscillator network. It was found that adding the couplings between spins actually improves performance over the classical softmax attention, which suggests that the oscillator-based model of cooperative attention (28) may achieve similar performance gains.

Conclusion

In this survey we reviewed a paradigm of computation where information is encoded through the phases of oscillations, and computation proceeds via the dynamics of a coupled oscillator network. This approach forms an attractive alternative to digital computing since (1) oscillator networks admit a variety of physical realizations, many of which are more efficient than digital electronics and (2) analog computers can solve problems that are intractable on digital computers. The approach we develop unites the dynamics of coupled oscillator networks, statistical mechanical models of disorder in spin glasses, computational neuroscience, and theoretical computer science into a

single common framework. Within this framework, we demonstrated how oscillator networks may implement three computational primitives: solving combinatorial optimization problems, storage and retrieval of memories, and the attention mechanism, which we hope may form the basis of oscillator-based realizations of efficient and intelligent devices.

Biographies

Ahmed Allibhoy

Ahmed Allibhoy ([email protected]) Ahmed Allibhoy is currently a postdoctoral scholar at UC Irvine. He received the B.S. degree in math and electrical engineering from UCLA, and the M.S. and Ph.D. degrees in mechanical engineering from UC San Diego. His main research interests include online optimization of dynamical systems, nonsmooth dynamics, synchronization in coupled oscillator networks, and their applications to network neuroscience, systems biology, and artificial intelligence.

Fabio Pasqualetti

Fabio Pasqualetti ([email protected]) Fabio Pasqualetti is a Professor of Electrical Engineering and Computer Science at UC Irvine, where he directs the UCI Robotarium. His research sits at the intersection of dynamical systems, machine learning, and computational neuroscience. He received the B.S. degree in computer engineering, the M.S. degree in automation engineering from the University of Pisa, and the Ph.D. degree in mechanical engineering from UC Santa Barbara.

References

  1. [1]A. Pikovsky, M. Rosenblum, and J. Kurths, Synchronization: A Universal Concept in Nonlinear Sciences. Cambridge University Press, 2001.
  2. [2]S. H. Strogatz, SYNC: The Emerging Science of Spontaneous Order. Hyperion, 2003.
  3. [3]A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, “Synchronization in complex networks,” Physics Reports, vol. 469, no. 3, pp. 93–153, 2008.DOI
  4. [4]A. Winfree, The Geometry of Biological Time, 2nd ed. Springer, 2001, vol. 12.
  5. [5]L. Glass, “Synchronization and rhythmic processes in physiology,” Nature, vol. 410, no. 6825, pp. 277–284, 2001.pubmed.ncbi.nlm.nih.gov/11258383
  6. [6]J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Proceedings of the National Academy of Sciences, vol. 79, no. 8, pp. 2554–2558, 1982.
  7. [7]———, “Neurons with graded response have collective computational properties like those of two-state neurons,” Proceedings of the National Academy of Sciences, vol. 81, no. 10, pp. 3088–3092, 1984.
  8. [8]T. S. D. H. Ackley, G.E. Hinton, “A learning algorithm for Boltzmann machines,” Cognitive science, vol. 9, no. 1, pp. 147–169, 1985.
  9. [9]F. Varela, J. P. Lachaux, E. Rodriguez, and J. Martinerie, “The brain-wave phase synchronization and large-scale integration,” Nature Reviews Neuroscience, vol. 2, no. 4, pp. 229–239, 2001.DOI
  10. [10]M. Breakspear, S. Heitmann, and A. Daffertshofer, “Generative models of critical oscillations: neurobiological implications of the Kuramoto model,” Frontiers in Human Neuroscience, vol. 4, p. 190, 2010.DOI
  11. [11]X. Wang, “Neurophysiological and computational principles of cortical rhythms in cognition,” Physiological Reviews, vol. 90, no. 3, pp. 1195–1268, 2010.DOI
  12. [12]J. Fell and N. Axmacher, “The role of phase synchronization in memory processes,” Nature Reviews Neuroscience, vol. 12, no. 2, pp. 105–118, 2011.DOI
  13. [13]P. Fries, “Rhythms for cognition: Communication through coherence,” Neuron, vol. 88, pp. 220–235, 2015.DOI
  14. [14]G. Csaba, A. Raychowdhury, S. Datta, and W. Porod, “Computing with coupled oscillators: Theory, devices, and applications,” in IEEE Int. Symposium on Circuits and Systems, Florence, Italy, May 2018, pp. 1–5.DOI
  15. [15]A. Raychowdhury, A. Parihar, G. H. Smith, V. Narayanan, G. Csaba, M. Jerry, W. Porod, and S. Datta, “Computing with networks of oscillatory dynamical systems,” Proceedings of the IEEE, vol. 107, no. 1, pp. 73–89, 2019.DOI
  16. [16]G. Csaba and W. Porod, “Coupled oscillators for computing: A review and perspective,” Applied Physics Reviews, vol. 7, no. 1, p. 011302, 2020.DOI
  17. [17]K. Binder and A. P. Young, “Spin glasses: Experimental facts, theoretical concepts, and open questions,” Reviews of Modern Physics, vol. 58, no. 4, pp. 801–976, 1986.DOI
  18. [18]M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond, ser. World Scientific Lecture Notes in Physics. World Scientific, 1987, vol. 9.
  19. [19]M. Mézard and A. Montanari, Information, Physics, and Computation. Oxford University Press, 2009.DOI
  20. [20]M. Talagrand, Mean Field Models for Spin Glasses. Volume I: Basic Examples, ser. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, 2011, vol. 54.
  21. [21]J. A. Acebrón, L. L. Bonilla, C. J. P. Vicente, F. Ritort, and R. Spigler, “The Kuramoto model: A simple paradigm for synchronization phenomena,” Reviews of Modern Physics, vol. 77, no. 1, pp. 137–185, 2005.DOI
  22. [22]H. Daido, “Population dynamics of randomly interacting self-oscillators. I: Tractable models without frustration,” Progress of Theoretical Physics, vol. 77, no. 3, pp. 622–634, 1987.DOI
  23. [23]———, “Quasientrainment and slow relaxation in a population of oscillators with random and frustrated interactions,” Physical Review Letters, vol. 68, no. 7, pp. 1073–1076, 1992.
  24. [24]L. L. Bonilla, C. J. P. Vicente, and J. M. Rubí, “Glassy synchronization in a population of coupled oscillators,” Journal of Statistical Physics, vol. 70, no. 3–4, pp. 921–937, 1993.DOI
  25. [25]R. Olfati-Saber, “Swarms on sphere: A programmable swarm with synchronous behaviors like oscillator networks,” in IEEE Conf. on Decision and Control, San Diego, CA, USA, December 2006, pp. 5060–5066.
  26. [26]J. Markdahl, J. Thunberg, and J. Goncalves, “Almost global consensus on the n-sphere,” IEEE Transactions on Automatic Control, vol. 63, no. 6, pp. 1664–1675, 2018.arxiv.org/abs/1609.04885
  27. [27]S. Chandra, M. Girvan, and E. Ott, “Continuous versus discontinuous transitions in the D-dimensional generalized Kuramoto model: Odd D is different,” Physical Review X, vol. 9, no. 1, p. 011002, 2019.DOI
  28. [28]M. Lipton, R. Mirollo, and S. H. Strogatz, “The Kuramoto model on a sphere: Explaining its low-dimensional dynamics with group theory and hyperbolic geometry,” Chaos, vol. 31, no. 9, p. 093113, 2021.DOI
  29. [29]J. Markdahl, D. Proverbio, L. Mi, and J. Goncalves, “Almost global convergence to practical synchronization in the generalized Kuramoto model on networks over the n-sphere,” Communications Physics, vol. 4, no. 1, p. 187, 2021.DOI
  30. [30]M. A. Lohe, “Non-abelian Kuramoto models and synchronization,” Journal of Physics A: Mathematical and Theoretical, vol. 42, no. 39, p. 395101, 2009.DOI
  31. [31]———, “Quantum synchronization over quantum networks,” Journal of Physics A: Mathematical and Theoretical, vol. 43, no. 46, p. 465301, 2010.DOI
  32. [32]Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang, “A tutorial on energy-based learning,” Predicting structured data, 2006.
  33. [33]A. N. Montanari, F. Bullo, D. Krotov, and A. E. Motter, “Energy-based dynamical models for neurocomputation, learning, and optimization,” arXiv preprint arXiv:2604.05042, 2026.arxiv.org/abs/2604.05042
  34. [34]F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt, “An application of combinatorial optimization to statistical physics and circuit layout design,” Operations Research, vol. 36, no. 3, pp. 493–513, 1988.DOI
  35. [35]C. Arora, S. Banerjee, P. Kalra, and S. N. Maheshwari, “An efficient graph cut algorithm for computer vision problems,” in European Conference on Computer Vision, Heraklion, Greece, Sep 2010, pp. 552–565.DOI
  36. [36]J. Wang, T. Jebara, and S.-F. Chang, “Semi-supervised learning using greedy max-cut,” Journal of Machine Learning Research, vol. 14, no. 23, pp. 771–800, 2013.
  37. [37]A. Lucas, “Ising formulations of many NP problems,” Frontiers in physics, vol. 2, p. 5, 2014.
  38. [38]N. Mohseni, P. McMahon, and T. Byrnes, “Ising machines as hardware solvers of combinatorial optimization problems,” Nature Reviews Physics, vol. 4, no. 6, pp. 363–379, 2022.arxiv.org/abs/2204.00276
  39. [39]C. W. Wu, “Graph coloring via synchronization of coupled oscillators,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 45, no. 9, pp. 974–978, 1998.DOI
  40. [40]J. Wu, L. Jiao, R. Li, and W. Chen, “Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem,” Physica D: Nonlinear Phenomena, vol. 240, no. 24, pp. 1972–1978, 2011.DOI
  41. [41]A. Parihar, N. Shukla, M. Jerry, S. Datta, and A. Raychowdhury, “Vertex coloring of graphs via phase dynamics of coupled oscillatory networks,” Scientific Reports, vol. 7, no. 1, p. 911, 2017.DOI
  42. [42]M. K. Bashar, Z. Lin, and N. Shukla, “Oscillator-inspired dynamical systems to solve Boolean satisfiability,” IEEE Journal on Exploratory Solid-State Computational Devices and Circuits, vol. 9, no. 1, pp. 12–20, 2023.DOI
  43. [43]S. Dutta, A. Khanna, A. S. Assoa, H. Paik, D. G. Schlom, Z. Toroczkai, A. Raychowdhury, and S. Datta, “An Ising Hamiltonian solver based on coupled stochastic phase-transition nano-oscillators,” Nature Electronics, vol. 4, no. 7, pp. 502–512, 2021.DOI
  44. [44]J. R. T. Wang, “OIM: Oscillator-based Ising machines for solving combinatorial optimisation problems,” in International Conference on Unconventional Computation and Natural Computation. Springer, 2019, pp. 232–256.
  45. [45]Y. Cheng, M. B. Khairu, N. Shukla, and Z. Lin, “A control theoretic analysis of oscillator Ising machines,” Chaos, vol. 34, no. 7, 2024.DOI
  46. [46]A. Allihboy, A. N. Montanari, F. Pasqualetti, and A. E. Motter, “Global optimization through heterogeneous oscillator Ising machines,” in IEEE Conf. on Decision and Control, Rio de Janeiro, Brazil, 2025.
  47. [47]T. Wang, L. Wu, P. Nobel, and J. Roychowdhury, “Solving combinatorial optimisation problems using oscillator based Ising machines,” Natural Computing, vol. 20, no. 2, pp. 287–306, 2021.DOI
  48. [48]C. Altafini, “Consensus problems on networks with antagonistic interactions,” IEEE Transactions on Automatic Control, vol. 58, no. 4, pp. 935–946, 2013.DOI
  49. [49]G. Shi, C. Altafini, and J. S. Baras, “Dynamics over signed networks,” SIAM Review, vol. 61, no. 2, pp. 229–257, 2019.arxiv.org/abs/1706.03362
  50. [50]C. D. Godsil and G. F. Royle, Algebraic Graph Theory, ser. Graduate Texts in Mathematics. Springer, 2001, vol. 207.
  51. [51]F. Bullo, Lectures on Network Systems, 1st ed. Kindle Direct Publishing, 2019, with contributions by J. Cortes, F. Dorfler, and S. Martinez.
  52. [52]D. Zelazo and M. Burger, “On the robustness of uncertain consensus networks,” IEEE Transactions on Control of Network Systems, vol. 4, no. 2, pp. 170–178, 2017.
  53. [53]T. Tao, Topics in Random Matrix Theory, ser. Graduate Studies in Mathematics. American Mathematical Society, 2012, vol. 132.DOI
  54. [54]M. Potters and J.-P. Bouchaud, A First Course in Random Matrix Theory: For Physicists, Engineers and Data Scientists. Cambridge University Press, 2020.DOI
  55. [55]W. Bryc, A. Dembo, and T. Jiang, “Spectral measure of large random Hankel, Markov and Toeplitz matrices,” The Annals of Probability, vol. 34, no. 1, pp. 1–38, 2006.DOI
  56. [56]X. Ding and T. Jiang, “Spectral distributions of adjacency and Laplacian matrices of random graphs,” The Annals of Applied Probability, vol. 20, no. 6, pp. 2086–2117, 2010.
  57. [57]T. Jiang, “Empirical distributions of Laplacian matrices of large dilute random graphs,” Random Matrices: Theory and Applications, vol. 1, no. 3, p. 1250004, 2012.DOI
  58. [58]A. N. Montanari, A. Allihboy, F. Pasqualetti, and A. Motter, “Designing oscillator-based Ising machines biased toward global minimizers,” in preparation, 2026.
  59. [59]K. Nakano, “Associatron—A model of associative memory,” IEEE Transactions on Systems, Man & Cybernetics, vol. SMC-2, no. 3, pp. 380–388, 1972.DOI
  60. [60]B. Hoover, H. Strobel, D. Krotov, J. Hoffman, Z. Kira, and D. H. Chau, “Memory in plain sight: A survey of the uncanny resemblances between diffusion models and associative memories,” arXiv preprint arXiv:2309.16750, 2023.arxiv.org/abs/2309.16750
  61. [61]L. Ambrogioni, “In search of dispersed memories: Generative diffusion models are associative memory networks,” Entropy, vol. 26, no. 5, p. 381, 2024.DOI
  62. [62]H. Ramsauer, B. Schäfl, J. Lehner, P. Seidl, M. Widrich, T. Adler, L. Gruber, M. Holzleitner, M. Pavlović, G. K. Sandve, V. Greiff, D. Kreil, M. Kopp, G. Klambauer, J. Brandstetter, and S. Hochreiter, “Hopfield networks is all you need,” in International Conference for Learning Representations, Virtual, May 2021.arxiv.org/abs/2008.02217
  63. [63]B. Hoover, Y. Liang, B. Pham, R. Panda, H. Strobel, D. H. Chau, M. Zaki, and D. Krotov, “Energy transformer,” in Conference on Neural Information Processing Systems, New Orleans, LA, USA, Dec 2023, pp. 27 532–27 559.arxiv.org/abs/2302.07253
  64. [64]M. A. Cohen and S. Grossberg, “Absolute stability of global pattern formation and parallel memory storage by competitive neural networks,” IEEE Transactions on Systems, Man & Cybernetics, vol. SMC-13, no. 5, pp. 815–826, 1983.
  65. [67]S. Betteti, G. Baggio, F. Bullo, and S. Zampieri, “Firing rate models as associative memory: Synaptic design for robust retrieval,” Neural Computation, vol. 37, no. 10, pp. 1807–1838, 2025.DOI
  66. [68]J. Hertz, A. Krogh, and R. G. Palmer, Introduction to the Theory of Neural Computation, ser. Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley, 1991.
  67. [69]D. O. Hebb, The Organization of Behavior: A Neuropsychological Theory. Wiley, 1949.DOI
  68. [70]W. S. McCulloch and W. Pitts, “A logical calculus of the ideas immanent in nervous activity,” The Bulletin of Mathematical Biophysics, vol. 5, pp. 115–133, 1943.
  69. [71]A. Arenas and C. J. P. Vicente, “Phase locking in a network of neural oscillators,” Europhysics Letters, vol. 26, no. 2, pp. 79–83, 1994.DOI
  70. [72]T. Aonishi, “Phase transitions of an oscillator neural network with a standard Hebb learning rule,” Physical Review E, vol. 58, no. 4, pp. 4865–4871, 1998.
  71. [73]C. J. P. Vicente, A. Arenas, and L. L. Bonilla, “On the short-time dynamics of networks of Hebbian coupled oscillators,” Journal of Physics A: Mathematical and General, vol. 29, no. 1, pp. L9–L16, 1996.DOI
  72. [74]M. Yamana, M. Shiino, and M. Yoshioka, “Oscillator neural network model with distributed native frequencies,” Journal of Physics A: Mathematical and General, vol. 32, no. 19, pp. 3525–3533, 1999.
  73. [75]M. Yoshioka and M. Shiino, “Associative memory storing an extensive number of patterns based on a network of oscillators with distributed natural frequencies in the presence of external white noise,” Physical Review E, vol. 61, no. 5, pp. 4732–4744, 2000.pubmed.ncbi.nlm.nih.gov/11031513
  74. [76]T. Nishikawa, Y. Lai, and F. C. Hoppensteadt, “Capacity of oscillatory associative-memory networks with error-free retrieval,” Physical Review Letters, vol. 92, no. 10, p. 108101, 2004.
  75. [77]T. Nishikawa, F. Hoppensteadt, and Y. Lai, “Oscillatory associative memory network with perfect retrieval,” Physica D: Nonlinear Phenomena, vol. 197, no. 1–2, pp. 134–148, 2004.DOI
  76. [78]A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in Conference on Neural Information Processing Systems, Long Beach, CA, USA, Dec 2017, pp. 6000–6010.arxiv.org/abs/1706.03762
  77. [79]D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in International Conference for Learning Representations, San Diego, CA, USA, May 2015.
  78. [80]J. Ramapuram, F. Danieli, E. G. Dhekane, F. Weers, D. Busbridge, P. Ablin, T. Likhomanenko, J. Digani, Z. Gu, A. Shidani, and R. Webb, “Theory, analysis, and best practices for sigmoid self-attention,” in International Conference for Learning Representations, Singapore, Apr 2025, pp. 65 464–65 519.arxiv.org/abs/2409.04431
  79. [81]A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are RNNs: Fast autoregressive transformers with linear attention,” in International Conference on Machine Learning, Virtual, Jul 2020, pp. 5156–5165.arxiv.org/abs/2006.16236
  80. [82]F. Pasqualetti and T. Guo, “Attention by synchronization in coupled oscillator networks,” Transactions on Machine Learning Research, 2026.arxiv.org/abs/2606.12059
  81. [83]Y. Lu, Z. Li, D. He, Z. Sun, B. Dong, T. Qin, L. Wang, and T.-Y. Liu, “Understanding and improving transformer from a multi-particle dynamic system point of view,” arXiv preprint arXiv:1906.02762, 2019.
  82. [86]C. Altafini, “Multistability of self-attention dynamics in transformers,” IEEE Transactions on Automatic Control, vol. 71, no. 10, pp. 6582–6595, 2026.arxiv.org/abs/2511.11553
  83. [87]G. Kim and D. K. Park, “Boltzmann attention: Learnable Ising couplings for cooperative attention,” arXiv preprint arXiv:2606.12478, 2026.arxiv.org/abs/2606.12478

Paper details

vlnc:W_ew2mngr2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents