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.
Applies and simulates the model of magnets known as the Ising model to solve combinatorial optimization problems.
Combinatorial Optimization Problems
Ising Model
Ising Machine
Combinatorial Optimization Problems.
Ising Machine
Ising Model
A combinatorial optimization algorithm discovered in the process of research into quantum computers we proposed as "quantum bifurcation machines"
Schrödinger equation
Hamilton's equation
Schrödinger equation
Hamilton's equation
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
Figure 1: Temporal change of particle position x
Figure 2: Motion of particles in phase space (xy plane surface)
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.
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
After translating real-world problems into combinatorial optimization problems, mapping to the so-called "Ising model" is required.
eg. Portfolio Optimization
Correlation between assets in portfolio
Find a combination of assets.
Modeling
Model the obtained combination as a problem to find those matrices that have desired properties.
Formulating an equation
Formulate an equation which minimizes when a combination represents matrices with optimal properties.
Computing
Obtain the optimal solution.
Ising machine
eg. Portfolio Optimization
Correlation between assets in portfolio
Find a combination of assets.
Modeling
Model the obtained combination as a problem to find those matrices that have desired properties.
Formulating an equation
Formulate an equation which minimizes when a combination represents matrices with optimal properties.
Computing
Obtain the optimal solution.
Ising machine
* The formulas on this page are used to explain the principles of SBM and may differ from the formulas in the SBM PoC version.
* The formulas on this page are used to explain the principles of SBM and may differ from the formulas in the SBM PoC version.
Following links will open in a new window
