We live in a world of dramatic change. Companies and societies are trying to tackle increasingly complex issues, and they are turning their attention to quantum technologies. Although it is expected to take some time before we see full-fledged quantum computers that utilize quantum phenomena, Toshiba is already working on quantum-inspired optimization technologies. We are applying our own in-house combinatorial optimization technologies for producing optimal results from massive numbers of options, providing them in the form of the quantum-inspired “SQBM+” optimization solution. This solution uses existing computers to produce highly accurate approximate solutions in short amounts of time. In this running feature, we will explain quantum-inspired optimization technologies.

The first issue will focus on an Ising machine, which uses Simulated Bifurcation Algorithms.

Simulations, AI/machine learning, and combinatorial optimization for finding optimal solutions are needed in areas such as the development of new drugs and materials, new financial products and transaction approaches, and the achievement of carbon neutrality, a vital task for our entire planet. These require massive amounts of computational power, so the time it takes to compute solutions rises exponentially as the scale of problems grows. Society is becoming more complex, so the problems that need to be solved are growing even larger. Producing solutions to these problems is ceasing to be feasible with conventional (classical) computers. For this reason, both in Japan and overseas, there is demand for the practical application of quantum computers, whose capabilities would far surpass classical computers.

Toshiba is also engaged in the research and development of quantum computers. Through this research process, we have discovered a new method for rapidly solving combinatorial optimization problems using classical computers. We refer to the unique algorithm used to solve these problems as a Simulated Bifurcation Algorithm and to the technology with which we implement this algorithm on classical computers as a Simulated Bifurcation Machine. These machines can also be categorized as a simulator of Ising machine, a type of quantum computer.

Quantum computers can be mainly divided into two types. “Gate-based computers” are envisioned for general purpose applications, while “Ising machines” are specially tailored to solving combinatorial optimization problems (Fig. 1).

Gate-based computers use “quantum bits” as their base unit of information. These quantum bits are comparable to the “bits” of classical computers. Instead of “logic gates,” they use “quantum gates,” and they perform computation by changing the states of quantum bits.

Quantum bits, which are composed of by applying quantum phenomena, can have a state that seems to contain a “0” and a “1” at the same time, unlike a classical computer bit, which is only a “0” or a “1.” By arranging sequences of quantum bits, which contain an even greater amount of information, gate-based quantum computers can contain an overwhelmingly larger number of states than a classical computer. Furthermore, quantum gates can simultaneously change the diverse states within a quantum bit, which gives them a far higher level of parallelism than a classical computer. Because of this, it is hoped that they will drive a tremendous leap in computing performance.

The gate approach makes it possible to create various programs by appropriately lining up quantum gates, so it is considered a “general purpose” approach. However, algorithms must be crafted with care in order to be able to rapidly extract useful information from the varied states of the bits. Shor’s algorithm is a famous algorithm used in prime factorization, which could lead to a compromise of the encryption systems, but there are still few effective algorithms for gate approach.

Another challenge facing systems that use the gate approach is hardware scalability. They function by applying quantum phenomena, so it is vital that they maintain stable quantum states. This requires advanced cooling technologies, so it is expected to take quite some time before we see Fault Tolerant Quantum Computers (FTQCs), large-scale fault-tolerant quantum computers. Therefore, efforts are being made to find practical applications for medium-sized quantum computers known as Noisy Intermediate-Scale Quantum devices, or NISQ devices, but even here, there is a challenge to find effective algorithms.

Now let’s look at another type of quantum computer: the Ising machine. These machines are named after 20th century German physicist Ernst Ising. Ising developed the Ising model to explain the properties of magnetism. Computers that use this model to express and rapidly solve combinatorial optimization problems are called Ising machines. Unlike systems that use the gate approach, which is envisioned as being used for general purpose problems, Ising machines are quantum computers that are designed exclusively to solve combinatorial optimization problems.

Ising machines are sometimes called “annealers.” They are based on simulated annealing algorithms that were developed to use software to simulate and optimize annealing, a process of heat treatment used to improve the properties of metals. The idea of applying these algorithms in quantum systems to solve combinatorial optimization problems was first proposed by Dr. Hidetoshi Nishimori of the Tokyo Institute of Technology in 1998, and it was called “quantum annealing.” Ising machines and annealers have now come to mean almost the exact same thing, and in this article we will refer to them as “Ising machines.”

Currently, for technical reasons, it is expected to take quite some time before either gate or Ising machine approaches can be used in actual quantum computers that leverage quantum mechanics on a practical scale. This is why, as we look toward the future creation of full-fledged quantum computers, people have proposed simulators which use software running on classical computers to simulate the behavior of quantum computers. This will make it possible to test quantum computer applications in advance.

For now, simulators are used to apply these techniques to various applications, with the belief that when full-fledged quantum computers become available in the future, we will be able to replace the simulators with hardware. By using a simulator to provide an environment with the same interfaces, all kinds of application ideas can be sought from around the world, even before there is any practical hardware to implement them on.

Several state vector methods have been proposed for gate-based simulators, but even supercomputer simulations are limited to roughly 50 quantum bits, so they are not yet feasible.

On the other hand, Ising machines are known to be able to produce practical and meaningful solutions on simulators, even for large-scale problems that cannot be solved using modern hardware. This is why they are being applied in simulators before large-scale hardware becomes available.

Quantum computer technologies are therefore divided into general-purpose systems and systems designed specifically for combinatorial optimization problems. They are also divided into hardware and software (simulator) systems, producing four categories: “gate-based hardware,” “gate-based simulators,” “Ising machine hardware,” and “Ising machine simulators” (Fig. 2).

The simulated bifurcation machines developed by us are Ising machine simulators, but they offer superb performance, sometimes even surpassing the performance of actual Ising machines (Ising machine hardware). Because of this, they are also software that can be used to solve problems that were once impossible to unsolved.

We have leveraged our technical development of software and our expertise in various fields to create the Simulated Quantum-inspired Bifurcation Machine +, or SQBM+. This quantum-inspired optimization solution makes it possible to rapidly produce highly accurate approximate solutions to combinatorial optimization problems using classical computers.

Let’s look at what we mean when we say that SQBM+ is “quantum-inspired.”

SQBM+ is based on the Simulated Bifurcation Algorithm (SB Algorithm) which Toshiba’s Corporate Research & Development Center discovered in 2018. The SB Algorithm is an algorithm that simulates the classicalization of a quantum bifurcation machine. It was created based on a quantum computer called a quantum bifurcation machine, so it is “quantum-inspired.”

Next, let’s look at the steps involved in discovering the SB Algorithm in detail.

The quantum bifurcation machine is a quantum computer that we are researching on its own. It utilizes optical mechanisms, and theoretically is both a gate-based system and an Ising machine.

The first step in the discovery of the SB Algorithm was the classicalization of quantum bifurcation machine behavior.

In the early 20th century, when quantum mechanics were first becoming established, classical mechanics were often used to make inferences about quantum mechanics. Hamiltonian equations (classical mechanics equations) were converted into Schrödinger’s equations (quantum mechanics equations) in a process known as “quantization.”

The inverse of quantization is called “classicalization.” The SB Algorithm transforms a Schrödinger’s equation, which expresses the behavior of a quantum bifurcation machine, into the form of a Hamiltonian equation. In other words, we converted the equations of a quantum bifurcation machine from quantum mechanics formalism to classical mechanics formalism.

We tentatively refer to the quantum bifurcation machine, transformed into classical mechanics, as a “classical bifurcation machine.” This classical bifurcation machine should operate (approximate) in the same way as quantum bifurcation machines, because it is simply a re-expression of quantum bifurcation machines in the theory of classical mechanics. If the quantum bifurcation machine could function as an Ising machine and solve a combinatorial optimization problem, then the classical bifurcation machine should also be able to solve the combinatorial optimization problem (Fig. 3).

The classical bifurcation machine is a purely theoretical one. However, even if it is not actually constructed, the process of classicalization produces a formula, making it possible to use numerical calculation to simulate machine operation. A trial run of this process was the next step in the discovery of the SB Algorithm.

When numerical calculation was actually attempted, it was discovered that straightforward classicalization of Schrödinger’s equation, which represents the operation of a quantum bifurcation machine, produced results that were excessively complex and not suited to numerical calculation. For example, the Hamiltonian equation produced by classicalization includes an element that contains the product of variables that correspond to position and momentum within a function that indicates the energy of a system (known as the Hamiltonian). Each time the system needs to progress to the next step it must solve an additional formula because the formula includes this element, making the numerical calculation process less efficient. Insights from another field helped solve this problem.

Numerical calculations for systems based on Hamiltonian equations have been used for roughly two centuries in the field of celestial mechanics and for almost 70 years in the field of molecular dynamics.

When the Toshiba Corporate Research & Development Center first came up with the SB Algorithm, it had members with experience in high-speed molecular dynamics computation, so Hamiltonian equations were reviewed using insights from molecular dynamics. The Center arrived at the idea of dramatically simplifying the fundamental Hamiltonian equations and then applying the symplectic Euler method, a simple and fast numerical calculation method suitable for use in simulations (Fig. 4).

Simplifying the Hamiltonian equation and applying the symplectic Euler method produced the SB Algorithm. With this algorithm, the time-intensive matrix calculations performed within a step only needed to be performed once. All of the other processes were extremely simple and the overall system achieved an extremely high level of parallelism. This property is highly suited to use in modern Graphics Processing Units (GPUs).

* Implementation in GPUs is introduced in detail in the second article of this series.

Of course, even if this high speed calculation were made possible, it would be meaningless unless it also produced high quality solutions. Actual testing of the algorithm found that numerical calculation performed on the simplified Hamiltonian equations produced high quality solutions to combinatorial optimization problems. We believe that the idea of bifurcation is at work behind this algorithm.

In the first issue of this running feature, we introduced the structure of the quantum-inspired technologies that play a critical role in SQBM+, which is based on Ising machines. In the second issue, we will explain bifurcation. We will also explain speed and accuracy improvements achieved using SQBM+ GPUs, the future potential of the SB Algorithm, and an overall understanding of quantum-inspired optimization technologies.

• Quantum-Inspired Optimization Solutions “SQBM+”