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

IEEE International Symposium on Circuits and Systems proceedings

FPGA-Based Dense-Sparse Adaptive Simulated Bifurcation Ising Machine for MAX-CUT Problems

Yihang Peng, Chengjie Wang, Yudi Zhao, Shisheng Xiong

Published May 1, 2026• 0 citations
Publisher

Abstract

Combinatorial Optimization Problems (COP) are mostly arbitrary and sparse in practice. Simulated bifurcation (SB), as an emerging quantum-inspired heuristic algorithm exhibits strong performance in solving COP. However, existing SB-based Ising machines lack adaptability to sparse graphs, require excessive hardware resources, and struggle to balance convergence speed and solution quality. To address these issues, this paper proposes a fully connected FPGA-based dense-sparse adaptive SB Ising Machine (DSA-SBM) for sparse COP. DSA-SBM adopts an adaptive SB strategy rooted in saturating-growth control to balance system convergence speed and optimal solution accuracy. Its hardware features a dense-sparse adaptive architecture with compressed sparse row (CSR) format storage for 5-bit coefficient matrix and supports dynamic data allocation and adaptive matrix-spin multiplication. Implemented on Xilinx UltraScale+ XCZU7EV FPGA with 151 MHz clock frequency, it achieves 13.81× higher energy efficiency than the original dense SB Ising machine. In the 2000 spin MAX-CUT benchmark, it achieves 99.56% accuracy with an average of 0.687 ms, delivering a 123.6-170.5× speedup compared to the GPU.

DOI
10.1109/iscas66217.2026.11562489

Related papers

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

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

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

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•7 citations

Engineering Discrete Simulated Bifurcation for an FPGA Digital Ising Machine

Fabrizio Orlando, Deborah Volpe, Giacomo Orlandi +3 more

Simulated Adiabatic Bifurcation (aSB) is a quantum-inspired algorithm that provides approximate solutions for large-scale optimization problems using the Ising model. It emulates the quantum adiabatic evolution of a network of non-linear Kerr oscillators on classical platforms. These oscillators undergo bifurcation, where each branch corresponds to a spin state, with the network creating an energy imbalance to deter-mine the optimal solution. This approach is highly parallelizable, making it suitable for implementation on GPUs and FPGAs. However, classical emulation introduces analog errors, potentially compromising performance. To address this, alternative methods like ballistic (bSB) and discrete (dSB) evolutions were developed, with the ballistic approach further enhanced by thermal fluctuations (HbSB). Our comprehensive analysis of bSB, dSB, and HbSB using benchmark Max-Cut and knapsack problems aimed to identify the best balance of speed, area, and accuracy. We found that fixed-point number representation allows more algorithm iterations within the same timeframe as floating-point representation. The proposed FPGA architecture implements d$S$B and its heated version, leveraging high parallelizability and efficient memory or-ganization. This design supports larger coefficients and improves problem-solving efficiency without multipliers for matrix-vector evaluation. Challenges include mitigating data dependency between matrix-vector multiplication and time evolution, and developing a preconditioning method for adapting problem coefficients, making the architecture suitable for real-world applications and potential ASIC release.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Efficient and Scalable Architecture for Multiple-Chip Implementation of Simulated Bifurcation Machines

Tomoya Kashimata, Masaya Yamasaki, Ryo Hidaka +1 more

Ising machines are specialized computers for finding the lowest energy states of Ising spin models, onto which many practical combinatorial optimization problems can be mapped. Simulated bifurcation (SB) is a quantum-inspired parallelizable algorithm for Ising problems that enables scalable multi-chip implementations of Ising machines. However, the computational performance of a previously proposed multi-chip architecture tends to saturate as the number of chips increases for a given problem size because computation and communication are exclusive in the time domain. In this paper, we propose a streaming architecture for multi-chip implementations of SB-based Ising machines with full spin-to-spin connectivity. The data flow in in-chip computation is harmonized with the data flow in inter-chip communication, enabling the computation and communication to overlap and the communication time to be hidden. Systematic experiments demonstrate linear strong scaling of performance up to the vicinity of the ideal communication limit determined only by the latency of chip-to-chip communication. Our eight-FPGA (field-programmable gate array) cluster can compute a 32,768-spin problem with a high pipeline efficiency of 97.9%. The performance of a 79-FPGA cluster for a 100,000-spin problem, projected using a theoretical performance model validated on smaller experimental clusters, is comparable to that of a state-of-the-art 100,000-spin optical Ising machine.

arXiv:2311.17370•IEEE Access•Jan 1, 2024•23 citations
Combinatorial Optimization Problems (COP) are mostly arbitrary and sparse in practice. Simulated bifurcation (SB), as an emerging quantum-inspired heuristic algorithm exhibits strong performance in solving COP. However, existing SB-based Ising machines lack adaptability to sparse graphs, require excessive hardware resources, and struggle to balance convergence speed and solution quality. To address these issues, this paper proposes a fully connected FPGA-based dense-sparse adaptive SB Ising Machine (DSA-SBM) for sparse COP. DSA-SBM adopts an adaptive SB strategy rooted in saturating-growth control to balance system convergence speed and optimal solution accuracy. Its hardware features a dense-sparse adaptive architecture with compressed sparse row (CSR) format storage for 5-bit coefficient matrix and supports dynamic data allocation and adaptive matrix-spin multiplication. Implemented on Xilinx UltraScale+ XCZU7EV FPGA with 151 MHz clock frequency, it achieves 13.81× higher energy efficiency than the original dense SB Ising machine. In the 2000 spin MAX-CUT benchmark, it achieves 99.56% accuracy with an average of 0.687 ms, delivering a 123.6-170.5× speedup compared to the GPU.
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).
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.
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.
Simulated Adiabatic Bifurcation (aSB) is a quantum-inspired algorithm that provides approximate solutions for large-scale optimization problems using the Ising model. It emulates the quantum adiabatic evolution of a network of non-linear Kerr oscillators on classical platforms. These oscillators undergo bifurcation, where each branch corresponds to a spin state, with the network creating an energy imbalance to deter-mine the optimal solution. This approach is highly parallelizable, making it suitable for implementation on GPUs and FPGAs. However, classical emulation introduces analog errors, potentially compromising performance. To address this, alternative methods like ballistic (bSB) and discrete (dSB) evolutions were developed, with the ballistic approach further enhanced by thermal fluctuations (HbSB). Our comprehensive analysis of bSB, dSB, and HbSB using benchmark Max-Cut and knapsack problems aimed to identify the best balance of speed, area, and accuracy. We found that fixed-point number representation allows more algorithm iterations within the same timeframe as floating-point representation. The proposed FPGA architecture implements dSSSB and its heated version, leveraging high parallelizability and efficient memory or-ganization. This design supports larger coefficients and improves problem-solving efficiency without multipliers for matrix-vector evaluation. Challenges include mitigating data dependency between matrix-vector multiplication and time evolution, and developing a preconditioning method for adapting problem coefficients, making the architecture suitable for real-world applications and potential ASIC release.
Ising machines are specialized computers for finding the lowest energy states of Ising spin models, onto which many practical combinatorial optimization problems can be mapped. Simulated bifurcation (SB) is a quantum-inspired parallelizable algorithm for Ising problems that enables scalable multi-chip implementations of Ising machines. However, the computational performance of a previously proposed multi-chip architecture tends to saturate as the number of chips increases for a given problem size because computation and communication are exclusive in the time domain. In this paper, we propose a streaming architecture for multi-chip implementations of SB-based Ising machines with full spin-to-spin connectivity. The data flow in in-chip computation is harmonized with the data flow in inter-chip communication, enabling the computation and communication to overlap and the communication time to be hidden. Systematic experiments demonstrate linear strong scaling of performance up to the vicinity of the ideal communication limit determined only by the latency of chip-to-chip communication. Our eight-FPGA (field-programmable gate array) cluster can compute a 32,768-spin problem with a high pipeline efficiency of 97.9%. The performance of a 79-FPGA cluster for a 100,000-spin problem, projected using a theoretical performance model validated on smaller experimental clusters, is comparable to that of a state-of-the-art 100,000-spin optical Ising machine.