| |
Toshiba Corporation (global.toshiba) has developed a breakthrough algorithm that dramatically boosts the performance of the Simulated Bifurcation Machine (SBM), its proprietary quantum‑inspired combinatorial optimization computer. The new algorithm significantly improves the probability of obtaining an optimal solution or a known best solution within a limited number of trials referred to as the success probability, a key benchmark for evaluating combinatorial optimization technologies.
The SBM is designed to solve large‑scale combinatorial optimization problems in a wide range of fields, including new drug discovery, delivery route optimization, and investment portfolio design. While previous algorithms could find optimal or known best solutions with a sufficiently large number of trials, large‑scale problems often trapped the search process in local optima, significantly lowering success probability under practical constraints that limit the number of trials.
Toshiba has overcome this challenge by developing a third‑generation simulated bifurcation (SB) algorithm. This ground-breaking advance builds on the original SB algorithm, announced in April 2019*1, and the second‑generation SB algorithm, released in February 2021*2, which delivered major boosts to computational speed and accuracy.
The new algorithm expands the bifurcation parameter that triggers the bifurcation phenomena*3 a defining feature of the SB algorithm from a single global parameter to individual parameters assigned to each position variable*4. These bifurcation parameters are independently controlled according to the values of the corresponding position variables, enabling a more adaptive and effective solution search.
With the introduction of this advanced control mechanism, the algorithm exhibits either regular or chaotic behavior*5, depending on conditions. Crucially, Toshiba discovered that by effectively harnessing chaos at the edge of chaos the boundary between regular dynamics and chaotic motion the algorithm can escape local optima far more efficiently. As a result, the success probability of reaching the global optimum increases dramatically, approaching 100%.
The SBM based on the new algorithm is therefore much faster. It delivers a time to solution (TTS) required to obtain an optimal or known best solution that is approximately 100 times faster than the SBM based on the second‑generation algorithm. These advances are expected to accelerate the practical applications of combinatorial optimization across a broad range of challenges.
The research results were published in the April 6, 2026 issue of Physical Review Applied, a peer‑reviewed journal of the American Physical Society*6.
Development background
Efficiently addressing many modern industrial challenges such as optimizing logistics routes, constructing profitable investment portfolios, and designing novel molecules for drug discovery requires identifying optimal solutions from an enormous number of possible combinations. Many of these challenges can be mathematically formulated as combinatorial optimization problems.
Such problems are notoriously difficult to solve because the number of candidate solutions increases exponentially with the size of the problem, a phenomenon known as combinatorial explosion. As a result, substantial research and development efforts are underway around the world to create computing systems specialized for combinatorial optimization.
Toshiba is at the forefront of these efforts. In April 2019, the company introduced the Simulated Bifurcation (SB) algorithm, a proprietary quantum‑inspired algorithm well suited to parallel computation*1. In February 2021, the company further advanced the technology with the second‑generation SB algorithm, which achieved major improvements in speed and accuracy*2.
While the Simulated Bifurcation Machine, powered by the SB algorithm, can rapidly solve large‑scale combinatorial optimization problems by exploiting its high parallelizability, challenges have remained in dealing with instances of large problems, where the solution search can become trapped in local optima. Achieving a high success probability within a limited number of trials remained a key technical hurdle.
Features of the technology
Toshiba addressed this issue by further generalizing and enhancing the second‑generation SB algorithm. This work culminated in the development of the third‑generation SB algorithm, which dramatically boosts the probability of success to nearly 100%.
The key innovation lies in expanding the bifurcation parameter from a single shared value to individual parameters assigned to each position variable, along with the introduction of nonlinear control, whereby each parameter is governed by a nonlinear function of its corresponding position variable.
Through extensive analysis, Toshiba found that adjusting the strength of nonlinear control leads to a striking phenomenon: under certain conditions, the success probability sharply increases to nearly 100%.
A detailed investigation of system dynamics revealed that when the nonlinear control strength is small, the system exhibits regular behavior, while stronger control induces chaotic dynamics. At the edge of chaos the boundary between these two regimes the system demonstrates a dramatic improvement in its ability to reach the global optimum without becoming trapped in local optima (Figure 1).
This effect was first confirmed in a fully connected 2,000‑spin Ising problem*7 and was subsequently observed across a range of problems with different variable sizes. Importantly, the inherent high parallelizability of the SB algorithm is preserved. When implemented in an ultra‑parallel architecture using FPGA technology*8, the third‑generation SBM achieves a 10 to 100 times faster performance than the second‑generation SBM across many problem classes (Figure 2).
Future developments
Toshiba will further strengthen SQBM+™, its quantum‑inspired optimization solution, by incorporating the newly developed third‑generation SB algorithm. This will accelerate solution-finding in real‑world applications.
*1. global.toshiba/ww/technology/corporate/rdc/rd/topics/19/1904-01.html;
H. Goto, K. Tatsumura, A. R. Dixon, Sci. Adv. 5, eaav2372 (2019). advances.sciencemag.org/content/5/4/eaav2372 (American Association for the Advancement of Science)
*2. global.toshiba/ww/technology/corporate/rdc/rd/topics/21/2102-01.html;
H. H. Goto et al., Science Advances Vol. 7, no. 6, eabe7953 (2021). advances.sciencemag.org/content/7/6/eabe7953 (American Association for the Advancement of Science)
*3. In nonlinear dynamical systems, a phenomenon in which changes in system parameters (bifurcation parameters) cause the number of stable points to change from one to multiple.
*4. In the SB algorithm, the equations of motion of a classical dynamical system consisting of many oscillators are solved. A position variable represents the position of each oscillator, and these position variables correspond to the decision variables (discrete variables) of the combinatorial optimization problem.
*5. In nonlinear dynamical systems, a phenomenon in which even slight differences in initial conditions cause the subsequent trajectories of motion to diverge significantly, resulting in disordered (chaotic) behavior. This sensitivity of chaos to initial conditions is known as the butterfly effect, and the upper panel of Figure 1 provides a quantitative evaluation of this effect.
*6. H. Goto, R. Hidaka, K. Tatsumura, Physical Review Applied 25, 044011 (2026). doi.org/10.1103/2qd9-x6v8
*7. The Ising problem is a representative combinatorial optimization problem that seeks the spin configuration with minimum energy in the Ising model, the simplest model of a magnetic material, in which Ising spins taking values of ±1 are coupled through a quadratic energy function.
*8. FPGA is an abbreviation for Field‑Programmable Gate Array, a type of integrated circuit whose functions can be reconfigured by the user after manufacturing according to the intended application.
|
