Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization
Open Access
- 2 May 2023
- journal article
- research article
- Published by Springer Nature in Nature Communications
- Vol. 14 (1) , 1-10
Abstract
Simulating physical dynamics to solve hard combinatorial optimization has proven effective for medium- to large-scale problems. The dynamics of such systems is continuous, with no guarantee of finding optimal solutions of the original discrete problem. We investigate the open question of when simulated physical solvers solve discrete optimizations correctly, with a focus on coherent Ising machines (CIMs). Having established the existence of an exact mapping between CIM dynamics and discrete Ising optimization, we report two fundamentally distinct bifurcation behaviors of the Ising dynamics at the first bifurcation point: either all nodal states simultaneously deviate from zero (synchronized bifurcation) or undergo a cascade of such deviations (retarded bifurcation). For synchronized bifurcation, we prove that when the nodal states are uniformly bounded away from the origin, they contain sufficient information for exactly solving the Ising problem. When the exact mapping conditions are violated, subsequent bifurcations become necessary and often cause slow convergence. Inspired by those findings, we devise a trapping-and-correction (TAC) technique to accelerate dynamics-based Ising solvers, including CIMs and simulated bifurcation. TAC takes advantage of early bifurcated “trapped nodes” which maintain their sign throughout the Ising dynamics to reduce computation time effectively. Using problem instances from open benchmark and random Ising models, we validate the superior convergence and accuracy of TAC.Keywords
Funding Information
- Huawei CSTT Research Grants Council of Hong Kong
This publication has 57 references indexed in Scilit:
- Coherent Ising machine based on degenerate optical parametric oscillatorsPhysical Review A, 2013
- Finding low-energy conformations of lattice protein models by quantum annealingScientific Reports, 2012
- Optimization hardness as transient chaos in an analog approach to constraint satisfactionNature Physics, 2011
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Approximation Algorithms for NP-Hard ProblemsACM SIGACT News, 1997
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A theoretical investigation into the performance of the Hopfield modelIEEE Transactions on Neural Networks, 1990
- Neurons with graded response have collective computational properties like those of two-state neurons.Proceedings of the National Academy of Sciences, 1984
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- Reducibility among Combinatorial Problems1972