Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
By Hayato Goto, Kosuke Tatsumura, Alexander Dixon. Science Advances, 2019
433 citations recorded by the source corpus.
Nonlinear Hamiltonian systems search optimal solutions exploiting their adiabatic and chaotic evolutions. 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.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/dcf48728e86da649fc5367c219e76e54a596055a
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Toshimori Honjo
- Hiroki Takesue
- Naeimeh Mohseni
- Ken-ichi Kawarabayashi
- Tomohiro Sonobe
- Tim Byrnes
- Peter Leonard McMahon
- Jure Leskovec
Citations in the corpus
- 100,000-spin coherent Ising machine (2021, positive): “They showed that it can improve the solution accuracy and calculation time compared with the previous SB algorithm ( 46 ).”
- Ising machines as hardware solvers of combinatorial optimization problems (2022, methodology): “In 2019, Toshiba developed an FPGA and GPU-based SB machine showing excellent performance due in part to its high parallelizability 180,181 .”