ROC-Spin: A 28nm 2,000 Ring-Oscillator-Collapse Spins for Solving Combinatorial Optimization Problems

Emerging computer based on quantum [1] or CMOS technologies [2 –5] has gained attention as an alternative for solving non-deterministic polynomial-time hard combinatorial optimization problems (COPs) intractable using classical computers. Among them, oscillator-based Ising chips [3–4] demonstrated cost-effective, massively parallel, scalable, and energy efficient solutions. Such Ising chips implemented a two-dimensional (2-D) array of spins through a network of coupled ring oscillators where their spin states are represented by the oscillation phases. The oscillator-based spins naturally find their minimum energy states, where the oscillators are synchronized to the same (in-phase) or the opposite (out-of-phase) oscillation phase. However, the phase-based spin interactions could degrade the accuracy of solutions due to a complex phase readout circuitry, which is prone to errors, and lead to a significant hardware overhead. To mitigate these issues, this work proposes a novel ring-oscillator-collapse (ROC) spin circuit, where a duty cycle of its output clock represents spin state. For instance, a 100% duty-cycle (or DC high) represents spin-up, a 0% duty-cycle (DC low) represents spin-down. A duty cycle between 0% and 100% represents a superposed state, which will eventually collapses to either a DC high (spin-up) or low (spin-down) as a result of interactions between ROC spins. The collapsed spin states (a DC high or low) are read out using a simple digital read circuit with minimal error and area overhead. A 28 nm test chip with 2,000 ROC spins demonstrated 0.1% error rate and $3-50 \mathrm{~ns}$ time-to-solution (TTS) for solving max-cut problems.