Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem
Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem
复制标题
DOI：
10.1109/jxcdc.2020.3025994
复制
发表时间：
2020-12-01
影响因子：
2.4
通讯作者：
Shukla, Nikhil
中科院分区：
文献类型：
--
作者：
Bashar, Mohammad Khairul;Mallick, Antik;Shukla, Nikhil
在这项工作中，我们通过实验证明了一个由30个弛豫振荡器组成的集成电路（IC），具有可重构电容耦合，以解决NP-Hard最大切割（Max-Cut）问题。我们证明了在外部二次谐波注入信号的影响下，振荡器相位表现出一种可用于计算高质量近似Max-Cut解的双分频。利用全可重构耦合架构，我们使用随机生成的不同大小和边缘密度（eta）的图实例来实验评估振荡器的计算特性。此外，将Max-Cut解与最优值进行比较，我们发现振荡器（经过简单的后处理）在36个测量图中的28个图中产生的Max-Cut在最优值的99%以内；重要的是，振荡器在密集图中特别有效，在eta = 0.8的9个测量图中有7个图的Max-Cut是最优的。我们的工作标志着朝着创建一个高效的，室温兼容的非布尔硬件求解器的硬组合优化问题迈出了一步。
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 showthat under the infiuence 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 allto-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, roomtemperature-compatible non-Boolean hardware-based solver for hard combinatorial optimization problems.