Toshiba's breakthrough algorithm realizes world's fastest, largest-scale combinatorial optimization

Toshiba Corporation 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 quickly solve diverse social and business problems, aiming for commercialization in 2019.

Details of the new technology are published in the online academic journal Science Advances.

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, 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), 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 recognized as the world's fastest can solve the same problem. In addition, using a cluster of eight GPUs, 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, adiabatic processes, and ergodic processes in classical mechanics to rapidly find highly accurate solutions. Toshiba derived the principle from a theory of a quantum computer proposed by the company itself. This discovery in classical mechanics inspired by quantum mechanics is an academically interesting, highly novel result that suggests the existence of unknown mathematical theorems.

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.