Solving combinatorial optimisation problems using oscillator based Ising machines
Solving combinatorial optimisation problems using oscillator based Ising machines
复制标题
DOI：
10.1007/s11047-021-09845-3
复制
发表时间：
2021-05-05
影响因子：
2.1
通讯作者：
Roychowdhury, Jaijeet
中科院分区：
文献类型：
--
作者：
Wang, Tianshi;Wu, Leon;Roychowdhury, Jaijeet
我们提出了一种利用耦合自维持非线性振子网络来制造振子机的新方法OIM （Oscillator Ising Machines）。OIM理论植根于一个新的结果，即在次谐波注入锁定的影响下，耦合振荡器系统的相位动力学由与耦合图的伊辛哈密顿量密切相关的李雅普诺夫函数控制。结果，这种振荡器网络的动力学自然地演化到李雅普诺夫函数的局部极小值。两个简单的附加步骤（即平稳地打开和关闭次谐波锁定，以及添加噪声）使网络能够找到伊辛问题的优秀解决方案。我们在MAX-CUT和图形着色问题的Ising版本上展示了我们的方法，表明它在G基准集中的几个问题上改进了先前发表的结果。利用已知全局最小值的合成问题，我们也给出了初始标度结果。我们的方案可以使用来自不同物理域的多种振荡器来实现，特别适合CMOS IC实现，与以前的制造Ising机器的技术相比，具有显着的实际优势。我们报告了使用CMOS电子振荡器的工作硬件原型。
We present OIM (Oscillator Ising Machines), a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. OIM is theoretically rooted in a novel result that establishes that the phase dynamics of coupled oscillator systems, under the influence of subharmonic injection locking, are governed by a Lyapunov function that is closely related to the Ising Hamiltonian of the coupling graph. As a result, the dynamics of such oscillator networks evolve naturally to local minima of the Lyapunov function. Two simple additional steps (i.e., turning subharmonic locking on and off smoothly, and adding noise) enable the network to find excellent solutions of Ising problems. We demonstrate our method on Ising versions of the MAX-CUT and graph colouring problems, showing that it improves on previously published results on several problems in the G benchmark set. Using synthetic problems with known global minima, we also present initial scaling results. Our scheme, which is amenable to realisation using many kinds of oscillators from different physical domains, is particularly well suited for CMOS IC implementation, offering significant practical advantages over previous techniques for making Ising machines. We report working hardware prototypes using CMOS electronic oscillators.