Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization

Juntao Wang, Daniel Ebler (), K. Y. Michael Wong, David Shui Wing Hui and Jie Sun ()
Additional contact information
Juntao Wang: Huawei Technologies Co. Ltd.
Daniel Ebler: Huawei Technologies Co. Ltd.
K. Y. Michael Wong: Hong Kong University of Science and Technology
David Shui Wing Hui: Huawei Technologies Co. Ltd.
Jie Sun: Huawei Technologies Co. Ltd.

Nature Communications, 2023, vol. 14, issue 1, 1-10

Abstract: 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.

Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-023-37695-3 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-37695-3

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-023-37695-3

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().