SQBM+ Technologies
What is the Simulated Bifurcation Machine?
Originated from research on quantum bifurcation machines,
the SBM is a practical and ready-to-use ISING machine that solves large-scale "combinatorial optimization problrems" at high speed.
※Simulated Bifurcation Machine=SBM
Software
No need for special hardware, can be implemented on general-purpose computers using GPUs and FPGAs and as cloud services.
Large-scale
Supports up to 10M variables.
Performance enhancement is possible by way of scale-ups and scale-outs.
Fast
100 times faster than a simulated annealing*2, now widely used to solve a Ising problem.
*1：The number of non-zero coefficients is up to 1 billion.
*2：Based on our environment
What is a combinatorial optimization problem?
A problem for finding the best combination among an exponential number of candidates. With an increase in the problem size, i.e., the number of combinations in total, it is practically impossible to exhaustively test every combination and arrive at a good solution, which is one of the limitations of traditional computing.
Examples of combinatorial optimization problems
Logistic optimization
Find a route with the shortest travel distance.
Traffic congestion alleviation
Determine the route of each vehicle to minimize congestion.
Financial portfolio optimization
Find a combination of different stocks with high return and low risk.
Molecular design for drug discovery
Identify the molecular makeup of drugs with the desired efficacy.
Small-scale problems
Possible to test every single combination and find the solution.
Large-scale problems
Practically impossible to every single combination; the remaining option is to rely on experiences, educated guesses, and trial and error.
Ising machine that utilizes natural phenomenon for problem solving
Applies and simulates the model of magnets known as the Ising model to solve combinatorial optimization problems.
What is the Simulated Bifurcation algorithm?
A combinatorial optimization algorithm discovered in the process of research into quantum computers we proposed as "quantum bifurcation machines"
Theories behind the Simulated Bifurcation algorithm
We have applied such interesting phenomena in classical dynamics as bifurcation phenomena, adiabatic processes, and ergodic processes (chaos) to combinatorial optimization for the first time.Theoretically derived from our unique quantum computers called "quantum bifurcation machines", the theories behind it represent a purely quantum-mechanical discovery that even suggests the existence of unknown theorem in mathematical physics.
Bifurcation phenomenon
Changes in system parameters result in a transition from a single stable state to multiple stable states
Convert continuous variables into discrete variables.
Adiabatic process
The system remains in a low-energy state when the system parameters slowly change
Track the bottom of potential.
Ergodic process
The system visits all allowable energy states and stays longer in states with low potential energy
Find a lower point.
The motion of 2,000 particles as the Simulated Bifurcation Machine solves an optimization problem with 2,000 fully connected variables
RED: x is positive BLUE: x is negative
* Click the Play button to start the video. YouTube is the services provided by another company; please follow the terms of use in YouTube.
Reasons for high speed
Unlike simulated annealing (SA) characterized by sequential updates, our algorithm for computationally solving differential equations allows parallel updates, which in turn makes it possible for conventional parallel computers to achieve acceleration.
Our algorithm thus highly resonates with the technology trends in parallel computing.
H. Goto (2016). Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network, Scientific Reports, 6, 21686
Two new algorithms that significantly improves speed, accuracy, and scale for SQBM+
Ballistic Simulated Bifurcation Algorithm (bSB): A high-speed algorithm for finding a good solution in a short time
bSB is optimized and named for speed of operation, and finds good approximate solutions in a short time. It generates fewer errors than a previously reported Adiabatic Simulated Bifurcation Algorithm (aSB), and so returns faster, more accurate results. Implemented on a field programmable gate array (FPGA), dubbed the ballistic simulated bifurcation machine (bSBM), it obtains a good solution to a 2,000-bit problem approximately 10 times faster than the previous aSB machine (aSBM) (Figure 1).
Discrete Simulated Bifurcation Algorithm (dSB): A high-accuracy algorithm for finding more accurate solutions at a calculation speed that surpasses
dSB is a high-accuracy algorithm. Although implemented in a classical computer, it nonetheless arrives at optimal solutions faster than current quantum machines. Its name is derived from the replacement of continuous variables with discrete variables in equations of motion. This exhibits a quasi-quantum tunneling effect that breaks through the limits of approaches grounded in classical mechanics, reaching the optimal solution of the 2000-bit problem.
Toshiba has implemented dSB on a FPGA and built a discrete simulated bifurcation machine (dSBM) that achieves a higher speed than other machines in terms of computation times required to obtain optimal solutions for various problems . Implemented on a 16-GPU machine, the dSBM solved a one-million-bit problem, the largest yet reported in scientific papers, and arrived at a nearly optimal solution in 30 minutes—20,000 times faster than a CPU-based simulated annealing machine, which would take 14 months to carry out the computation (Figure 2).
In applying the two algorithms to real-world problems, Toshiba proposes bSB for applications that require an immediate response, and dSB for applications that require high accuracy, even if it takes a little longer time.
SQBM+ Includes a function that automatically selects and uses one of the two algorithms listed above.
H. Goto et al., Science Advances Vol. 7, no. 6, eabe7953 (2021)
The parameter auto-tuning function
In order to obtain highly-accurate solutions quickly, it is necessary to adjust the specific parameters that control the properties of the SQBM+ computation according to the optimization problem, but there are no fixed rules for how to adjust them. The trial and error of repeated calculations to find good parameters will undermine the high-speed and highly-accurate features of SQBM+.
SQBM+ implements an interface that automatically adjusts the optimal parameter values and returns the best solution found. Utilizing the Bayesian optimization method, it automatically searches for better parameters while performing multiple optimization calculations inside the SQBM+ service. As a result, by inputting only the input data of the optimization problem to be solved into SQBM+, the best solution can be obtained without trial and error of parameter adjustment.
The figure on the right illustrates the parameter auto-tuning function in case of the parameter dt which represents the time step width in the SB algorithm. The accuracy of the solution varies greatly depending on the value of dt. It has not been easy to find the best solution by trial and error of the value of dt. By using the parameter auto-tuning function, we can obtain the best possible solution with just one trial without trial and error.
Steps for applying the SQBM+ to real-world problems
After translating real-world problems into combinatorial optimization problems, mapping to the so-called "Ising model" is required.
* The formulas on this page are used to explain the principles of SBM and may differ from the formulas in the SBM PoC version.
