Using synchronized oscillators to compute the maximum independent set

Antik Mallick1, Mohammad Khairul Bashar1, Daniel S Truesdell1

  • 1Department of Electrical and Computer Engineering, University of Virginia, Charlottesville, VA, 22904, USA.

Nature Communications
|September 18, 2020
PubMed
Summary

This study demonstrates a 30-oscillator analog computing circuit that solves complex Maximum Independent Set problems with over 90% accuracy. This analog approach shows promise for tackling computationally hard problems intractable for digital computers.

Related Concept Videos

Oscillations about an Equilibrium Position01:04

Oscillations about an Equilibrium Position

Stability is an important concept in oscillation. If an equilibrium point is stable, a slight disturbance of an object that is initially at the stable equilibrium point will cause the object to oscillate around that point. For an unstable equilibrium point, if the object is disturbed slightly, it will not return to the equilibrium point. There are three conditions for equilibrium points—stable, unstable, and half-stable. A half-stable equilibrium point is also unstable, but is named so...
6.4K
Alternative Sets of Equilibrium Equations01:31

Alternative Sets of Equilibrium Equations

When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
812
Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
11.0K
Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
12.2K
Forced Oscillations01:06

Forced Oscillations

When an oscillator is forced with a periodic driving force, the motion may seem chaotic. The motions of such oscillators are known as transients. After the transients die out, the oscillator reaches a steady state, where the motion is periodic, and the displacement is determined.
7.4K
Simplified Synchronous Machine Model01:30

Simplified Synchronous Machine Model

The Synchronous Machine Model is a fundamental tool in analyzing and ensuring the transient stability of power systems. This model simplifies the representation of a synchronous machine under balanced three-phase positive-sequence conditions, assuming constant excitation and ignoring losses and saturation. The model is pivotal for understanding the behavior of synchronous generators connected to a power grid, particularly during transient events.
In this model, each generator is connected to a...
619