Method

Simulated bifurcation: a classical, quantum-inspired solver for Ising and QUBO problems

Simulated bifurcation (SB) is a classical algorithm that solves Ising and QUBO problems by integrating the equations of motion of a network of oscillators, each of which ends on one of two branches that are read as a spin of +1 or −1. It runs on ordinary digital hardware, updates every variable at once, and is fast on dense problems. It is a heuristic with no guarantee of optimality, and independent benchmarks place it first on some problem classes and in the middle on others.

Updated

At a glance

What it solves
Ising and QUBO problems: the same input a quantum annealer or QAOA takes
What it runs on
Classical digital hardware: FPGAs, GPUs and CPUs. There are no qubits.
Where it comes from
The classical limit of a network of Kerr parametric oscillators, a proposed quantum Ising machine[1]
Variants
Adiabatic SB (2019), then ballistic (bSB) and discrete (dSB) SB (2021), which reduce the error of reading continuous positions as spins[2]
Why it is fast
Every variable is updated at the same time, so it parallelises well; simulated annealing updates spins one by one
What it guarantees
Nothing: it is a heuristic, so a run returns a good solution, not a proof that it is the best one
In eigenkit
No SB solver. eigenkit states the problem as a QUBO or Ising model and solves it with QAOA.

How simulated bifurcation works

SB gives every spin of the Ising problem a particle with a position xix_i and a momentum yiy_i. The particles move in a potential that a control parameter a(t)a(t), the pump, changes slowly from zero to a final value a0a_0. At the start the potential of each particle has one minimum at the origin, and the particles circle around it. As a(t)a(t) grows, each potential splits into two minima, one at positive and one at negative xx: this is the bifurcation. The particles follow one branch each, and at the end the sign of xix_i is read as the spin si=±1s_i = \pm 1[1].

The coupling term c0∑jJijxjc_0 \sum_j J_{ij} x_j pulls each particle toward the side its neighbours favour, so the branches that appear first and lowest are those of low Ising energy. In ballistic SB the equations of motion are x˙i=a0yi\dot{x}_i = a_0 y_i and y˙i=−(a0−a(t))xi+c0∑jJijxj\dot{y}_i = -(a_0 - a(t)) x_i + c_0 \sum_j J_{ij} x_j, integrated with the symplectic Euler method. Walls at xi=±1x_i = \pm 1 stop a particle dead when it reaches them: its position is set to ±1\pm 1 and its momentum to zero. Discrete SB uses the signs of the neighbours, sgn⁡(xj)\operatorname{sgn}(x_j), in the coupling term instead of their positions.

Two properties follow from this design. The first is parallelism: every xix_i and yiy_i is updated in the same step, with one matrix-vector product per step, which maps onto FPGA and GPU hardware. Simulated annealing, by contrast, generally needs spins updated one at a time to converge. The second is that the dynamics conserve energy, as an ideal adiabatic quantum annealer would, rather than following a gradient downhill. The name comes from that origin: SB is the classical, simulable counterpart of the quantum bifurcation machine, a network of Kerr-nonlinear parametric oscillators proposed as a quantum Ising machine[2].

The method has knobs. The time step Δt\Delta t, the number of steps, the pump schedule and the coupling scale c0c_0 change the result, and the published runs tune Δt\Delta t per problem. Because the final state depends on the random start, SB is run many times, often in parallel, and the best answer is kept.

Ballistic SB in a dozen lines, on an eigenkit problem

import numpy as np
from eigenkit.optimization import max_cut


def ballistic_sb(ising, steps=1000, dt=0.5, seed=0):
    """Ballistic SB (Goto et al. 2021) for an Ising model with no local fields."""
    upper = np.triu(ising.J, 1)
    J = -(upper + upper.T)                   # SB's sign convention: E = −sᵀJs/2
    n = len(J)
    c0 = 0.5 / (np.sqrt(n) * np.sqrt((J**2).sum() / (n * (n - 1))))
    rng = np.random.default_rng(seed)
    x, y = rng.uniform(-0.1, 0.1, (2, n))    # positions and momenta near zero
    for a in np.linspace(0.0, 1.0, steps):   # the pump a(t) rises to a0 = 1
        y += (-(1.0 - a) * x + c0 * (J @ x)) * dt
        x += y * dt
        wall = np.abs(x) > 1                 # perfectly inelastic walls at ±1
        x[wall], y[wall] = np.sign(x[wall]), 0.0
    return tuple(int(v < 0) for v in x)      # spin +1 is bit 0 in eigenkit


rng = np.random.default_rng(7)
edges = [(i, j) for i in range(14) for j in range(i + 1, 14) if rng.random() < 0.5]
problem = max_cut(edges)

print(-problem.energy(ballistic_sb(problem)))  # 32.0  edges cut by SB
print(-problem.brute_force()[1])               # 32.0  the maximum cut, from all 2**14 cuts

A teaching sketch of the bSB update rule with the coupling scale c0c_0 set as in Goto et al. 2021, run on a random 14-node MaxCut built by eigenkit and checked against eigenkit's exact brute_force(). It is not Toshiba's solver, it handles problems without local fields only, and one run is not a benchmark.

What the published benchmarks show

Two kinds of evidence exist: benchmarks by the inventors, against the machines they chose, and independent benchmarks that include SB among other solvers. They do not agree on a single ranking, because they measure different problems with different clocks.

BenchmarkWho ran itWhat it showed for SB
All-to-all 2,000-node MaxCut (K2000), single FPGAInventors, 2019Better average cut in 0.5 ms[1] than a coherent Ising machine in 5 ms and a tuned simulated annealing in 50 ms
All-to-all 100,000-node problem, 8-GPU clusterInventors, 2019About 10 times[1] faster than the authors' best simulated annealing at the same energy
K2000, time to reach 99% of the best known cutInventors, 2021bSB on an FPGA 0.26 ms[2], against 1.50 ms for the STATICA chip (a simulator's prediction) and 1.1 s for a coherent Ising machine
3-regular 3-XORSAT, scaling of time to solutionIndependent, 2022Middle group: exponent 0.0217[3], behind the Fujitsu Digital Annealer (0.0185) and a GPU code run on the original cubic form (0.0171), ahead of parallel tempering (0.0248) and D-Wave Advantage (0.08)
Sherrington-Kirkpatrick spin glass, 8,192 variablesIndependent, 2022Best of four solvers, with the best solutions by the 100 s[4] mark
45 MQLib instances, 5-minute runsIndependent, 2022Best, ties included, on 16 of 45[4], against 22 for D-Wave's hybrid solver, 20 for the Digital Annealer and 7 for simulated annealing
Random NAE 3-SAT at the phase transition, 8,192 variablesIndependent, 2022About the same as simulated annealing on a PC; the Digital Annealer was best[4]

The 2021 paper notes that some of the machines it compares against were not their latest versions. The 2022 benchmark used Toshiba's SBM evaluation version 1.5.1 with automatic parameter search. Times exclude loading the problem and network transfer.

Toshiba and Dharma Capital: SB in live trading at the Tokyo Stock Exchange

The most widely reported application of SB is a set of trading systems that Toshiba built and ran with Dharma Capital in the JPX co-location area of the Tokyo Stock Exchange, published as three IEEE Access papers in 2023[8]. Two of them are real-time trading systems with an SB solver on an FPGA in the order path. The first finds pairs-trading opportunities by an optimal path search in a market graph of N stocks. The second picks a balanced long and short basket of N stocks by a portfolio optimisation that rewards deviation from the volume-weighted average price and penalises correlation. The third is an asset-management back-test that picks a low-correlation portfolio by solving a maximum independent set problem on a market graph.

The question the live systems answer is narrow: can an NP-hard optimisation be solved between a market data packet and the order it triggers, fast enough that the order still fills at the price the decision assumed? To test this, each system traded for a few months and its real transactions were compared with a back-cast simulation of the same strategy that assumes every order fills at the intended price. The figures below are Toshiba's own, from papers written by Toshiba researchers.

The trading systems, in the vendor's own figures

Pairs tradingBalanced basket
Universe solved per decision15 stocks, 210 pairs[5]128 stocks[6]
System latency, market feed to order33 µs[5]164 µs[6]
Real-time trading period125 business days, 750 hours[5], March to August 202242 business days, 252 hours[6], February to March 2023
Real transaction amount against the simulation+2.6%[5], with 93.4%[5] of orders filled at the intended price+0.01%[6]
Sharpe ratio (annualised return / risk) of the back-cast simulation0.79 (7.5% / 9.5%)[5] over about 5 years1.23 (3.6% / 2.9%)[6] over about 3 years
Erroneous orders from wrong calculationNone observed in more than 1,000 hours[8] across the experimentsNone observed[8]

The asset-management study reports a back-tested Sharpe ratio of 1.16[7] for its best maximum-independent-set portfolio over 2013–2023 on more than 1,700 Japanese stocks, against 0.66 for TOPIX. That best strategy was chosen among 38 parameter settings on the same history.

When to try simulated bifurcation

SB is worth a trial when the problem is dense or fully connected, when it has thousands of variables or more, or when the answer is needed within a tight time limit and an approximate answer is acceptable. Those are the settings where the published results favour it. On sparse problems, or where a proof of optimality matters, a mixed-integer solver or a tuned classical heuristic is the baseline to beat first.

Toshiba sells SB as SQBM+, as software for GPU and FPGA machines and as a cloud service; the independent 3-XORSAT benchmark reached it through a cloud marketplace[3]. For experiments there is also an open-source implementation on PyPI, the simulated-bifurcation package. Whichever you use, run it against simulated annealing or parallel tempering on your own instances, with the same time budget, and compare the time to reach a target energy rather than one run each.

The formulation is the part that carries over between solvers. The QUBO and Ising guide shows how to write constraints as penalties and check the result in eigenkit, and the comparison of quantum annealing, simulated annealing and simulated bifurcation sets the benchmarks above next to the other Ising machines.

Questions

What is simulated bifurcation?

Simulated bifurcation is a heuristic algorithm for Ising and QUBO optimisation problems, proposed by Hayato Goto and colleagues at Toshiba in 2019. Each variable is a particle in a potential that slowly splits into two wells; the coupling between particles steers them so that the wells they end in, read as spins of +1 or −1, give a low Ising energy.

Is simulated bifurcation a quantum algorithm?

No. It is a classical algorithm that runs on ordinary FPGAs, GPUs and CPUs. It is called quantum-inspired because it is the classical counterpart of a proposed quantum machine, a network of Kerr-nonlinear parametric oscillators, and its equations can be simulated efficiently on a digital computer.

What is the difference between aSB, bSB and dSB?

Adiabatic SB (aSB), from 2019, uses a quartic potential and reads continuous positions as spins at the end, which introduces analog errors. Ballistic SB (bSB), from 2021, replaces the quartic term with hard walls at plus and minus one and reaches good approximate solutions faster. Discrete SB (dSB) also uses the signs of the neighbouring positions in the coupling term; in the 2021 paper it was the variant that found optimal or near-optimal solutions on problems with up to a million spins.

Is simulated bifurcation better than simulated annealing or quantum annealing?

It depends on the problem. In an independent 2022 benchmark SB was best on Sherrington-Kirkpatrick spin glasses but only about as good as simulated annealing on hard random satisfiability instances, and on a 3-XORSAT benchmark it scaled better than parallel tempering and D-Wave Advantage but worse than the Fujitsu Digital Annealer. No benchmark shows it winning on every class.

What is Toshiba SQBM+?

SQBM+ is Toshiba's commercial product built on its simulated bifurcation machines. It solves QUBO and Ising problems and is offered as software for computers with GPUs or FPGAs and as a cloud service. The trading systems Toshiba tested at the Tokyo Stock Exchange used SB implemented on FPGAs inside the trading system rather than a cloud service.

Can I run simulated bifurcation with eigenkit?

Not directly: eigenkit has no simulated bifurcation solver. It can build and check a QUBO or Ising problem, convert between the two, find the exact answer by brute force for small problems, and solve the problem with QAOA. The h and J arrays of an eigenkit Ising model can be passed to any SB implementation.

Sources

  1. H. Goto, K. Tatsumura, A. R. Dixon. Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Science Advances 5, eaav2372, 2019.
  2. H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, K. Tatsumura. High-performance combinatorial optimization based on classical mechanics. Science Advances 7, eabe7953, 2021.
  3. M. Kowalsky, T. Albash, I. Hen, D. A. Lidar. 3-regular 3-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quantum Science and Technology 7, 025008, 2022. arXiv:2103.08464.
  4. H. Oshiyama, M. Ohzeki. Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization. Scientific Reports 12, 2146, 2022. arXiv:2104.14096.
  5. K. Tatsumura, R. Hidaka, J. Nakayama, T. Kashimata, M. Yamasaki. Pairs-trading system using quantum-inspired combinatorial optimization accelerator for optimal path search in market graphs. IEEE Access 11, 104406–104416, 2023. arXiv:2307.05923.
  6. K. Tatsumura, R. Hidaka, J. Nakayama, T. Kashimata, M. Yamasaki. Real-time trading system based on selections of potentially profitable, uncorrelated, and balanced stocks by NP-hard combinatorial optimization. IEEE Access 11, 120023–120033, 2023. arXiv:2307.06339.
  7. R. Hidaka, Y. Hamakawa, J. Nakayama, K. Tatsumura. Correlation-diversified portfolio construction by finding maximum independent set in large-scale market graph. IEEE Access 11, 142979–142991, 2023. arXiv:2308.04769.
  8. Toshiba Corporation. The world's first demonstration of systems that execute unprecedented stock trading strategies based on computationally-hard quadratic discrete optimization by using quantum-inspired computer, Toshiba's simulated bifurcation machine. Toshiba Corporate Research and Development Center, press release, 15 December 2023, 2023.

Run it yourself with eigenkit

eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.

$ pip install eigenkit