Introduced in April 2019, the previous SB broke new ground as a platform for finding solutions to combinatorial optimisation problems, surpassing other approaches by a factor of 10.

Toshiba has now extended this achievement with two new algorithms that apply new approaches, such as a quasi-quantum tunneling effect, to performance improvement, allowing them to acquire optimal solutions (exact solutions) for large-scale combinatorial optimisation problems that challenge the capabilities of their predecessor.

They got dSB to go on a 16-GPU machine, and found it could come up with a nearly optimal solution for a one-million-bit problem in 30 minutes—a computation that would take 14 months on a typical CPU-based computer. The research results were published in the online academic journal, Science Advances, on 3 February.

The new algorithms have different characteristics. bSB is optimized and named for speed of operation, and finds good approximate solutions in a short time. It generates fewer errors than a previously reported Adiabatic Simulated Bifurcation Algorithm (aSB)^*4, and so returns faster, more accurate results. Implemented on a field programmable gate array (FPGA), dubbed the ballistic simulated bifurcation machine (bSBM), it obtains a good solution to a 2,000-bit problem approximately 10 times faster than the previous aSB machine (aSBM).

Toshiba said that dSB is a high-accuracy algorithm. Although implemented in a classical computer, it nonetheless arrives at optimal solutions faster than current quantum machines. Its name is derived from the replacement of continuous variables with discrete variables in equations of motion. This exhibits a quasi-quantum tunneling effect that breaks through the limits of approaches grounded in classical mechanics, reaching the optimal solution of the 2000-bit problem.

Toshiba has implemented dSB on a FPGA and built a discrete simulated bifurcation machine (dSBM) that achieves a higher speed than other machines in terms of computational times required to obtain optimal solutions for various problems (Figure 2).

In applying the two algorithms to real-world problems, Toshiba proposes bSB for applications that require an immediate response, and dSB for applications that require high accuracy, even if it takes a little longer time.

Toshiba expects the new algorithms to bring higher efficiencies to industry, business and complex decision-making by addressing combinatorial optimization problems in fields including investment portfolios, drug development, and delivery route planning.

Hayato Goto, Chief Research Scientist at Toshiba Corporation’s Corporate Research & Development Center, said: “We face many real-world problems where we must find the optimal solution among a huge number of choices, and we must also deal with combinatorial explosion, where the number of combination patterns increases exponentially as a problem increases in scale. This is why research into special-purpose computers for combinatorial optimization is being carried out worldwide. Our aim is to develop a software solution—algorithms that can solve large-scale combinatorial optimization problems quickly and accurately, and contribute to the realization of higher efficiencies.”

Toshiba will offer the newly developed simulated bifurcation algorithms as a GPU-based cloud service and as an on-premises version implemented on an FPGA within 2021.