Using synchronized oscillators to compute the maximum independent set
Open Access
- 17 September 2020
- journal article
- research article
- Published by Springer Nature in Nature Communications
- Vol. 11 (1) , 1-7
Abstract
Not all computing problems are created equal. The inherent complexity of processing certain classes of problems using digital computers has inspired the exploration of alternate computing paradigms. Coupled oscillators exhibiting rich spatio-temporal dynamics have been proposed for solving hard optimization problems. However, the physical implementation of such systems has been constrained to small prototypes. Consequently, the computational properties of this paradigm remain inadequately explored. Here, we demonstrate an integrated circuit of thirty oscillators with highly reconfigurable coupling to compute optimal/near-optimal solutions to the archetypally hard Maximum Independent Set problem with over 90% accuracy. This platform uniquely enables us to characterize the dynamical and computational properties of this hardware approach. We show that the Maximum Independent Set is more challenging to compute in sparser graphs than in denser ones. Finally, using simulations we evaluate the scalability of the proposed approach. Our work marks an important step towards enabling application-specific analog computing platforms to solve computationally hard problems.Keywords
This publication has 62 references indexed in Scilit:
- Bit storage and bit flip operations in an electromechanical oscillatorNature Nanotechnology, 2008
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- Scene segmentation using neuromorphic oscillatory networksIEEE Transactions on Neural Networks, 2003
- Some massively parallel algorithms from natureWuhan University Journal of Natural Sciences, 2002
- The maximum clique problemJournal of Global Optimization, 1994
- Complexity of protein foldingBulletin of Mathematical Biology, 1993
- Computing with Arrays of Coupled Oscillators: An Application to Preattentive Texture DiscriminationNeural Computation, 1990
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding threeDiscrete Mathematics, 1988
- The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.Journal of the Operational Research Society, 1986
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982