Novel multipolicy-based annealer for solving real-world combinatorial optimization problems

A fully connected annealer scalable to a multi-chip system and featuring a multi-policy mechanism has been designed by Tokyo Tech researchers to solve a broad class of combinatorial optimization (CO) problems relevant to real-world scenarios the world quickly and efficiently. Called Amorphica, the annealer has the ability to fine-tune parameters according to a specific target CO problem and has potential applications in logistics, economics, machine learning and so on.

The modern world has become accustomed to an efficient delivery of goods right outside the door. But did you know that realizing such efficiency requires solving a mathematical problem, namely what is the best possible route between all the destinations? This is known as the “traveling salesman problem”, and belongs to a class of mathematical problems known as “combinatorial optimization” (CO) problems.

As the number of destinations increases, the number of possible routes grows exponentially, and a brute force method based on exhaustive search for the best route becomes impractical. Instead, an approach called “annealing computing” is used to find the best route quickly without an exhaustive search.

Nevertheless, a numerical study conducted by Tokyo Tech researchers has shown that although there are many annealing calculation methods, there is no one method that is suitable for solving a wide class of CO problems. Therefore, an annealing mechanism that has multiple annealing methods (a multi-policy mechanism) is needed to target a variety of such problems.

Fortunately, the same team of researchers, led by Assistant Professor Kazushi Kawamura and Professor Masato Motomura from the Tokyo Institute of Technology (Tokyo Tech), has reported a new annealer that takes such a multi-policy approach or “metamorphic annealing”. Their findings are published in Continuation of ISSCC2023 and will be presented at the upcoming 2023 International Solid-State Circuits Conference.

“In the annealing calculation, a CO problem is represented as an energy function in terms of (pseudo) spin vectors. We start from an initially randomized spin vector configuration and then stochastically update it to find the minimum energy states by reducing its (pseudo) temperature. This closely reflects the annealing process of metals where hot metals are cooled in a controlled manner,” explains Dr. Kawamura. “Our annealer called Amorphica has several annealing methods, including a new one proposed by our team. This gives it the ability to apply the annealing method to the specific CO problem.”

The team designed Amorphica to address the limitations of previous annealers, namely that their applicability is limited to only a few CO problems. This is, firstly, due to the fact that these annealers are local coupling, which means that they can only handle spin models that have local interspin coupling. Another reason is that they do not have flexibility when it comes to annealing methods and parameter control. These problems were solved in Amorphica by using a full-connectivity spin model and incorporating finely controllable annealing methods and parameters. In addition, the team introduced a new annealing policy called “ratio-controlled parallel annealing” to improve the convergence speed and stability of existing annealing methods.

In addition, Amorphica can be expanded into a multi-chip, full-connectivity system with reduced inter-chip data transfer. By testing Amorphica against a GPU, the researchers found that it was up to 58 times faster while using only (1/500) the power consumption, meaning it achieves around 30,000 times more energy efficiency.

“With a full-connectivity annealer like Amorphica, we can now handle arbitrary topologies and densities of interspin couplings, even when they are irregular. This in turn will allow us to solve real-world CO problems such as those related to logistics, finance and machine learning, ” concludes Prof. Motomura.