Solving discrete optimization problems is useful in many modern applications, but they are well known for their hardness. With advances in technologies such as the Coherent Ising Machine (CIM) and Simulated Bifurcation (SB), there is an emergent interest in using physical dynamics of continuous variables to solve hard combinatorial optimizations. An important issue is whether such continuous dynamics can lead to solutions coincident with those of the discrete problem. In particular, we are interested in bifurcations of the continuous dynamics when external parameters (such as the pump rate in CIMs or SBs) are tuned, and their role in finding the optimal solution of the discrete problem. When all nodal states undergo bifurcation dynamics at the same tuning value of the external parameter, we derive sufficient conditions that the transition contains enough information for exactly solving the discrete optimization problem. When synchronous bifurcations are not possible due to frustration effects, subsequent cascades of bifurcations become necessary to reveal further details of the discrete optimization landscape. When the pump rate increases further, we derive the pump rate above which there is a guaranteed existence of the steady state of the continuous dynamics that can be binarized to map to the ground state of the discrete system. Inspired by the observation that nodes which bifurcate early tend to maintain their signs during the dynamical evolution, we devise a new trapping-and-correction (TAC) approach, which can be applied to various physical solvers, including CIMs and SBs and their variants. The proposed approach takes advantages of fixing the early bifurcated “trapped nodes” to enable updates of other nodes, effectively reducing computation time of the Ising dynamics. Using problem instances from the Biq-Mac library benchmark and random Ising models, we validated TAC approach's superior convergence and accuracy.

References
[1] Juntao Wang, Daniel Ebler, K. Y. Michael Wong, David Shui Wing Hui, and Jie Sun, Nature Communications, v. 14, May 2023, article number 2510.