Computing with oscillators from theoretical underpinnings to applications and demonstrators

Networks of coupled oscillators have far-reaching implications across various fields, providing insights into a plethora of dynamics. This review offers an in-depth overview of computing with oscillators covering computational capability, synchronization occurrence and mathematical formalism. We discuss numerous circuit design implementations, technology choices and applications from pattern retrieval, combinatorial optimization problems to machine learning algorithms. We also outline perspectives to broaden the applications and mathematical understanding of coupled oscillator dynamics.

Design of oscillatory neural networks by machine learning

We demonstrate the utility of machine learning algorithms for the design of oscillatory neural networks (ONNs). After constructing a circuit model of the oscillators in a machine-learning-enabled simulator and performing Backpropagation through time (BPTT) for determining the coupling resistances between the ring oscillators, we demonstrate the design of associative memories and multi-layered ONN classifiers. The machine-learning-designed ONNs show superior performance compared to other design methods (such as Hebbian learning), and they also enable significant simplifications in the circuit topology. We also demonstrate the design of multi-layered ONNs that show superior performance compared to single-layer ones. We argue that machine learning can be a valuable tool to unlock the true computing potential of ONNs hardware.

A global synchronization theorem for oscillators on a random graph

Consider n identical Kuramoto oscillators on a random graph. Specifically, consider Erdős-Rényi random graphs in which any two oscillators are bidirectionally coupled with unit strength, independently and at random, with probability 0 ≤ p ≤ 1. We say that a network is globally synchronizing if the oscillators converge to the all-in-phase synchronous state for almost all initial conditions. Is there a critical threshold for p above which global synchrony is extremely likely but below which it is extremely rare? It is suspected that a critical threshold exists and is close to the so-called connectivity threshold, namely, p ∼ log ⁡ ( n ) / n for n ≫ 1. Ling, Xu, and Bandeira made the first progress toward proving a result in this direction: they showed that if p ≫ log ⁡ ( n ) / ⁿ, then Erdős-Rényi networks of Kuramoto oscillators are globally synchronizing with high probability as n → ∞. Here, we improve that result by showing that p ≫ ^log ⁡ ( n ) / n suffices. Our estimates are explicit: for example, we can say that there is more than a 99.9996 % chance that a random network with n = ¹⁰ and p > 0.011 17 is globally synchronizing.

Graph Coloring via Locally-Active Memristor Oscillatory Networks

This manuscript provides a comprehensive tutorial on the operating principles of a bio-inspired Cellular Nonlinear Network, leveraging the local activity of NbOx memristors to apply a spike-based computing paradigm, which is expected to deliver such a separation between the steady-state phases of its capacitively-coupled oscillators, relative to a reference cell, as to unveal the classification of the nodes of the associated graphs into the least number of groups, according to the rules of a non-deterministic polynomial-hard combinatorial optimization problem, known as vertex coloring. Besides providing the theoretical foundations of the bio-inspired signal-processing paradigm, implemented by the proposed Memristor Oscillatory Network, and presenting pedagogical examples, illustrating how the phase dynamics of the memristive computing engine enables to solve the graph coloring problem, the paper further presents strategies to compensate for an imbalance in the number of couplings per oscillator, to counteract the intrinsic variability observed in the electrical behaviours of memristor samples from the same batch, and to prevent the impasse appearing when the array attains a steady-state corresponding to a local minimum of the optimization goal. The proposed Memristor Cellular Nonlinear Network, endowed with ad hoc circuitry for the implementation of these control strategies, is found to classify the vertices of a wide set of graphs in a number of color groups lower than the cardinality of the set of colors identified by traditional either software or hardware competitor systems. Given that, under nominal operating conditions, a biological system, such as the brain, is naturally capable to optimise energy consumption in problem-solving activities, the capability of locally-active memristor nanotechnologies to enable the circuit implementation of bio-inspired signal processing paradigms is expected to pave the way toward electronics with higher time and energy efficiency than state-of-the-art purely-CMOS hardware.

Collective dynamics of phase-repulsive oscillators solves graph coloring problem

We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO2) to efficiently solve vertex coloring of graphs. Pairwise coupled VO2 oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO2 oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO2 oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.

Energy function-based approaches to graph coloring

We describe an approach to optimization based on a multiple-restart quasi-Hopfield network where the only problem-specific knowledge is embedded in the energy function that the algorithm tries to minimize. We apply this method to three different variants of the graph coloring problem: the minimum coloring problem, the spanning subgraph k-coloring problem, and the induced subgraph k-coloring problem. Though Hopfield networks have been applied in the past to the minimum coloring problem, our encoding is more natural and compact than almost all previous ones. In particular, we use k-state neurons while almost all previous approaches use binary neurons. This reduces the number of connections in the network from (Nk)(2) to N(2) asymptotically and also circumvents a problem in earlier approaches, that of multiple colors being assigned to a single vertex. Experimental results show that our approach compares favorably with other algorithms, even nonneural ones specifically developed for the graph coloring problem.