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

International SoC Design Conference

Solving Traveling Salesman Problems Using Ising Models with Simulated Bifurcation

Tingting Zhang, Qichao Tao, Jie Han

Published Oct 6, 2021• 10 citations
Publisher

Abstract

Many combinatorial optimization problems can be solved by numerically simulating classical nonlinear Hamiltonian systems based on the Ising model. Solving the traveling salesman problem (TSP) using the Ising model requires a quadratically increasing number of spins with strict constraints. Unlike classical simulated annealing, simulated bifurcation (SB) can update the states of spins in parallel. This feature can potentially accelerate the convergence of Hamiltonian in the Ising model by taking advantage of modern multi-core processors. As an improved SB algorithm, the ballistic SB (bSB) algorithm is considered for solving the TSP in this paper. The TSP is converted to an Ising problem with external magnetic fields. bSB is then expanded by introducing a time-dependent factor. Experiments on benchmark datasets show that the bSB-based Ising solver offers superior performance in solution quality and convergence speed.

DOI
10.1109/isocc53507.2021.9613918

Related papers

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

Solving traveling salesman problems via a parallel fully connected ising machine

Qichao Tao, Jie Han

Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly improves the accuracy and performance in solving constrained combinatorial optimization problems such as the TSP. Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Large scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm.

ACM/IEEE Design Automation Conference (DAC)•Jul 10, 2022•21 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•80 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•5 citations
Many combinatorial optimization problems can be solved by numerically simulating classical nonlinear Hamiltonian systems based on the Ising model. Solving the traveling salesman problem (TSP) using the Ising model requires a quadratically increasing number of spins with strict constraints. Unlike classical simulated annealing, simulated bifurcation (SB) can update the states of spins in parallel. This feature can potentially accelerate the convergence of Hamiltonian in the Ising model by taking advantage of modern multi-core processors. As an improved SB algorithm, the ballistic SB (bSB) algorithm is considered for solving the TSP in this paper. The TSP is converted to an Ising problem with external magnetic fields. bSB is then expanded by introducing a time-dependent factor. Experiments on benchmark datasets show that the bSB-based Ising solver offers superior performance in solution quality and convergence speed.
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.
Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly improves the accuracy and performance in solving constrained combinatorial optimization problems such as the TSP. Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Large scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm.
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.