Solving Hard Computational Problems using Oscillator Networks

Seminar | May 1 | 4-5:30 p.m. | 560 Evans Hall

 Tianshi Wang, EECS, UC Berkeley

 Neuroscience Institute, Helen Wills

Over the last few years, there has been considerable interest in Ising machines, ie, analog hardware for solving difficult (NP hard/complete) computational problems effectively. We present a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. Our scheme is theoretically rooted in a novel result that connects the phase dynamics of coupled oscillator systems with the Ising Hamiltonian. We show that the dynamics of appropriately-designed oscillator networks evolve naturally towards local minima of the Ising Hamiltonian. Two simple additional steps (ie, adding noise, and turning sub-harmonic locking on and off smoothly) enable the network to find very good solutions of Ising problems. We evaluate our method on Ising versions of the MAX-CUT problem, showing that it performs excellently on many benchmark problems.

Our scheme, which is amenable to realization using many kinds of oscillators from different physical domains, is particularly well suited for CMOS, in which it offers significant practical advantages over previous techniques for making Ising machines. We have demonstrated several working hardware prototypes using CMOS electronic oscillators, built on breadboards/perfboards and PCBs, implementing Ising machines consisting of up to 240 spins with programmable couplings.