An official website of the United States government
Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms.
more »
« less
Cardiac Muscle Cell‐Based Coupled Oscillator Network for Collective Computing
Current rate of data generation and the need for real‐time data analytics can benefit from new computational approaches where computation proceeds in a massively parallel way while being scalable and energy efficient. Biological systems arising from interaction of living cells can provide such pathways for sustainable computing. Current designs for biocomputing leveraging the information processing units of the cells, such as DNA, gene, or protein circuitries, are inherently slow (hours to days speed) and, therefore, are primarily being considered for archival storage of information. On the contrary, electrically active cells that can synchronize in milliseconds and can be connected as networks to perform massively parallel tasks can transform biocomputing and lead to novel ways of high throughput information processing. Herein, coupled oscillator networks made of living cardiac muscle cells, or bio‐oscillators, is explored as collective computing components for solving computationally hard problems. An empirically validated circuit compatible macromodel is developed for the bio‐oscillators and the fibroblast cells acting as coupling elements, to faithfully reproduce the synchronization dynamics of the network and it is shown that such bio‐oscillator network can be scaled up to hundreds of nodes and be used to solve computationally hard problems faster than traditional heuristics‐based Boolean algorithms.
more »
« less
- Award ID(s):
- 1807551
- PAR ID:
- 10210210
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Advanced Intelligent Systems
- Volume:
- 3
- Issue:
- 4
- ISSN:
- 2640-4567
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Coupled electronic oscillators have recently been explored as a compact, integrated circuit- and room temperature operation-compatible hardware platform to design Ising machines. However, such implementations presently require the injection of an externally generated second-harmonic signal to impose the phase bipartition among the oscillators. In this work, we experimentally demonstrate a new electronic autaptic oscillator (EAO) that uses engineered feedback to eliminate the need for the generation and injection of the external second harmonic signal to minimize the Ising Hamiltonian. Unlike conventional relaxation oscillators that typically decay with a single time constant, the feedback in the EAO is engineered to generate two decay time constants which effectively helps generate the second harmonic signal internally. Using this oscillator design, we show experimentally, that a system of capacitively coupled EAOs exhibits the desired bipartition in the oscillator phases without the need for any external second harmonic injection, and subsequently, demonstrate its application in solving the computationally hard Maximum Cut (MaxCut) problem. Our work not only establishes a new oscillator design aligned to the needs of the oscillator Ising machine but also advances the efforts to creating application specific analog computing platforms.more » « less
-
Abstract Combinatorial optimization problems are difficult to solve with conventional algorithms. Here we explore networks of nonlinear electronic oscillators evolving dynamically towards the solution to such problems. We show that when driven into subharmonic response, such oscillator networks can minimize the Ising Hamiltonian on non-trivial antiferromagnetically-coupled 3-regular graphs. In this context, the spin-up and spin-down states of the Ising machine are represented by the oscillators’ response at the even or odd driving cycles. Our experimental setting of driven nonlinear oscillators coupled via a programmable switch matrix leads to a unique energy minimizer when one exists, and probes frustration where appropriate. Theoretical modeling of the electronic oscillators and their couplings allows us to accurately reproduce the qualitative features of the experimental results and extends the results to larger graphs. This suggests the promise of this setup as a prototypical one for exploring the capabilities of such an unconventional computing platform.more » « less
-
BackgroundSelf‐sustained oscillations are a ubiquitous and vital phenomenon in living systems. From primitive single‐cellular bacteria to the most sophisticated organisms, periodicities have been observed in a broad spectrum of biological processes such as neuron firing, heart beats, cell cycles, circadian rhythms, etc. Defects in these oscillators can cause diseases from insomnia to cancer. Elucidating their fundamental mechanisms is of great significance to diseases, and yet challenging, due to the complexity and diversity of these oscillators. ResultsApproaches in quantitative systems biology and synthetic biology have been most effective by simplifying the systems to contain only the most essential regulators. Here, we will review major progress that has been made in understanding biological oscillators using these approaches. The quantitative systems biology approach allows for identification of the essential components of an oscillator in an endogenous system. The synthetic biology approach makes use of the knowledge to design the simplest,de novooscillators in both live cells and cell‐free systems. These synthetic oscillators are tractable to further detailed analysis and manipulations. ConclusionWith the recent development of biological and computational tools, both approaches have made significant achievements.more » « less
-
Abstract The rich non‐linear dynamics of the coupled oscillators (under second harmonic injection) can be leveraged to solve computationally hard problems in combinatorial optimization such as finding the ground state of the Ising Hamiltonian. While prior work on the stability of the so‐called Oscillator Ising Machines (OIMs) has used the linearization method, in this letter, the authors present a complementary method to analyze stability using the second‐order derivative test of the energy/cost function. The authors establish the equivalence between the two methods, thus augmenting the tool kit for the design and implementation of OIMs.more » « less
