Leleu Timothée, Yamamoto Yoshihisa, Utsunomiya Shoko, Aihara Kazuyuki
Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan.
ImPACT program, The Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan.
Phys Rev E. 2017 Feb;95(2-1):022118. doi: 10.1103/PhysRevE.95.022118. Epub 2017 Feb 14.
The dynamics of driven-dissipative systems is shown to be well-fitted for achieving efficient combinatorial optimization. The proposed method can be applied to solve any combinatorial optimization problem that is equivalent to minimizing an Ising Hamiltonian. Moreover, the dynamics considered can be implemented using various physical systems as it is based on generic dynamics-the normal form of the supercritical pitchfork bifurcation. The computational principle of the proposed method relies on an hybrid analog-digital representation of the binary Ising spins by considering the gradient descent of a Lyapunov function that is the sum of an analog Ising Hamiltonian and archetypal single or double-well potentials. By gradually changing the shape of the latter potentials from a single to double well shape, it can be shown that the first nonzero steady states to become stable are associated with global minima of the Ising Hamiltonian, under the approximation that all analog spins have the same amplitude. In the more general case, the heterogeneity in amplitude between analog spins induces the stabilization of local minima, which reduces the quality of solutions to combinatorial optimization problems. However, we show that the heterogeneity in amplitude can be reduced by setting the parameters of the driving signal near a regime, called the dynamic phase transition, where the analog spins' DC components map more accurately the global minima of the Ising Hamiltonian which, in turn, increases the quality of solutions found. Last, we discuss the possibility of a physical implementation of the proposed method using networks of degenerate optical parametric oscillators.
结果表明，驱动耗散系统的动力学非常适合实现高效的组合优化。所提出的方法可应用于解决任何等同于最小化伊辛哈密顿量的组合优化问题。此外，由于所考虑的动力学基于通用动力学——超临界叉形分岔的范式，因此可以使用各种物理系统来实现。所提出方法的计算原理依赖于通过考虑作为模拟伊辛哈密顿量与典型单阱或双阱势之和的李雅普诺夫函数的梯度下降，对二元伊辛自旋进行混合模拟 - 数字表示。通过逐渐将后者势的形状从单阱变为双阱形状，可以证明，在所有模拟自旋具有相同幅度的近似下，第一个变得稳定的非零稳态与伊辛哈密顿量的全局最小值相关。在更一般的情况下，模拟自旋之间幅度的不均匀性会导致局部最小值的稳定，这会降低组合优化问题的解的质量。然而，我们表明，通过将驱动信号的参数设置在一个称为动态相变的区域附近，可以减少幅度的不均匀性，在该区域中，模拟自旋的直流分量更准确地映射伊辛哈密顿量的全局最小值，进而提高找到的解的质量。最后，我们讨论了使用简并光学参量振荡器网络对所提出方法进行物理实现的可能性。
