Overcoming the Accuracy vs. Performance Trade-off in Oscillator Ising Machines
Overcoming the Accuracy vs. Performance Trade-off in Oscillator Ising Machines
复制标题
克服振荡器吊机的精度与性能之间的权衡
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
N. Shukla
中科院分区：
文献类型：
--
作者：
A. Mallick;M. K. Bashar;D. Truesdell;B. Calhoun;N. Shukla
基于耦合振荡器的伊辛机器提供了一种有效的基于随机搜索的方法来解决NP-hard组合优化问题（这里考虑的最大切割问题），这些问题使用传统计算机计算成本很高。在这里，我们测量了一个基于600个振荡器的Ising机器，其中包含bbb29,000个可编程耦合元件。使用该平台，我们通过实验揭示了解决方案质量和计算时间之间的基本权衡，与数字算法相比，这可能会限制Ising机器的准确性和性能。此外，我们还证明了该解对图的大小和稀疏度高度敏感。为了克服这些限制，我们提出了一种混合方法，该方法使用振荡器伊辛机获得接近最优的解决方案（非常快），然后使用简单的局部搜索算法对其进行改进，并具有最小的时间惩罚。我们的混合方法：(i)在给定时间内产生比基于独立振荡器的硬件更好的质量解决方案；（ii）与数字算法（流形优化，在具有256GB RAM的32核处理器上执行）相比，在等解质量下实验测量的计算时间提高了3-100倍；（iii）表现出对图的输入属性的最小灵敏度（<2%）。我们的工作为克服振荡器Ising机器的性能与质量权衡提供了一条途径，随后，在保持高精度的同时加速困难的组合问题。
Coupled oscillator-based Ising machines offer an efficient stochastic search-based approach to solve NP-hard combinatorial optimization problems (Maximum Cut problem considered here) that are computationally expensive to solve using traditional computers. Here, we measure a 600 oscillator-based Ising machine with >29,000 programmable coupling elements. Using this platform, we experimentally reveal a fundamental trade-off between the solution quality and the time-to-compute, which can limit the accuracy & performance of the Ising machine in comparison to digital algorithms. Furthermore, we also show that the solution is highly sensitive to the size and the sparsity of graph. To overcome these limitations, we propose a hybrid approach that uses the oscillator Ising machine to obtain near-optimal solutions (extremely fast), which are then subsequently improved using a simple local-search algorithm with minimum time penalty. Our hybrid approach: (i) produces better quality solutions than stand-alone oscillator-based hardware in a given time; (ii) shows 3-100× improvement in experimentally measured time-to-compute at iso-solution quality, when compared to a digital algorithm (manifold optimization, executed on a 32-core processor with 256GB RAM); (iii) shows minimal sensitivity (<2%) in performance to the input properties of the graph. Our work provides a pathway to overcome the performance vs. quality tradeoff in oscillator Ising machines, and subsequently, accelerate hard combinatorial problems while maintaining high accuracy.