Sparsely connected and Fully connected (Part 2)

Overview

In Sparsely connected and Fully connected (Part 1), we discussed how the structure of the network of Ising models is chosen according to whether it represents conceptual or physical coupling of events. In the second part, we will discuss the structural specifications and technical challenges of the annealing machine that actually derives the ground state of the Ising model.

Why do we have Sparsely connected annealing machines?

The CMOS annealing machines running on the Annealing Cloud Web are sparsely connected. D-Wave's quantum annealing machines are also sparsely connected. Why do they have a sparsely connected structure instead of a fully connected structure? As explained in the previous part, there are many combinatorial optimization problems, such as the number partitioning problem and the timetable problem, in which the fully connected Ising model is chosen because of the conceptual coupling of variables that occurs. Therefore, a not-insignificant amount people may say that if all the spins of the annealing machine are connected between all the spins, then it must be better.

This is because, as explained in the input data preparation, the fully connected interaction requires $O(N^2)$, which is physically difficult to implement. If you want to solve an fully connected problem with 10 spins, you only need 9 interactions per spin, so 45 in total, but problem of 10 spins is not very useful since the annealing machine is expected to solve a large problem. If you want to 100 spins to be fully connected, it is need to have 99 interactions to per spin.

How are fully connected annealing machines implemented?

Fully connected annealing machines also exist: the Coherent Ising Machine (CIM) from NTT and NII, the Digital Annealer (DA) from Fujitsu, Toshiba's SQBM+, Fixstars Amplify Annealing Engine (AE), and Hitachi's 2019 Momentum Annealing (MA) version of CMOS annealing is fully connected.

How can fully connected annealing machines be implemented? Most fully connected machines are implemented in software, which reproduces the interactions between spins that are virtually connected, rather than physically connecting the interactions in hardware as is done in sparsely connected machines such as ASICs. In general, the software approach takes more computation time than using hardware, but it can implement complex connections. Hitachi's MA version of CMOS annealing uses an algorithm that makes the process as fast as possible by increasing the parallelism of the calculations.

Features of two types of CMOS annealing

Let's take a look at the usage features that both of the ASIC versions of CMOS annealing can run on Annealing Cloud Web and the MA version of CMOS annealing described above.

The ASIC version is a sparsely connected machine that implements the Ising model of King's graph on a semiconductor CMOS. The latest machines are slightly larger than a postcard and can be greatly expanded by simply connecting ASIC boards vertically and horizontally with cables. They are characterized by their ease of expansion, low power operation, and fast processing time to derive the optimal solution.

Currently, a large-scale hardware capable of inputting 2.25M bits has been installed in the Hitachi Research and Development Group ”Kyoso-no-Mori” and a demonstration of a signal control optimization for congestion relief has been opened to the public, so that guests can see optimization of an entire intersection consisting of 64 x 64 grid roads on the spot. Although this large-scale hardware cannot solve problems that require a fully connected grid as it is, there is no limit to the number of spins that can be input if the problem can be represented by a sparsely connected Ising model, such as signal control. In fact, the signal optimization process can be performed on a 1500 x 1500 road network if run on the full specifications of this 2.25 Mbit large-scale hardware.

On the other hand, the MA version of CMOS annealing has the greatest advantage of being able to solve fully connected problems, as mentioned earlier, and has been applied to work shift optimization and financial portfolio optimization, reaching practical use before the ASIC version^{*Note1, 2}.

Graph embedding algorithm

There are also efforts to solve the problem of fully connected with a sparsely connected annealing machine. One such effort is the "graph embedding algorithm"^*Note3.

In graph theory, Ising model spins are represented as "vertices" and interactions as "edges.

See the figure below, which illustrates graph embedding. On the left is the fully connected Ising model. The result of graph embedding is shown on the right.

Spin number (1) is one in the fully connected Ising model, but it is split (duplicated) into 8 spins as shown on the right in order to connect with all other spins. This means that the connection to all other spins can be represented by a sparsely connected graph.

Thus, replacing a graph structure of complex shape with a sparsely connected graph structure by partitioning vertices is called graph embedding. Graph embedding allows us to connect vertices that could not be made adjacent to each other on the hardware, so that even a machine with a sparsely connected structure can handle problems requiring a fully connected structure.

There are still a few problems which remain to be solved before embedding can be used effectively: the first problem is that the number of vertices to be split must be kept as small as possible. The second problem is when using the embedding algorithm, computation requirements increase to determine which vertices to split and to create the input data associated with the increased number of vertices must be increased. Although the time to find the optimal solution itself is extremely short when using an annealing machine, the full processing time may be longer because of the preprocessing time required for the reasons mentioned above.

To solve these problems, researchers and engineers are exploring various ideas and methods to break through hardware limitations using graph theory. You may be the one to make the next move.

Summary

The ASIC version of CMOS annealing machines implements the interaction through physical connections, which are limited in the number of connections, but have high computational speed.
Most annealing machines that solve the fully connected Ising model implement the interactions virtually by software.
The embedding algorithm designed to input the fully connected Ising model into a sparsely connected machine has several challenges, ideas, and methods, all of which are needed to break through the issues.

What is a combinatorial optimization problem?

Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.

Optimization of researcher shifts with consideration for COVID-19 infection control

In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.

Optimize an insurer's reinsurance portfolio

This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.

If you want to know how to use an annealing machine

Easy-to-learn optimization flow

For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".

Math for Annealing Machines

This article provides an easy-to-understand explanation of the mathematical assumptions you need to understand, focusing on "quadratic" and "discrete," which are some of the characteristics of the problems that annealing machines excel at solving.