Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Nature Communications

Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization

Juntao Wang, Daniel Ebler, K. Y. Michael Wong, David Shui Wing Hui, Jie Sun

Published May 2, 2023• 30 citations
Publisher

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.

DOI
10.1038/s41467-023-37695-3

Related papers

Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization

Junpeng Hou, Amin Barzegar, Helmut G. Katzgraber

Combinatorial optimization problems are ubiquitous in industrial applications. However, finding optimal or close-to-optimal solutions can often be extremely hard. Because some of these problems can be mapped to the ground-state search of the Ising model, tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms such as quantum simulators and coherent Ising machines to tackle hard optimization problems. Here, we examine and benchmark several physics-inspired optimization algorithms, including coherent Ising machines, gain-dissipative algorithms, simulated bifurcation machines, and Hopfield neural networks, which we collectively refer to as stochastic driven nonlinear dynamical systems. Most importantly, we benchmark these algorithms against random Ising problems with planted solutions and compare them to simulated annealing as a baseline leveraging the same software stack for all solvers. We further study how different numerical integration techniques and graph connectivity affect performance. This work provides an overview of a diverse set of new optimization paradigms.

arXiv:2503.15427•Physical review. E•Jul 1, 2025•1 citation

Quantized Simulated Bifurcation for the Ising Model

Tingting Zhang, Jie Han

Developed from the Ising model, Ising machines are promising to be efficient domain-specific accelerators for solving combinatorial optimization problems (COPs). A simulated bifurcation (SB) algorithm enables an Ising machine to achieve massive parallelism in the simulation of Hamiltonian dynamics. Although SB significantly accelerates the search, more resources are required due to the use of continuous variables for the position of oscillators to obtain discrete spin states, compared to conventional simulated annealing. This article proposes ternary and multiple-value quantized SB (qSB) algorithms by discretizing the position variables used for the hardware-consuming multiply-accumulate (MAC) operations in SB. These quantization schemes do not only reduce the computational complexity, but also improve the solution quality for COPs. Specifically, the ternary qSB with dynamic threshold settings converts the MAC into addition and subtraction. To improve the precision in number representation when solving large-scale COPs, a uniform quantization scheme is applied to provide multiple-valued quantization. Alternatively, a logarithmic qSB leverages the evolution characteristics of position variables and implements multiplication by using simple shift operations. We demonstrate that using the proposed qSB improves the solution quality in a long search and accelerates energy convergence in a short search for solving COPs tackled by up to 2000 fully connected spins.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Jul 2, 2023•6 citations

Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

Hayato Goto, Kosuke Tatsumura, A. R. Dixon

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.

Science Advances•Apr 5, 2019•406 citations

CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems

Yunuo Cen, Debasis Das, Xuanyao Fong

Simulated annealing (SA) attracts more attention among classical heuristic algorithms because the solution of the combinatorial optimization problem can be naturally mapped to the ground state of the Ising Hamiltonian. However, in practical implementation, the annealing process cannot be arbitrarily slow and hence, it may deviate from the expected stationary Boltzmann distribution and become trapped in a local energy minimum. To overcome this problem, this paper proposes a heuristic search algorithm by expanding search space from a Markov chain to a recursive depth limited tree based on SA, where the parent and child nodes represent the current and future spin states. At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of `look ahead'. Furthermore, motivated by coherent Ising machine (CIM), we relax the discrete representation of spin states to continuous representation with a regularization term and utilize the reduced dynamics of the oscillators to explore the surrounding neighborhood of the selected tree nodes. We tested our algorithm on a representative NP-hard problem (MAX-CUT) to illustrate the effectiveness of this algorithm compared to semi-definite programming (SDP), SA, and simulated CIM. Our results show that above the primal heuristics SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.

arXiv:2203.09926•Mar 9, 2022•0 citations

On connection among quantum-inspired algorithms of the Ising model

Bowen Liu, Kaizhi Wang, Dongmei Xiao +1 more

Various combinatorial optimization NP-hard problems can be reduced to finding the minimizer of an Ising model, which is a discrete mathematical model. It is an intellectual challenge to develop some mathematical tools or algorithms for solving the Ising model. Over the past decades, some continuous approaches or algorithms have been proposed from physical, mathematical or computational views for optimizing the Ising model such as quantum annealing, the coherent Ising machine, simulated annealing, adiabatic Hamiltonian systems, etc.. However, the mathematical principle of these algorithms is far from being understood. In this paper, we reveal the mathematical mechanism of dynamical system algorithms for the Ising model by Morse theory and variational methods. We prove that the dynamical system algorithms can be designed to minimize a continuous function whose local minimum points give all the candidates of the Ising model and the global minimum gives the minimizer of Ising problem. Using this mathematical mechanism, we can easily understand several dynamical system algorithms of the Ising model such as the coherent Ising machine, the Kerr-nonlinear parametric oscillators and the simulated bifurcation algorithm. Furthermore, motivated by the works of C. Conley, we study transit and capture properties of the simulated bifurcation algorithm to explain its convergence by the low energy transit and capture in celestial mechanics. A detailed discussion on $2$-spin and $3$-spin Ising models is presented as application.

arXiv:2012.01156•Communications in Mathematical Sciences•Jan 1, 2023•2 citations

Effects of local minima and bifurcation delay on combinatorial optimization with continuous variables

Shintaro Sato

Combinatorial optimization problems can be mapped onto Ising models, and their ground state is generally difficult to find. A lot of heuristics for these problems have been proposed, and one promising approach is to use continuous variables. In recent years, one such algorithm has been implemented by using parametric oscillators known as coherent Ising machines. Although these algorithms have been confirmed to have high performance through many experiments, unlike other familiar algorithms such as simulated annealing, their computational ability has not been fully investigated. In this paper, we propose a simple heuristic based on continuous variables whose static and dynamical properties are easy to investigate. Through the analyses of the proposed algorithm, we find that many local minima in the early stage of the optimization and bifurcation delay reduce its performance in a certain class of Ising models.

arXiv:2211.00822•Nov 2, 2022•0 citations
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.
Combinatorial optimization problems are ubiquitous in industrial applications. However, finding optimal or close-to-optimal solutions can often be extremely hard. Because some of these problems can be mapped to the ground-state search of the Ising model, tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms such as quantum simulators and coherent Ising machines to tackle hard optimization problems. Here, we examine and benchmark several physics-inspired optimization algorithms, including coherent Ising machines, gain-dissipative algorithms, simulated bifurcation machines, and Hopfield neural networks, which we collectively refer to as stochastic driven nonlinear dynamical systems. Most importantly, we benchmark these algorithms against random Ising problems with planted solutions and compare them to simulated annealing as a baseline leveraging the same software stack for all solvers. We further study how different numerical integration techniques and graph connectivity affect performance. This work provides an overview of a diverse set of new optimization paradigms.
Developed from the Ising model, Ising machines are promising to be efficient domain-specific accelerators for solving combinatorial optimization problems (COPs). A simulated bifurcation (SB) algorithm enables an Ising machine to achieve massive parallelism in the simulation of Hamiltonian dynamics. Although SB significantly accelerates the search, more resources are required due to the use of continuous variables for the position of oscillators to obtain discrete spin states, compared to conventional simulated annealing. This article proposes ternary and multiple-value quantized SB (qSB) algorithms by discretizing the position variables used for the hardware-consuming multiply-accumulate (MAC) operations in SB. These quantization schemes do not only reduce the computational complexity, but also improve the solution quality for COPs. Specifically, the ternary qSB with dynamic threshold settings converts the MAC into addition and subtraction. To improve the precision in number representation when solving large-scale COPs, a uniform quantization scheme is applied to provide multiple-valued quantization. Alternatively, a logarithmic qSB leverages the evolution characteristics of position variables and implements multiplication by using simple shift operations. We demonstrate that using the proposed qSB improves the solution quality in a long search and accelerates energy convergence in a short search for solving COPs tackled by up to 2000 fully connected spins.
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.
Simulated annealing (SA) attracts more attention among classical heuristic algorithms because the solution of the combinatorial optimization problem can be naturally mapped to the ground state of the Ising Hamiltonian. However, in practical implementation, the annealing process cannot be arbitrarily slow and hence, it may deviate from the expected stationary Boltzmann distribution and become trapped in a local energy minimum. To overcome this problem, this paper proposes a heuristic search algorithm by expanding search space from a Markov chain to a recursive depth limited tree based on SA, where the parent and child nodes represent the current and future spin states. At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of `look ahead'. Furthermore, motivated by coherent Ising machine (CIM), we relax the discrete representation of spin states to continuous representation with a regularization term and utilize the reduced dynamics of the oscillators to explore the surrounding neighborhood of the selected tree nodes. We tested our algorithm on a representative NP-hard problem (MAX-CUT) to illustrate the effectiveness of this algorithm compared to semi-definite programming (SDP), SA, and simulated CIM. Our results show that above the primal heuristics SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.
Various combinatorial optimization NP-hard problems can be reduced to finding the minimizer of an Ising model, which is a discrete mathematical model. It is an intellectual challenge to develop some mathematical tools or algorithms for solving the Ising model. Over the past decades, some continuous approaches or algorithms have been proposed from physical, mathematical or computational views for optimizing the Ising model such as quantum annealing, the coherent Ising machine, simulated annealing, adiabatic Hamiltonian systems, etc.. However, the mathematical principle of these algorithms is far from being understood. In this paper, we reveal the mathematical mechanism of dynamical system algorithms for the Ising model by Morse theory and variational methods. We prove that the dynamical system algorithms can be designed to minimize a continuous function whose local minimum points give all the candidates of the Ising model and the global minimum gives the minimizer of Ising problem. Using this mathematical mechanism, we can easily understand several dynamical system algorithms of the Ising model such as the coherent Ising machine, the Kerr-nonlinear parametric oscillators and the simulated bifurcation algorithm. Furthermore, motivated by the works of C. Conley, we study transit and capture properties of the simulated bifurcation algorithm to explain its convergence by the low energy transit and capture in celestial mechanics. A detailed discussion on 222-spin and 333-spin Ising models is presented as application.
Combinatorial optimization problems can be mapped onto Ising models, and their ground state is generally difficult to find. A lot of heuristics for these problems have been proposed, and one promising approach is to use continuous variables. In recent years, one such algorithm has been implemented by using parametric oscillators known as coherent Ising machines. Although these algorithms have been confirmed to have high performance through many experiments, unlike other familiar algorithms such as simulated annealing, their computational ability has not been fully investigated. In this paper, we propose a simple heuristic based on continuous variables whose static and dynamical properties are easy to investigate. Through the analyses of the proposed algorithm, we find that many local minima in the early stage of the optimization and bifurcation delay reduce its performance in a certain class of Ising models.