Scalable and fully coupled quantum-inspired processor solves optimization problems

However, large-scale combinatorial optimization problems are very computationally intensive to solve using standard computers, making researchers turn to other approaches. One such approach is based on the "Ising model," which mathematically represents the magnetic orientation of atoms, or "spins," in a ferromagnetic material. At high temperatures, these atomic spins are oriented randomly. But as the temperature decreases, the spins line up to reach the minimum energy state where the orientation of each spin depends on its neighbors. It turns out that this process, known as "annealing," can be used to model combinatorial optimization problems such that the final state of the spins yields the optimal solution.

Researchers have tried creating annealing processors that mimic the behavior of spins using quantum devices, and have attempted to develop semiconductor devices using large-scale integration (LSI) technology aiming to do the same. In particular, Professor Takayuki Kawahara's research group at Tokyo University of Science (TUS) in Japan has been making important breakthroughs in this particular field.

In 2020, Prof. Kawahara and his colleagues presented at the 2020 international conference, IEEE SAMI 2020, one of the first fully coupled (that is, accounting for all possible spin-spin interactions instead of interactions with only neighboring spins) LSI annealing processors, comprising 512 fully-connected spins. Their work appeared in the journal IEEE Transactions on Circuits and Systems I: Regular Papers. These systems are notoriously hard to implement and upscale owing to the sheer number of connections between spins that needs to be considered. While using multiple fully connected chips in parallel was a potential solution to the scalability problem, this made the required number of interconnections (wires) between chips prohibitively large.

In a recent study published in Microprocessors and Microsystems, Prof. Kawahara and his colleague demonstrated a clever solution to this problem. They developed a new method in which the calculation of the system's energy state is divided among multiple fully coupled chips first, forming an "array calculator." A second type of chip, called "control chip," then collects the results from the rest of the chips and computes the total energy, which is used to update the values of the simulated spins. "The advantage of our approach is that the amount of data transmitted between the chips is extremely small," explains Prof. Kawahara. "Although its principle is simple, this method allows us to realize a scalable, fully connected LSI system for solving combinatorial optimization problems through simulated annealing."

The researchers successfully implemented their approach using commercial FPGA chips, which are widely used programmable semiconductor devices. They built a fully connected annealing system with 384 spins and used it to solve several optimization problems, including a 92-node graph coloring problem and a 384-node maximum cut problem. Most importantly, these proof-of-concept experiments showed that the proposed method brings true performance benefits. Compared with a standard modern CPU modeling the same annealing system, the FPGA implementation was 584 faster and 46 times more energy efficient when solving the maximum cut problem.

Now, with this successful demonstration of the operating principle of their method in FPGA, the researchers plan to take it to the next level. "We wish to produce a custom-designed LSI chip to increase the capacity and greatly improve the performance and power efficiency of our method," Prof. Kawahara remarks. "This will enable us to realize the performance required in the fields of material development and drug discovery, which involve very complex optimization problems."

Finally, Prof. Kawahara notes that he wishes to promote the implementation of their results to solve real problems in society. His group hopes to engage in joint research with companies and bring their approach to the core of semiconductor design technology, opening doors to the revival of semiconductors in Japan.