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

arXiv:2203.08361 · Communications Physics

Simulated bifurcation assisted by thermal fluctuation

Taro Kanao, Hayato Goto

Published Jun 14, 2022• 37 citations
arXivHTMLPDF

Abstract

Abstract Various kinds of Ising machines based on unconventional computing have recently been developed for practically important combinatorial optimization. Among them, the machines implementing a heuristic algorithm called simulated bifurcation have achieved high performance, where Hamiltonian dynamics are simulated by massively parallel processing. To further improve the performance of simulated bifurcation, here we introduce thermal fluctuation to its dynamics relying on the Nosé–Hoover method, which has been used to simulate Hamiltonian dynamics at finite temperatures. We find that a heating process in the Nosé–Hoover method can assist simulated bifurcation to escape from local minima of the Ising problem, and hence lead to improved performance. We thus propose heated simulated bifurcation and demonstrate its performance improvement by numerically solving instances of the Ising problem with up to 2000 spin variables and all-to-all connectivity. Proposed heated simulated bifurcation is expected to be accelerated by parallel processing.

DOI
10.1038/s42005-022-00929-9

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

High-performance combinatorial optimization based on classical mechanics

Hayato Goto, Kotaro Endo, Masaru Suzuki +6 more

Quickly obtaining optimal solutions of combinatorial optimization problems has tremendous value but is extremely difficult. Thus, various kinds of machines specially designed for combinatorial optimization have recently been proposed and developed. Toward the realization of higher-performance machines, here, we propose an algorithm based on classical mechanics, which is obtained by modifying a previously proposed algorithm called simulated bifurcation. Our proposed algorithm allows us to achieve not only high speed by parallel computing but also high solution accuracy for problems with up to one million binary variables. Benchmarking shows that our machine based on the algorithm achieves high performance compared to recently developed machines, including a quantum annealer using a superconducting circuit, a coherent Ising machine using a laser, and digital processors based on various algorithms. Thus, high-performance combinatorial optimization is realized by massively parallel implementations of the proposed algorithm based on classical mechanics.

Science Advances•Feb 3, 2021•231 citations

Solving Traveling Salesman Problems Using Ising Models with Simulated Bifurcation

Tingting Zhang, Qichao Tao, Jie Han

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.

International SoC Design Conference•Oct 6, 2021•10 citations

Simulated bifurcation for higher-order cost functions

Taro Kanao, Hayato Goto

Abstract High-performance Ising machines for solving combinatorial optimization problems have been developed with digital processors implementing heuristic algorithms such as simulated bifurcation (SB). Although Ising machines have been designed for second-order cost functions, there are practical problems expressed naturally by higher-order cost functions. In this work, we extend SB to such higher-order cost functions. By solving a problem having third-order cost functions, we show that the higher-order SB can outperform not only the second-order SB with additional spin variables, but also simulated annealing applied directly to the third-order cost functions. This result suggests that the higher-order SB can be practically useful.

arXiv:2211.09296•Applied Physics Express•Dec 14, 2022•28 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
Abstract Various kinds of Ising machines based on unconventional computing have recently been developed for practically important combinatorial optimization. Among them, the machines implementing a heuristic algorithm called simulated bifurcation have achieved high performance, where Hamiltonian dynamics are simulated by massively parallel processing. To further improve the performance of simulated bifurcation, here we introduce thermal fluctuation to its dynamics relying on the Nosé–Hoover method, which has been used to simulate Hamiltonian dynamics at finite temperatures. We find that a heating process in the Nosé–Hoover method can assist simulated bifurcation to escape from local minima of the Ising problem, and hence lead to improved performance. We thus propose heated simulated bifurcation and demonstrate its performance improvement by numerically solving instances of the Ising problem with up to 2000 spin variables and all-to-all connectivity. Proposed heated simulated bifurcation is expected to be accelerated by parallel processing.
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.
Quickly obtaining optimal solutions of combinatorial optimization problems has tremendous value but is extremely difficult. Thus, various kinds of machines specially designed for combinatorial optimization have recently been proposed and developed. Toward the realization of higher-performance machines, here, we propose an algorithm based on classical mechanics, which is obtained by modifying a previously proposed algorithm called simulated bifurcation. Our proposed algorithm allows us to achieve not only high speed by parallel computing but also high solution accuracy for problems with up to one million binary variables. Benchmarking shows that our machine based on the algorithm achieves high performance compared to recently developed machines, including a quantum annealer using a superconducting circuit, a coherent Ising machine using a laser, and digital processors based on various algorithms. Thus, high-performance combinatorial optimization is realized by massively parallel implementations of the proposed algorithm based on classical mechanics.
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.
Abstract High-performance Ising machines for solving combinatorial optimization problems have been developed with digital processors implementing heuristic algorithms such as simulated bifurcation (SB). Although Ising machines have been designed for second-order cost functions, there are practical problems expressed naturally by higher-order cost functions. In this work, we extend SB to such higher-order cost functions. By solving a problem having third-order cost functions, we show that the higher-order SB can outperform not only the second-order SB with additional spin variables, but also simulated annealing applied directly to the third-order cost functions. This result suggests that the higher-order SB can be practically useful.
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).