• TOP
  • SBM Technologies
  • Partners
  • Inquiry
  • Link
Jump to contents
Toshiba
Toshiba

TOSHIBA DIGITAL SOLUTIONS

  • Japanese
  • Sitemap
  • Contact us
Show navigation
  • TOSHIBA DIGITAL SOLUTIONS CORPORATION
  • Services and Solutions
  • Corporate Infomation
  • News
  • Contact Us
  • ▲ Close
  • Corporate Infomation
  • News
  • Services and Solutions

HOME > Simulated Bifurcation Machine TOP > Simulated Bifurcation Machine (SBM) Technologies

  • TOP
  • SBM Technologies
  • Partners
  • Inquiry
  • Links

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

Logistic optimization

Find a route with the shortest travel distance.

Traffic congestion alleviation

Traffic congestion alleviation

Determine the route of each vehicle to minimize congestion.

Financial portfolio optimization

Financial portfolio optimization

Find a combination of different stocks with high return and low risk.

Molecular design for drug discovery

Molecular design for drug discovery

Identify the molecular makeup of drugs with the desired efficacy.

Small-scale problems

Small-scale problems

Possible to test every single combination and find the solution.

→ Combinatorial explosion

Large-scale problems

Large-scale problems

Practically impossible to every single combination; the remaining option is to rely on experiences, educated guesses, and trial and error.

Open in a separate windowTry SBM

Open in a separate windowTry SBM

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.

  • Combinatorial Optimization Problems

    Combinatorial Optimization Problems
  • Modeling
  • Ising Model

    Ising Model
  • Simulation
  • Ising Machine

    Ising Machine
  • Stable state with the lowest energy Obtains the optimal solution
  • Model of magnets representing the interaction of atomic spins that are aligned in a lattice system.
  • Combinatorial Optimization Problems.

    Combinatorial Optimization Problems
  • Modeling
  • Ising Machine

    Ising Machine
  • Simulation
  • Ising Model

    Ising Model
  • Stable state with the lowest energy Obtains the optimal solution
  • ※Model of magnets representing the interaction of atomic spins that are aligned in a lattice system.

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"

  • Quantum bifurcation machine

    Schrödinger equation

    Schrödinger equation
  • Discovered in the process of reserch
  • Classical bifurcation machine

    Hamilton's equation

    Hamilton's equation
  • We can't run a simulation, we need real computers.
  • Refine the mechanism to enable fast implementation on parallel computers. SB algorithm
  • We can run a simulation on conventional computers.
  • Quantum bifurcation machine

    Schrödinger equation

    Schrödinger equation
  • We can't run a simulation, we need real computers.
  • Discovered in the process of reserch
  • Classical bifurcation machine

    Hamilton's equation

    Hamilton's equation
  • Refine the mechanism to enable fast implementation on parallel computers. SB algorithm

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

Bifurcation phenomenon

Convert continuous variables into discrete variables.

Adiabatic process

The system remains in a low-energy state when the system parameters slowly change

Adiabatic process

Track the bottom of potential.

Ergodic process

The system visits all allowable energy states and stays longer in states with low potential energy

Ergodic process

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.

Open in a separate windowTry SBM

Open in a separate windowTry SBM

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.

  • Simulated annealing (SA)
    Sequentially updates the sub-optimal solution
    →Does not allow parallel updates of variables

    Simulated annealing (SA) Sequentially updates the sub-optimal solution →Does not allow parallel updates of variables
  • Our simulated bifurcation (SB) algorithm
    Computationally solves differential equations.
    →Allows parallel updates of variables

    Our simulated bifurcation (SB) algorithm Computationally solves differential equations. →Allows parallel updates of variables
  • Simulated annealing (SA)
    Sequentially updates the sub-optimal solution
    →Does not allow parallel updates of variables

    Simulated annealing (SA) Sequentially updates the sub-optimal solution →Does not allow parallel updates of variables
  • Our simulated bifurcation (SB) algorithm Computationally solves differential equations.
    →Allows parallel updates of variables

    Our simulated bifurcation (SB) algorithm Computationally solves differential equations. →Allows parallel updates of variables

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.

  • 1.Real-world problems

    eg. Portfolio Optimization

    Correlation between assets in portfolio

    Find a combination of assets.

    eg. Portfolio Optimization
  • 2.Combinatorial optimization problems

    Modeling

    Model the obtained combination as a problem to find those matrices that have desired properties.

    Combinatorial optimization problems
  • 3.Ising model

    Formulating an equation

    Formulate an equation which minimizes when a combination represents matrices with optimal properties.

    Ising model
  • 4.SBM

    Computing

    Obtain the optimal solution.

    Ising machine最適解を得る

  • 1.Real-world problems

    eg. Portfolio Optimization
    Correlation between assets in portfolio

    Find a combination of assets.

    eg. Portfolio Optimization

  • 2.Combinatorial optimization problems

    Modeling

    Model the obtained combination as a problem to find those matrices that have desired properties.

    Combinatorial optimization problems

  • 3.Ising model

    Formulating an equation

    Formulate an equation which minimizes when a combination represents matrices with optimal properties.

    Ising model

  • 4.SBM

    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.

Open in a separate windowFollowing links will open in a new window

To Top

Questions?
Mail / Stack overflow / FAQ

Open in a separate windowResearch Paper Open in a separate windowTry SBM

Open in a separate windowTwitter

  • Privacy Policy
  • Terms and Conditions
  • Contact Us
TOSHIBA DIGITAL SOLUTIONS
Copyright