Garg Neha, Singhal Sanyam, Aggarwal Nakul, Sadashiva Aniket, Muduli Pranaba K, Bhowmik Debanjan
Department of Physics, Indian Institute of Technology Delhi, New Delhi, Delhi 110016, India.
Department of Physics, Indian Institute of Technology Bombay, Mumbai, Maharashtra 400076, India.
Nanotechnology. 2024 Aug 28;35(46). doi: 10.1088/1361-6528/ad6f18.
Solving certain combinatorial optimization problems like Max-Cut becomes challenging once the graph size and edge connectivity increase beyond a threshold, with brute-force algorithms which solve such problems exactly on conventional digital computers having the bottleneck of exponential time complexity. Hence currently, such problems are instead solved approximately using algorithms like Goemans-Williamson (GW) algorithm, run on conventional computers with polynomial time complexity. Phase binarized oscillators (PBOs), also often known as oscillator Ising machines, have been proposed as an alternative to solve such problems. In this paper, restricting ourselves to the combinatorial optimization problem Max-Cut solved on three kinds of graphs (Mobius Ladder, random cubic, Erdös Rényi) up to 100 nodes, we empirically show that computation time/time to solution (TTS) for PBOs (captured through Kuramoto model) grows at a much lower rate (logarithmically:O(log(N)), with respect to graph size) compared to GW algorithm, for which TTS increases as square of graph size (O()). However, Kuramoto model being a physics-agnostic mathematical model, this time complexity/ TTS trend for PBOs is a general trend and is device-physics agnostic. So for more specific results, we choose spintronic oscillators, known for their high operating frequency (in GHz), and model them through Slavin's model which captures the physics of their coupled magnetization oscillation dynamics. We thereby empirically show that TTS of spintronic oscillators also grows logarithmically with graph size (O(log(N)), while their accuracy is comparable to that of GW. So spintronic oscillators have improved time complexity over GW algorithm. For large graphs, they are expected to compute Max-Cut values much faster than GW algorithm, as well as other oscillators operating at lower frequencies, while maintaining the same level of accuracy.
一旦图的规模和边连通性增加到超过某个阈值，解决某些组合优化问题（如最大割问题）就会变得具有挑战性，因为在传统数字计算机上精确解决此类问题的暴力算法存在指数时间复杂度的瓶颈。因此，目前此类问题改为使用具有多项式时间复杂度的算法（如戈曼斯 - 威廉姆森（GW）算法）在传统计算机上近似求解。相位二值化振荡器（PBO），通常也称为振荡器伊辛机，已被提出作为解决此类问题的一种替代方案。在本文中，我们将研究限制在对三种图（莫比乌斯梯子图、随机立方图、厄多斯 - 雷尼图）上解决的组合优化问题最大割，图的节点数最多为100个。我们通过实验表明，与GW算法相比，PBO（通过库拉托莫模型捕获）的计算时间/求解时间（TTS）增长速率要低得多（对数增长：O(log(N))，相对于图的规模），而GW算法的TTS随着图规模的平方增加（O()）。然而，库拉托莫模型是一个与物理无关的数学模型，PBO的这种时间复杂度/TTS趋势是一个普遍趋势，与器件物理无关。因此，为了获得更具体的结果，我们选择以其高工作频率（GHz）而闻名的自旋电子振荡器，并通过斯拉文模型对其进行建模该模型捕获了它们耦合磁化振荡动力学的物理特性。我们通过实验表明，自旋电子振荡器的TTS也随图规模对数增长（O(log(N))），同时其精度与GW算法相当。因此，自旋电子振荡器相对于GW算法具有改进的时间复杂度。对于大型图，预计它们计算最大割值的速度比GW算法以及其他工作频率较低的振荡器要快得多，同时保持相同的精度水平。
