Ring oscillator

Algorithm

Electrical engineering

Physics

Mathematical optimization

Engineering

Optimization problem

Voltage

Topology (electrical circuits)

Mathematics

Computer science

Scalability

Ising model

Combinatorial optimization

Quantum mechanics

Node (physics)

Database

Nature Electronics

Computational architectures that are optimized to solve non-deterministic polynomial-time hard or complete problems are of use in the development of machine learning, logistical planning and pathfinding. A range of quantum-, optical- and spintronic-based approaches have been explored for solving such combinatorial optimization problems, but they remain complicated to build and to scale. Here we report a scalable ring-oscillator-based integrated circuit for optimization problem solving. Our 1,968-node King’s graph ring oscillator array has five levels of coupling strengths and can achieve up to 95% accuracy for randomly generated combinatorial optimization problems. The measured average power consumption of the Ising chip is 0.042 W and it takes less than 50 oscillation cycles to resolve to the ground state. Our device is resilient to environmental and variation effects. By using a multi-phase phase measurement circuit, we also capture the true phase behaviour within a coupled-oscillator integrated circuit. A coupled ring-oscillator-based integrated circuit with 1,968 nodes can be used to efficiently solve combinatorial optimization problems with an accuracy of up to 95%.

A 1,968-node coupled ring oscillator circuit for combinatorial optimization problem solving