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

Science Advances

Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

Hayato Goto, Kosuke Tatsumura, A. R. Dixon

Published Apr 5, 2019• 456 citations
Publisher

Abstract

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.

DOI
10.1126/sciadv.aav2372

Related papers

Large-scale combinatorial optimization in real-time systems by FPGA-based accelerators for simulated bifurcation

Kosuke Tatsumura

Combinatorial optimization problems are economically valuable but computationally hard to solve. Many practical combinatorial optimizations can be converted to the ground-state search problems of Ising spin models. Simulated bifurcation (SB) is a quantum-inspired algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism, providing an opportunity for quickly solving those problems by massively parallel processing. In this article, we review our recent works on the design and implementation of high-performance FPGA-based accelerators for SB and their applications toward innovative real-time systems that make optimal responses to ever-changing situations. An example of such an application is an ultrafast financial transaction machine that detects the most profitable cross-currency arbitrage opportunities at microsecond speeds. Also, we show a scale-out architecture for SB-based Ising machines with all-to-all spin-spin couplings that allows continued scaling of both machine size and computational throughput by connecting multiple chips, rather than scaling up a single chip.

International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART)•Jun 21, 2021•6 citations

Large-scale combinatorial optimization in real-time systems by FPGA-based accelerators for simulated bifurcation

Kosuke Tatsumura

Combinatorial optimization problems are economically valuable but computationally hard to solve. Many practical combinatorial optimizations can be converted to the ground-state search problems of Ising spin models. Simulated bifurcation (SB) is a quantum-inspired algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism, providing an opportunity for quickly solving those problems by massively parallel processing. In this article, we review our recent works on the design and implementation of high-performance FPGA-based accelerators for SB and their applications toward innovative real-time systems that make optimal responses to ever-changing situations. An example of such an application is an ultrafast financial transaction machine that detects the most profitable cross-currency arbitrage opportunities at microsecond speeds. Also, we show a scale-out architecture for SB-based Ising machines with all-to-all spin-spin couplings that allows continued scaling of both machine size and computational throughput by connecting multiple chips, rather than scaling up a single chip.

IEICE Technical Report; IEICE Tech. Rep.•Jun 1, 2021•0 citations

Principle and Applications of Simulated Bifurcation Machine

Hayato Goto

Recently, we have proposed a new heuristic algorithm for combinatorial optimization inspired by our proposed quantum computer. We named the algorithm “simulated bifurcation (SB) algorithm,” because it is based on the numerical simulation of nonlinear Hamiltonian systems exhibiting bifurcations. Here we present the principle, performance, and applications of our SB machine.

Vacuum and Surface Science•Mar 9, 2020•0 citations

Edge-of-chaos-enhanced quantum-inspired algorithm for combinatorial optimization

Hayato Goto, Ryo Hidaka, Kosuke Tatsumura

Nonlinear dynamical systems with continuous variables can be used for solving combinatorial optimization problems with discrete variables. Numerical simulations of them are also useful as heuristic algorithms with a desirable property, namely, parallelizability, which allows us to execute them in a massively parallel manner, leading to ultrafast performance. However, the dynamical-system approaches with continuous variables are usually less accurate than conventional approaches with discrete variables such as simulated annealing. To improve the solution accuracy of a quantum-inspired algorithm called simulated bifurcation (SB), which was found from classical simulation of a quantum nonlinear oscillator network exhibiting quantum bifurcation, here we generalize it by introducing nonlinear control of individual bifurcation parameters and show that the generalized SB (GSB) can achieve surprisingly high performance, namely, almost 100% success probabilities for some large-scale problems. As a result, the time to solution for a 2000-variable problem is shortened to 10 ms by a GSB-based machine, which is 2 orders of magnitude shorter than the best known value, 1.3 s, previously obtained by an SB-based machine. To examine the reason for the ultrahigh performance, we investigated chaos in the GSB changing the nonlinear-control strength and found that the dramatic increase of success probabilities happens near the edge of chaos. That is, the GSB can find a solution with high probability by harnessing the edge of chaos. This finding suggests that dynamical-system approaches to combinatorial optimization will be enhanced by harnessing the edge of chaos, opening a broad possibility for physics-inspired approaches to combinatorial optimization.

arXiv:2508.17655•Physical Review Applied•Feb 26, 2026•13 citations

High-Parallel FPGA-Based Discrete Simulated Bifurcation for Large-Scale Optimization

Fabrizio Orlando, Deborah Volpe, Orlandi, Giacomo +3 more

Combinatorial Optimization (CO) problems exhibit exponential complexity, making their resolution challenging. Simulated Adiabatic Bifurcation (aSB) is a quantum-inspired algorithm to obtain approximate solutions to largescale CO problems written in the Ising form. It explores the solution space by emulating the adiabatic evolution of a network of Kerr-nonlinear parametric oscillators (KPOs), where each oscillator represents a variable in the problem. The optimal solution corresponds to the ground state of this system. A key advantage of this approach is the possibility of updating multiple variables simultaneously, making it particularly suited for hardware implementation. To enhance solution quality and convergence speed, variations of the algorithm have been proposed in the literature, including ballistic (bSB), discrete (dSB), and thermal (HbSB) versions. In this work, we have comprehensively analyzed dSB, bSB, and HbSB using dedicated software models, evaluating the feasibility of using a fixed-point representation for hardware implementation. We then present an opensource hardware architecture implementing the dSB algorithm for Field-Programmable Gate Arrays (FPGAs). The design allows users to adjust the degree of algorithmic parallelization based on their specific requirements. A proof-of-concept implementation that solves 256-variable problems was achieved on an AMD Kria KV260 SoM, a low-tier FPGA, validated using well-known max-cut and knapsack problems.

arXiv:2510.12407•Oct 14, 2025•2 citations

FPGA-Based Simulated Bifurcation Machine

Kosuke Tatsumura, A. R. Dixon, Hayato Goto

Since many combinatorial optimization problems can be mapped onto ground-state search problems of Ising models, special-purpose machines for Ising problems have attracted intense attention. Simulated bifurcation (SB) is a recently proposed algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism underlying in the algorithm, providing an opportunity to solve the Ising problems very fast by massively parallel processing. In this work, we implement the SB algorithm on FPGAs by designing massively parallel custom circuits. We then compare the FPGA-based SB machines with a state-of-the-art machine called a coherent Ising machine (CIM), a highly optimized implementation of simulated annealing (SA), and GPU-based SB machines. SB machines with spin size of 2,048/4,096 (2K/4K) on an Arria10 GX1150 FPGA have 8,192 processing elements for the matrix-vector multiplication (MM) modules (the most computationally intensive part) and achieve computation throughput of 1,873/2,027 GMAC/s for the MM modules, outperforming 2K/4K SB machines on an Nvidia Tesla V100 GPU (113/183 GMAC/s). The 2K FPGA-SB solves all-to-all connected 2000-node MAX-CUT problem 14X (/124X) faster than the CIM (/the highly-optimized SA), with much better energy efficiency (288X better than the CIM).

International Conference on Field Programmable Logic and Applications (FPL)•Sep 1, 2019•89 citations
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.
Combinatorial optimization problems are economically valuable but computationally hard to solve. Many practical combinatorial optimizations can be converted to the ground-state search problems of Ising spin models. Simulated bifurcation (SB) is a quantum-inspired algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism, providing an opportunity for quickly solving those problems by massively parallel processing. In this article, we review our recent works on the design and implementation of high-performance FPGA-based accelerators for SB and their applications toward innovative real-time systems that make optimal responses to ever-changing situations. An example of such an application is an ultrafast financial transaction machine that detects the most profitable cross-currency arbitrage opportunities at microsecond speeds. Also, we show a scale-out architecture for SB-based Ising machines with all-to-all spin-spin couplings that allows continued scaling of both machine size and computational throughput by connecting multiple chips, rather than scaling up a single chip.
Combinatorial optimization problems are economically valuable but computationally hard to solve. Many practical combinatorial optimizations can be converted to the ground-state search problems of Ising spin models. Simulated bifurcation (SB) is a quantum-inspired algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism, providing an opportunity for quickly solving those problems by massively parallel processing. In this article, we review our recent works on the design and implementation of high-performance FPGA-based accelerators for SB and their applications toward innovative real-time systems that make optimal responses to ever-changing situations. An example of such an application is an ultrafast financial transaction machine that detects the most profitable cross-currency arbitrage opportunities at microsecond speeds. Also, we show a scale-out architecture for SB-based Ising machines with all-to-all spin-spin couplings that allows continued scaling of both machine size and computational throughput by connecting multiple chips, rather than scaling up a single chip.
Nonlinear dynamical systems with continuous variables can be used for solving combinatorial optimization problems with discrete variables. Numerical simulations of them are also useful as heuristic algorithms with a desirable property, namely, parallelizability, which allows us to execute them in a massively parallel manner, leading to ultrafast performance. However, the dynamical-system approaches with continuous variables are usually less accurate than conventional approaches with discrete variables such as simulated annealing. To improve the solution accuracy of a quantum-inspired algorithm called simulated bifurcation (SB), which was found from classical simulation of a quantum nonlinear oscillator network exhibiting quantum bifurcation, here we generalize it by introducing nonlinear control of individual bifurcation parameters and show that the generalized SB (GSB) can achieve surprisingly high performance, namely, almost 100% success probabilities for some large-scale problems. As a result, the time to solution for a 2000-variable problem is shortened to 10 ms by a GSB-based machine, which is 2 orders of magnitude shorter than the best known value, 1.3 s, previously obtained by an SB-based machine. To examine the reason for the ultrahigh performance, we investigated chaos in the GSB changing the nonlinear-control strength and found that the dramatic increase of success probabilities happens near the edge of chaos. That is, the GSB can find a solution with high probability by harnessing the edge of chaos. This finding suggests that dynamical-system approaches to combinatorial optimization will be enhanced by harnessing the edge of chaos, opening a broad possibility for physics-inspired approaches to combinatorial optimization.
Combinatorial Optimization (CO) problems exhibit exponential complexity, making their resolution challenging. Simulated Adiabatic Bifurcation (aSB) is a quantum-inspired algorithm to obtain approximate solutions to largescale CO problems written in the Ising form. It explores the solution space by emulating the adiabatic evolution of a network of Kerr-nonlinear parametric oscillators (KPOs), where each oscillator represents a variable in the problem. The optimal solution corresponds to the ground state of this system. A key advantage of this approach is the possibility of updating multiple variables simultaneously, making it particularly suited for hardware implementation. To enhance solution quality and convergence speed, variations of the algorithm have been proposed in the literature, including ballistic (bSB), discrete (dSB), and thermal (HbSB) versions. In this work, we have comprehensively analyzed dSB, bSB, and HbSB using dedicated software models, evaluating the feasibility of using a fixed-point representation for hardware implementation. We then present an opensource hardware architecture implementing the dSB algorithm for Field-Programmable Gate Arrays (FPGAs). The design allows users to adjust the degree of algorithmic parallelization based on their specific requirements. A proof-of-concept implementation that solves 256-variable problems was achieved on an AMD Kria KV260 SoM, a low-tier FPGA, validated using well-known max-cut and knapsack problems.
Since many combinatorial optimization problems can be mapped onto ground-state search problems of Ising models, special-purpose machines for Ising problems have attracted intense attention. Simulated bifurcation (SB) is a recently proposed algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism underlying in the algorithm, providing an opportunity to solve the Ising problems very fast by massively parallel processing. In this work, we implement the SB algorithm on FPGAs by designing massively parallel custom circuits. We then compare the FPGA-based SB machines with a state-of-the-art machine called a coherent Ising machine (CIM), a highly optimized implementation of simulated annealing (SA), and GPU-based SB machines. SB machines with spin size of 2,048/4,096 (2K/4K) on an Arria10 GX1150 FPGA have 8,192 processing elements for the matrix-vector multiplication (MM) modules (the most computationally intensive part) and achieve computation throughput of 1,873/2,027 GMAC/s for the MM modules, outperforming 2K/4K SB machines on an Nvidia Tesla V100 GPU (113/183 GMAC/s). The 2K FPGA-SB solves all-to-all connected 2000-node MAX-CUT problem 14X (/124X) faster than the CIM (/the highly-optimized SA), with much better energy efficiency (288X better than the CIM).