Algorithms in the News: Simulated Bifurcation

A new algorithm (SB) appears to represent a major new development in combinatorial optimization.

A number of publications are reporting a new deveiopment in the area of combinatorial optimization: a new algorithm called Simulated Bifurcation (SB). has a good write-up:

Toshiba's breakthrough algorithm realizes world's fastest, largest-scale combinatorial optimization

Here's the research article:

Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems 

Supplementary Materials

And here's an article on Ising machines for more background:

Performance evaluation of coherent Ising machines against classical neural networks


There are a number of interesting and important points about this development:

1. Though the work was inspired by quantum optimization, the SB algorithm itself simulates the evolution of classical nonlinear Hamiltonian systems

2. The new approach appears to be much faster even than the previous state of the art (laser-based coherent Ising machine)

3. SB is suitable for parallelization, unlike many other combinatorial algorithms.

The authors use SB to solve the N-spin Ising problem, which is mathematically equivalent to the max-cut problem. The problem is NP-hard - the total number of (spin) configurations is 2N, meaning that it is very hard to find exact solutions for large N. SB is proposed as a new option in the area of heuristic algorithms. They implement an SB-based 2000-spin Ising machine on an FPGA, achieving impressive results (must faster than the previous best). They also solved an all-to-all connected 100,000-node MAX-CUT problem (about 5 billion edges) using a GPU cluster - here SB outperforms Simulated Annealing by a factor of ten.