Improved Computation Time of Electronic Ring Oscillator Networks Compared to a Popular Classical Optimization Algorithm for the Max-Cut Problem

Time required to solve combinatorial optimization problems like Max-Cut increases exponentially with problem size. Hence, approximation algorithms like Goemans-Williamson (GW), implemented on conventional digital computers, are used to solve them approximately. However, analog systems like oscillator neural networks (ONN) (also called oscillator Ising machines (OIM)) have emerged as an alternative way to solve such problems. An electronic ring-oscillator circuit is a cheap and scalable way of implementing such an ONN. Here, we design and simulate such a ring-oscillator-based ONN with all-to-all connectivity. Consequently, we show that computation time, or time to solution (TTS), of our ONN is much lower than that of GW for Max-Cut solved on graphs of three types (Mobius ladder, random cubic, and Erdos Renyi), with the number of nodes varying from 10 to 80 at gaps of 10. In fact, we show that for ring-oscillator-based ONN, TTS almost remains constant irrespective of graph size (unlike GW, where TTS grows quadratically with graph size), while accuracy numbers of ONN and GW are comparable. This makes electronic ring oscillators attractive for solving optimization problems very fast.