Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem

摘要: 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 influence external second-harmonic injection signal, oscillator phases exhibit a bi-partition which can be used calculate high quality approximate Max-Cut solution. Leveraging all-to-all architecture, evaluate computational properties using randomly generated graph instances varying size and edge density . Further, comparing solutions optimal values, (after simple post-processing) produce is within 99% value in 28 36 measured graphs; importantly, are particularly effective dense graphs being seven out nine 0.8. Our work marks step towards creating efficient, room-temperature-compatible non-Boolean hardware-based solver for hard combinatorial optimization problems.