On August 30, Hitachi announced the “Momentum Annealing” algorithm that can calculate combinatorial optimization problems at high speed. When the same algorithm was implemented on four NVIDIA GPUs, it was possible to calculate an approximate solution of a large-scale problem called “100,000 variables and fully connected” in less than a second.

“Momentum annealing” algorithm that can calculate combinatorial optimization problems at high speed
Momentum annealing (MA) is one of the algorithms that approximates the “Ising model” representing the combinatorial optimization problem using a conventional computer. Combinatorial optimization calculations are expected to be applied to social and business issues such as traffic congestion and financial portfolio optimization.

There are two approaches to solving the Ising model: “quantum annealing” using quantum effects, and “simulated annealing” (SA) that mimics quantum annealing on a conventional computer. Toshiba’s “simulated branch algorithm” announced in April, which can solve combinatorial optimization problems faster and larger than quantum computers, is also used to solve the Ising model.

MA is an algorithm that modifies SA and enables parallel calculation of all connections. Takuya Okuyama, one of the developers of MA, says, “Because parallel processing is possible, the amount of computation can be reduced even if the problem scale increases.”

“ Full join or parallel computation ”-overcoming conventional problems
There were two problems with Hitachi’s traditional approach at SA. “It is not a full join” and “SA is in principle difficult to parallelize”.

The Ising model multiplies spins (variables) indicating +1 or -1 by a variable representing “interaction”. The smaller the sum of all the values, the closer to the optimal solution for the combination. Each algorithm that solves the Ising model calculates so that the value of the spin is properly determined so that the sum is small.

Ising model Ising model
Representing combinatorial optimization problems with Ising models Various algorithms have been developed to solve Ising models at high speed
“In principle, in SA, connected spins cannot be updated at the same time,” says Okuyama. In other words, in the “all coupling problem” in which all the spins interact with each other, high-speed computation by parallelization is impossible with SA.

In principle, parallel calculation is not possible with a fully coupled SA.
Conversely, spins without interaction can be updated simultaneously. For this reason, Hitachi has made a CMOS circuit dedicated to annealing that can solve the Ising model of “adjacent coupling” in which only adjacent spins interact, and has approached the problem of large-scale variables.

However, in order to solve the full connection problem in the adjacent connection circuit, a variable mapping operation called “embedding” is required. Mr. Okuyama reveals that the problem is that if the entire coupling problem is embedded in an adjacent coupling circuit, the spin will increase in the order of a square.

When the problem of total coupling is converted into a lattice-like adjacent coupling model, the spin increases by the square
Hitachi’s CMOS annealing can handle the 100,000 variable / adjacent connection problem, but if we try to handle the full connection problem, it will be reduced to about 300 variables.

Therefore, Mr. Okuyama and others devised a model that can separate spins, while being equivalent to the Ising model with all bonds.

Represent all connections with a “bipartite graph” Update all variables in 2 steps
Okuyama et al. Converted the fully connected Ising model into a graph called “bipartite graph”. For example, when a 7-variable fully coupled model is converted into a bipartite graph, it becomes a graph of 14 variables with 7 variables on the left and right.