Goto Hayato, Endo Kotaro, Suzuki Masaru, Sakai Yoshisato, Kanao Taro, Hamakawa Yohei, Hidaka Ryo, Yamasaki Masaya, Tatsumura Kosuke
Corporate Research and Development Center, Toshiba Corporation, 1 Komukai Toshiba-cho, Saiwai-ku, Kawasaki 212-8582, Japan.
Software Systems Research and Development Center, Toshiba Digital Solutions Corporation, 72-34 Horikawa-cho, Saiwai-ku, Kawasaki 212-8585, Japan.
Sci Adv. 2021 Feb 3;7(6). doi: 10.1126/sciadv.abe7953. Print 2021 Feb.
Quickly obtaining optimal solutions of combinatorial optimization problems has tremendous value but is extremely difficult. Thus, various kinds of machines specially designed for combinatorial optimization have recently been proposed and developed. Toward the realization of higher-performance machines, here, we propose an algorithm based on classical mechanics, which is obtained by modifying a previously proposed algorithm called simulated bifurcation. Our proposed algorithm allows us to achieve not only high speed by parallel computing but also high solution accuracy for problems with up to one million binary variables. Benchmarking shows that our machine based on the algorithm achieves high performance compared to recently developed machines, including a quantum annealer using a superconducting circuit, a coherent Ising machine using a laser, and digital processors based on various algorithms. Thus, high-performance combinatorial optimization is realized by massively parallel implementations of the proposed algorithm based on classical mechanics.
快速获得组合优化问题的最优解具有巨大价值，但极其困难。因此，最近人们提出并开发了各种专门用于组合优化的机器。为了实现更高性能的机器，在此我们提出一种基于经典力学的算法，它是通过修改先前提出的名为模拟分岔的算法得到的。我们提出的算法不仅能通过并行计算实现高速，而且对于多达一百万个二进制变量的问题也能实现高求解精度。基准测试表明，与最近开发的机器相比，我们基于该算法的机器具有高性能，这些机器包括使用超导电路的量子退火器、使用激光的相干伊辛机以及基于各种算法的数字处理器。因此，通过基于经典力学的所提出算法的大规模并行实现，实现了高性能的组合优化。
