Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
复制标题
DOI：
10.1126/sciadv.aav2372
复制
发表时间：
2019-04-01
期刊：
影响因子：
13.6
通讯作者：
Dixon, Alexander R.
中科院分区：
文献类型：
--
作者：
Goto, Hayato;Tatsumura, Kosuke;Dixon, Alexander R.
组合优化问题是一个普遍存在但难以求解的问题。针对这些问题的硬件设备最近已经通过各种方法开发出来，包括量子计算机。受最近提出的利用非线性振子网络的量子绝热优化的启发，我们提出了一种新的优化算法，模拟经典非线性哈密顿系统的绝热演化过程，这种绝热演化过程表现出分岔现象，我们称之为模拟分岔（SB）. SB是基于非线性哈密顿系统的绝热和混沌（遍历）演化。SB也适用于并行计算，因为它的同时更新。实施SB与现场可编程门阵列，我们证明了SB机可以获得良好的近似解决方案的所有到所有连接的2000节点MAX-CUT问题在0.5毫秒，这是约10倍的速度比一个国家的最先进的激光为基础的机器称为相干伊辛机。SB将加速利用数字计算机技术的大规模组合优化，并提供计算和数学物理的新应用。
Combinatorial optimization problems are ubiquitous but difficult to solve. Hardware devices for these problems have recently been developed by various approaches, including quantum computers. Inspired by recently proposed quantum adiabatic optimization using a nonlinear oscillator network, we propose a new optimization algorithm simulating adiabatic evolutions of classical nonlinear Hamiltonian systems exhibiting bifurcation phenomena, which we call simulated bifurcation (SB). SB is based on adiabatic and chaotic (ergodic) evolutions of nonlinear Hamiltonian systems. SB is also suitable for parallel computing because of its simultaneous updating. Implementing SB with a field-programmable gate array, we demonstrate that the SB machine can obtain good approximate solutions of an all-to-all connected 2000-node MAX-CUT problem in 0.5 ms, which is about 10 times faster than a state-of-the-art laser-based machine called a coherent Ising machine. SB will accelerate large-scale combinatorial optimization harnessing digital computer technologies and also offer a new application of computational and mathematical physics.