Simulated Bifurcation Machine(SBM)Technologies
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 SBM
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
Steps for applying the SBM 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.