Toshiba’s Optimization Algorithm Sets Speed Record for Solving Combinatorial Problems

Toshiba has come up with a new way of solving combinatorial optimization problems. A classic example of such problems is the traveling salesman dilemma, in which a salesman must find the shortest route between many cities.

Such problems are found aplenty in science, engineering, and business. For instance, how should a utility select the optimal route for electric transmission lines, considering construction costs, safety, time, and the impact on people and the environment? Even the brute force of supercomputers is impractical when new variables increase the complexity of a question exponentially.

But it turns out that many of these problems can be mapped to ground-state searches made by Ising machines. These specialized computers use mathematical models to describe the up-and-down spins of magnetic materials interacting with each other. Those spins can be used to represent a combinatorial problem. The optimal solution, then, becomes the equivalent of finding the ground state of the model.

Different approaches to Ising machines include D-Wave's quantum annealer, Fujitsu's CMOS digital annealer, and NTT Corporation's laser-based coherent Ising machine that advanced computational speeds to the limit with its 2,000-spin capability in solving a combinatorial problem with three criteria.

The latest entrant into the Ising field is Toshiba with its Simulated Bifurcation Algorithm. SBA is a quantum-inspired classical heuristics algorithm that Toshiba says is 10 times faster than competing technologies. In October, it announced a prototype device implementing the algorithm that can detect and execute optimal arbitrage opportunities from among eight currency combinations in real-time, and issue a trade order in microseconds. Toshiba says the likelihood of finding the most profitable arbitrage opportunities is greater than 90 percent.

"Sub-millisecond latency had not been demonstrated before on other Ising machines," says Hayato Goto, a senior research scientist at Toshiba's corporate R&D center, who discovered the algorithm. "What's more, our algorithm can be accelerated using off-the-shelf FPGAs and GPUs. Massive parallelization is also possible because we can update all the variables at the same time, which means low communications overhead."

After implementing SBA on a single FPGA, Goto says they were able to run 8,000 operations in parallel to solve a 2,000-spin problem. That can't be done in simulated annealing, he notes, because that scheme uses sequential updating based on pseudorandom numbers.

In another trial using eight GPUs, the device solved a 100,000-spin Ising problem (achieving 5 billion connections) in 10 seconds. This is 1,000 times faster than when using standard optimized simulated annealing software, according to Goto. "So SBA has many advantages over that approach," he says. Other advantages he cites include the small size of the required hardware and a low power rating of just 40 watts.

"Sub-millisecond latency had not been demonstrated before on other Ising machines." -Hayato Goto, Toshiba

Goto discovered the algorithm after he had proposed a new kind of quantum computer in 2016. He wrote a paper on this quantum bifurcation machine and compared it to a classical bifurcation machine, which he also developed.

Goto is now working with hardware designer Kosuke Tatsumura, a senior research scientist in the same Toshiba R&D center. Together they are developing a massively parallel device for SBA implemented on FPGAs.

"We're focusing first on fintech," says Tatsumura. No one, he points out, has yet been able to employ combinatorial optimization in high-frequency trading. "So we're testing an end-to-end arbitrage system that can easily be installed in a forex trading center," referring to foreign currency exchanges.

The total response time, he says, "including all input, calculating and output times is just 30 microseconds." This is much shorter, he adds, than the time required for an exchange to execute a trade, which is about one millisecond.

Toshiba is so confident in the success of its technology that it's weighing the pros and cons of forming an alliance with an established financial trader, as well as setting up its own trading business to exploit the speed of SBA in arbitrage trading.

But Chi-Guhn Lee, a researcher in industrial engineering at the University of Toronto, offers a word of caution. "There's a common belief in the industry that such arbitrage opportunities will not last long. Returns may fade over time-just a few months at most." The market, he adds, will not allow one trader to enjoy its lead for very long.

And Hirotaka Tamura, a Fujitsu senior fellow, is quick to note that though Toshiba claims Fujitsu's digital annealer has difficulty in scaling, "We at Fujitsu have a different opinion and have experimental results to refute this claim. There are many possibilities for using digitally-emulated signals for binary optimization. In this regard, Toshiba's approach is one of many."

Looking ahead, Toshiba is also considering developing a general-purpose SBA Ising machine that could be used to optimize logistics routes to lower delivery costs, design drugs tailored for individuals, and mitigate traffic jams. As for commercialization, "It won't be so long," says Tatsumura, "because we want to commercialize within one to two years."

Meanwhile, Spectrum readers can test the technology for themselves. Toshiba has set up a free online site using Amazon Web Services for its Simulated Bifurcation Machine. Users can upload several kinds of combinatorial optimization problems and run them on the SBM, which has a capacity of 10,000 spins. Amazon charges $3 an hour for use of this service.