The construction of logistics networks, the relieving of traffic congestion, the discovery of new drugs… What if we told you that these and other social solutions across a variety of fields, could be realized by solving what are called “combinatorial optimization problems”? Sounds simple, but it’s actually very difficult—so difficult, in fact, that solutions to these problems are thought to require the use of quantum computers. Here at Toshiba, however, we’ve discovered a new algorithm, through our research into quantum computers, capable of solving combinatorial optimization problems at high speeds on conventional (classical, or non-quantum) computers.

This new algorithm which generates nearly optimal solutions to various social issues very fast without the need for quantum computers would have massive effects worldwide. The algorithm, called “simulated bifurcation,” is gaining attention both in Japan and overseas, with a paper on the topic published in the famous U.S. online science journal “Science Advances.” In this article, we delve into the details of this new algorithm, and discuss its future outlook.

What is a combinatorial optimization problem?

To make things more efficient, you have to select the best combination of choices from the myriad of available choices. This, in a nutshell, is what’s called a combinatorial optimization problem. The Japanese logistics industry, for example, has been suffering in recent years from a chronic shortage of personnel. By solving this kind of problem, they can figure out the shortest possible routes for deliveries, thereby lessening the impact of their personnel shortage. In the same way, traffic congestions can be relieved by determining which route would be the most efficient way for a car to get to its destination.

As the scale of the issue grows larger, the total possible number of combinations grows exponentially and determining optimal combinations—the ones with maximum intended effect become more difficult. This combinatorial explosion is what has made combinatorial optimization problems notoriously difficult to solve. Consider, for example, what’s called the “Traveling Salesman Problem.” This is a problem that asks you to determine the shortest possible route for a salesman who needs to visit multiple cities, visiting each only once, before returning to his point of origin. Even with only 10 cities, there are 181,440 combinations. With 30 or 50, the numbers grow ridiculously large, to the point where it becomes almost impossible to solve by complicated calculations with regular computers. Determining the optimal route in these instances takes an unbelievably long time, and is thought, in realistic terms, to be impossible.

“The larger the scale of the problem, the more difficult it becomes to determine optimal combinations simply by going over the combinations one by one. Building logistics networks and reducing traffic are textbook examples, as is the development of new drugs, which require you to look for the combination of molecules that would make a drug most effective, and the building of financial portfolios, which require you to look for combinations of low-risk, high-profit combinations of stocks. There are countless problems like these, each with a massive number of combinations, everywhere in business and in society.”

So says Hayato Goto of the Corporate Research & Development Center at Toshiba Corporation.

Hayato Goto, Senior Research Scientist, Frontier Research Laboratory, Corporate Research & Development Center, Toshiba Corporation

It’s not as if combinatorial optimization problems are new, just that there were issues in solving them in the past. Amongst researchers, the standard practice is to use a standard problem called the “Ising problem”(*1) to solve for the optimal solution. Researchers have developed various algorithms for the Ising problem, and development is currently underway for a computer made specifically for Ising problem. There is an issue, however. Algorithms using regular, classical computers were capable of handling large-scale calculations with an enormous amount of variables, but have difficulty with accelerating the speed of calculations using parallel computing, due to their functional limits. Quantum computers, on the other hand, were capable of parallel computing, but have difficulty processing large-scale calculations.

*1: A type of combinatorial optimization problem that asks for the minimum energy state for what is referred to as the “Ising model,” the simplest model for a magnet

It would, of course, be of enormous benefit both to society and to industry if we were able to come up with a solution. In our current reality, however, it is incredibly difficult to process all of these calculations. This is what’s called the “combinatorial optimization problem.”

“Until now, research has been conducted using specialized computers (quantum computers) that utilize superconducting circuits, lazer, etc., but the practical use of quantum computers is still a long ways away, and also comes with significant costs. We were researching various methodologies, and eventually developed the ‘simulated bifurcation algorithm.’ It runs on conventional computers, using parallel computing for high-speed processing, and makes it possible for us to determine nearly optimal combinations at high speeds,” said Goto.

Goto has been involved in quantum computer research in Toshiba for many years. He tells us that this algorithm was inspired by the logic of quantum mechanics.

A new algorithm, inspired by quantum mechanics

“We began our research when we noticed, in 2017, that we could probably come up with something that could beat the coherent Ising machine(*2), which at the time had the world’s highest-speed computing power. We’d discovered both the quantum bifurcation machine, a Toshiba original quantum computer, which seeks optimal solutions using the superposition principle that result from quantum-mechanical bifurcation phenomena(*3), and the classical bifurcation machine, which is based on bifurcation phenomena in classical mechanics(*4), at the same time in 2015. When we used the classical bifurcation machine to solve large-scale problems through numerical simulation, we found that it performed extremely well. We realized that we could beat the coherent Ising machine if we were able to implement it on a FPGA(*5). It had taken us two years since its discovery to realize the value of this classical approach,” said Goto.

*2: A specialized machine for combinatorial optimization problems, that uses lasers instead of semiconducting circuits to process calculations
*3: A phenomenon in nonlinear dynamical systems in which the number of steady states diverges, from one to multiple
*4: Form of mechanics that existed before quantum mechanics.
*5: Abbreviation of “field-programmable gate array.” A type of logic integrated circuit that allows the user to overwrite functions according to its intended purpose after manufacturing.

The newly developed algorithm makes effective use of phenomena in classical mechanics, like the adiabatic process and the ergodic process, to solve the Ising problem. It is an entirely new algorithm, unlike anything before it.

Simulated annealing, a type of computational processing using conventional technology, is a form of sequential computation, in which variables are updated one by one. This functional limit makes it difficult to accelerate processing speeds through parallel computing, which means it takes a significant amount of time to come out with a solution. This new algorithm, on the other hand, works to solve differential equations, and is capable of updating multiple variables at the same time. As such, it can accelerate processing speeds using existing parallel computers. Thus, the new algorithm goes well with the current trend of parallelization in computing technologies.

Goto, alongside Kosuke Tatsumura, who also works at the Corporate Research & Development Center, had gotten to work developing a classical computer with faster processing speed than the coherent Ising machine. More specifically, they were working to refine the new algorithm, design a massively parallel processing circuit for it, and implement it on a FPGA.

“As a result, we were able to record a processing speed about 10 times faster than the world’s then-fastest coherent Ising machine, using a classical computer with a single FPGA. When you look to optimize productivity and efficiency in systems, and when you really get into the mathematics of it, you tend to dead-end at combinatorial optimization problems. But I think our results have shown that it’s possible to come out with good solutions for these kinds of problems in very short time frames,” said Tatsumura.

Kosuke Tatsumura, Senior Research Scientist, Computer & Network Systems Laboratory, Corporate Research & Development Center, Toshiba Corporation

Tatsumura tells us that they are currently in the middle of verification testing to implement this technology in society.

“To solve issues in society and industry with the simulated bifurcation algorithm, we first need to think about how these issues should be formulated as Ising problems. This requires high-level mathematical creativity. We’ve gotten incredible reactions from all kinds of avenues, and we’re looking forward to hearing concrete, realistic ideas about we could utilize this algorithm,” said Tatsumura.

Like a software update, but for all of society

At Toshiba, work is currently underway to make the simulated bifurcation algorithm available for practical use. How will this impact the world?

“More efficient logistics will bring delivery costs down, and it’ll be easier than ever to manage your assets wisely. There could also be personalized medications tailored to the constitution and situation of an individual, and so much more. In addition to making our existing businesses more efficient, we’re also looking to use this new technology in a variety of businesses—for example, establishing new businesses using our alliances with partner companies,” said Tatsumura.

Back in the day, the arrival of the Internet revolutionized the foundation of society. Likewise, the simulated bifurcation algorithm may provide a new technological foundation as a platform for various services. This new algorithm will help dramatically elevate the performance of all kinds in all kinds of fields.

The newly developed algorithm was borne of the quantum computer R&D process.

Goto said, about his vision for quantum computers, “Classical computers are thought, generally, to be inferior performance-wise to quantum computers. But the simulated bifurcation algorithm has drastically elevated the performance of classical computers. Now that classical computers can do this—solve large-scale problems at high speeds—quantum computers have to, at the minimum, be able to exceed that level of performance. I think they’ll come into practical use once they’re able to do that, and once we’re able to show that they’ll be more cost-effective, and capable of being implemented in society.”

This new algorithm has massively bolstered the potential of classical computers. Both of the researchers, in discussing the circumstances that made this breakthrough possible, emphasize the importance of Toshiba’s very specific kind of research environment.

“I think it’s rare for a company to have experts from every field, whether it be computational scientists like me, or experts from physics, mathematics, mathematical engineering, information processing, cloud computing… I believe the simulated bifurcation algorithm is the fruit of this huge variety of personnel we have here at Toshiba,” said Tatsumura.

“I mean, it feels almost like fate that I just happened to run into Tatsumura, just as I’d come up with this idea. I don’t think we would have been able to implement it as a circuit this quickly if it weren’t for Toshiba, and its incredible array of personnel,” said Goto.

The simulated bifurcation algorithm was thus a crystallization of the efforts of a wide variety of personnel, all working organically together. And with it, we move one step forward into the next great social and industrial “revolution.”

This article is an English version of the Japanese article published on August 8th, 2019.