Jiang Mingrui, Shan Keyi, He Chengping, Li Can
Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China.
Nat Commun. 2023 Sep 22;14(1):5927. doi: 10.1038/s41467-023-41647-2.
Combinatorial optimization problems are prevalent in various fields, but obtaining exact solutions remains challenging due to the combinatorial explosion with increasing problem size. Special-purpose hardware such as Ising machines, particularly memristor-based analog Ising machines, have emerged as promising solutions. However, existing simulate-annealing-based implementations have not fully exploited the inherent parallelism and analog storage/processing features of memristor crossbar arrays. This work proposes a quantum-inspired parallel annealing method that enables full parallelism and improves solution quality, resulting in significant speed and energy improvement when implemented in analog memristor crossbars. We experimentally solved tasks, including unweighted and weighted Max-Cut and traveling salesman problem, using our integrated memristor chip. The quantum-inspired parallel annealing method implemented in memristor-based hardware has demonstrated significant improvements in time- and energy-efficiency compared to previously reported simulated annealing and Ising machine implemented on other technologies. This is because our approach effectively exploits the natural parallelism, analog conductance states, and all-to-all connection provided by memristor technology, promising its potential for solving complex optimization problems with greater efficiency.
组合优化问题在各个领域普遍存在，但由于随着问题规模的增大出现组合爆炸，获得精确解仍然具有挑战性。诸如伊辛机之类的专用硬件，特别是基于忆阻器的模拟伊辛机，已成为很有前景的解决方案。然而，现有的基于模拟退火的实现方式尚未充分利用忆阻器交叉阵列固有的并行性以及模拟存储/处理特性。这项工作提出了一种受量子启发的并行退火方法，该方法能够实现完全并行并提高解的质量，当在模拟忆阻器交叉阵列中实现时，可显著提高速度和能效。我们使用集成忆阻器芯片通过实验解决了包括无权和加权最大割以及旅行商问题在内的任务。与先前报道的在其他技术上实现的模拟退火和伊辛机相比，在基于忆阻器的硬件中实现的受量子启发的并行退火方法在时间和能源效率方面已展现出显著提升。这是因为我们的方法有效地利用了忆阻器技术提供的自然并行性、模拟电导状态以及全对全连接，有望更高效地解决复杂优化问题。
