Toshiba's Breakthrough Algorithm Realizes World's Fastest, Largest-scale Combinatorial Optimization
-Advance towards building service platform for rapid problem solving in logistics, drug development and other socially important areas-
Toshiba Corporation
TOKYO─Toshiba Corporation (TOKYO: 6502) has realized a major breakthrough in combinatorial optimization─the selection of the best solutions from among an enormous number of combinatorial patterns─with the development of an algorithm that delivers the world's fastest and largest-scale performance, and an approximately 10-fold improvement over current methods. Toshiba's new method can be applied to such daunting but essential tasks as identifying efficient delivery routes, determining the most effective molecular structures to investigate in new drug development, and building portfolios of profitable financial products.
The newly developed technique, the Simulated Bifurcation Algorithm, quickly obtains highly accurate approximate solutions (good solutions) for complex large-scale combinatorial optimization problems─problems that have resisted solution for a long time, and that are very difficult to solve using conventional techniques. Potentially even more important, the algorithm also realizes excellent scalability at a low cost using current computers, which could revolutionize current optimization processes.
Toshiba will use the Simulated Bifurcation Algorithm to build a service platform able to contribute to a better society by quickly solving diverse social and business problems, aiming for commercialization in 2019.
Details of the new technology are published in the online academic journal Science Advances (refer to Note10).
Many problems can only be solved by sifting through a vast number of options to find the best combinations. These include realizing efficient logistics (the traveling salesman problem in math), directing traffic to ease congestion, applying molecular design to drug development, and optimizing financial portfolios. Today, realizing such combinatorial optimization requires an enormous amount of computation, and using current computers to find solutions remains difficult.
There are growing expectations that next-generation computing devices, such as quantum computers, will lead the way to better solutions, and current research aims to develop computers specially designed for combinatorial optimization through the use of superconducting circuits, lasers, and semiconductor-based digital computers. Despite these efforts, it remains a challenge to increase the solvable-problem size and to reduce the computation time.
For example, it is still difficult for quantum computers with superconducting circuits to solve complex large-scale problems. And while today's semiconductor-based digital computers have made it easier to increase the solvable-problem size, current algorithms for combinatorial optimization are difficult to parallelize(Note 1), making it hard to use parallel computing to speed up problem solving.
Toshiba has solved these issues by developing a novel combinatorial optimization algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can therefore easily speed up problem solving on standard digital computer through parallel computation. As current large-scale computational systems can be used as is, there is no need to install new equipment, making it easy to scale up at a low cost.
For example, by using field-programmable gate arrays (FPGAs)(Note 2), a good solution to an optimization problem with 2,000 fully connected variables (approximately 2 million connections) can be obtained in just 0.5 milliseconds. This is approximately 10 times faster than the laser-based quantum computer(Note 3) recognized as the world's fastest can solve the same problem. In addition, using a cluster of eight GPUs(Note 4), Toshiba obtained a good solution for a large-scale problem involving 100,000 fully connected variables (about 5 billion connections) in only a few seconds. These results open up new ways of solving large-scale combinatorial optimization problems in many different areas of application.
The Simulated Bifurcation Algorithm harnesses bifurcation phenomena(Note 5), adiabatic processes(Note 6), and ergodic processes(Note 7) in classical mechanics(Note 8) to rapidly find highly accurate solutions. Toshiba derived the principle from a theory of a quantum computer proposed by the company itself(Note 9). This discovery in classical mechanics inspired by quantum mechanics is an academically interesting, highly novel result that suggests the existence of unknown mathematical theorems.
Toshiba Group in promoting digital transformation and bringing innovation to business models and platforms, and is committed to creating new problem-solving and results-oriented businesses in response to the management needs of clients in various business fields.
Moving forward this year, Toshiba now aims to use this key technology breakthrough to realize and commercialize a service platform that meets all optimization needs in logistics, finance, and other areas of modern society.
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 Play button to start movie. YouTube is the service provided from other company, and please follow the terms of use in YouTube.
- (Note 1)
- Simultaneous processing on multiple processors for calculations in an algorithm that can be performed at the same time.
- (Note 2)
- A logic integrated circuit designed configured by customers or designers after manufacturing for an application.
- (Note 3)
- Source: Toshiba study; see Inagaki et al., Science 354, 603 (2016).
- (Note 4)
- "Graphics processing unit," an integrated circuit for image processing with a large number of processing units. A set of interconnected GPUs is called a GPU cluster.
- (Note 5)
- In a nonlinear dynamic system, a phenomenon where changes in system parameters result in a transition from a single stable state to multiple stable states
- (Note 6)
- In a classical mechanical system, a phenomenon where the system remains in a low-energy state when the system parameters slowly change.
- (Note 7)
- In a classical mechanical system, the phenomenon of visiting all energetically allowable states. One type of chaos.
- (Note 8)
- In contrast to quantum mechanics, which describes the sub-microscopic world of atoms and other very small things, the mechanics recognized since Newton’s time is referred to as classical mechanics.
- (Note 9)
- A quantum computer based on the quantum adiabatic theorem and quantum bifurcation phenomena, proposed in H. Goto, Scientific Reports 6, 21686 (2016).
- (Note.10)
- H.Goto, K.Tatsumura ,A. R. Dixon, Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems,
Science Advances 19 Apr 2019:Vol. 5, no. 4, eaav2372
About Toshiba
Toshiba Corporation leads a global group of companies that combines knowledge and capabilities from over 140 years of experience in a wide range of businesses─from energy and social infrastructure to electronic devices─with world-class capabilities in information processing, digital and AI technologies. These distinctive strengths position Toshiba to become one of the world's leading cyber-physical-system technology companies. Guided by the Basic Commitment of the Toshiba Group, "Committed to People, Committed to the Future," Toshiba contributes to society's positive development with services and solutions that lead to a better world. The Group and its 132,000 employees worldwide secured annual sales surpassing 3.9 trillion yen (US$37.2 billion) in fiscal year 2017.
Find out more about Toshiba at www.toshiba.co.jp/worldwide/about/index.html
Media Contact
Media Relations Group
Public Relations & Investor Relations Office
Corporate Communications Div.
Toshiba Corporation
Phone: +81-3-3457-2100
Email: media.relations@toshiba.co.jp