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). Phys.org 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 **

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 2^{N}, 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.