Research Center for Integrated Quantum Electronics and Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.
Amoeba Energy Co., Ltd., Fujisawa, Japan.
Sci Rep. 2020 Nov 27;10(1):20772. doi: 10.1038/s41598-020-77617-7.
Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.
组合优化需要在大量合法候选者中搜索最佳解决方案，这就需要开发一种特定于领域的计算架构，以利用物理过程的计算能力，因为传统的通用计算机的能力还不够强大。最近，执行量子退火或相关快速搜索机制的伊辛机引起了人们的关注。然而，这些机器很难将应用问题映射到它们的架构中，并且经常在非法候选者处甚至会收敛。在这里，我们展示了一种用于解决旅行商问题的模拟电子计算系统，该系统通过电流在其核心中的自发动力学模拟变形虫生物的有效觅食行为，并使用电阻交叉点电路实现了高问题映射灵活性和弹性。该系统具有很高的应用潜力，因为它可以在与问题大小成比例增长的时间内确定高质量的合法解决方案，而不会受到伊辛机弱点的影响。
