1. Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem
- Author
-
Mohammad Khairul Bashar, Siddharth Joshi, Daniel S. Truesdell, Antik Mallick, Nikhil Shukla, and Benton H. Calhoun
- Subjects
FOS: Computer and information sciences ,Ising machines ,lcsh:Computer engineering. Computer hardware ,Computer science ,Maximum cut ,FOS: Physical sciences ,Computer Science - Emerging Technologies ,lcsh:TK7885-7895 ,Applied Physics (physics.app-ph) ,Hardware_PERFORMANCEANDRELIABILITY ,Integrated circuit ,Topology ,01 natural sciences ,coupled oscillators ,law.invention ,03 medical and health sciences ,law ,0103 physical sciences ,Electrical and Electronic Engineering ,030304 developmental biology ,010302 applied physics ,Capacitive coupling ,Coupling ,0303 health sciences ,Relaxation oscillator ,Analog ,Combinatorial optimization problem ,Physics - Applied Physics ,Solver ,Electronic, Optical and Magnetic Materials ,Capacitor ,Emerging Technologies (cs.ET) ,maximum cut (Max-Cut) ,integrated circuit (IC) ,Hardware and Architecture - Abstract
In this work, we experimentally demonstrate an integrated circuit (IC) of 30 relaxation oscillators with reconfigurable capacitive coupling to solve the NP-Hard maximum cut (Max-Cut) problem. We show that under the influence of an external second-harmonic injection signal, the oscillator phases exhibit a bipartition that can be used to calculate a high-quality approximate Max-Cut solution. Leveraging the all-to-all reconfigurable coupling architecture, we experimentally evaluate the computational properties of the oscillators using randomly generated graph instances of varying size and edge density ( $\eta $ ). Furthermore, comparing the Max-Cut solutions with the optimal values, we show that the oscillators (after simple postprocessing) produce a Max-Cut that is within 99% of the optimal value in 28 of the 36 measured graphs; importantly, the oscillators are particularly effective in dense graphs with the Max-Cut being optimal in seven out of nine measured graphs with $\eta =0.8$ . Our work marks a step toward creating an efficient, room-temperature-compatible non-Boolean hardware-based solver for hard combinatorial optimization problems.
- Published
- 2020
- Full Text
- View/download PDF