Tokyo University of Science

MEDIA RELATIONS

2024.11.13 Wednesday

Solving Complex Problems Faster: Innovations in Ising Machine Technology

Researchers propose a novel method to make Ising machines more scalable, boosting their applicability in real-world combinatorial optimization problems

Solving Complex Problems Faster: Innovations in Ising Machine Technology

Computers are essential for solving complex problems in fields, like scheduling, logistics, and route planning, but traditional computers struggle with large-scale combinatorial optimization, as they can't efficiently process vast numbers of possibilities. To address this, researchers have explored specialized systems.

One such system is the Hopfield network, a significant artificial intelligence breakthrough from 1982, proven in 1985 to solve combinatorial optimization by representing solutions as energy levels and naturally finding the lowest energy, or optimal, solution. Building on similar ideas, Ising machines use the principles of magnetic spin to find efficient solutions by minimizing system energy through a process akin to annealing. However, a major challenge with Ising machines is their large circuit footprint, especially in fully connected systems where every spin interacts with others, complicating their scalability.

Fortunately, a research team from the Tokyo University of Science, Japan, has been working towards finding solutions to this problem related to Ising machines. In a recent study led by Professor Takayuki Kawahara, they reported an innovative method that can halve the number of interactions that need to be physically implemented. Their findings were published in the journal IEEE Access on October 01, 2024.

The proposed method focuses on visualizing the interactions between spins as a two-dimensional matrix, where each element represents the interaction between two specific spins. Since these interactions are 'symmetric' (i.e., the interaction between Spin 1 and Spin 2 is the same as that between Spin 2 and Spin 1), half of the interaction matrix is redundant and can be omitted—this concept has been around for several years. In 2020, Prof. Kawahara and colleagues presented a method to fold and rearrange the remaining half of the interaction matrix into a rectangle shape to minimize the circuit footprint. While this led to efficient parallel computations, the wiring required to read the interactions and update the spin values became more complex and harder to scale up.

In this study, the researchers proposed a different way of halving the interaction matrix that leads to better scalability in circuitry. They divided the matrix into four sections and halved each of these sections individually, alternatively preserving either the 'top' or 'bottom' halves of each submatrix. Then, they folded and rearranged the remaining elements into a rectangular shape, unlike the previous approach, which retained the regularity of its arrangement.

Leveraging this crucial detail, the researchers implemented a fully coupled Ising machine based on this technique on their previously developed custom circuit containing 16 field-programmable gate arrays (FPGAs). "Using the proposed approach, we were able to implement 384 spins on only eight FPGA chips. In other words, two independent and fully connected Ising machines could be implemented on the same board," remarks Prof. Kawahara, "Using these machines, two classic combinatorial optimization problems were solved simultaneously—namely, the max-cut problem and four-color problem."

The performance of the circuit developed for this demo was astounding, especially when compared to how slow a conventional computer would be in the same situation. "We found that the performance ratio of two independent 384-spin fully coupled Ising machines was about 400 times better than simulating one Ising machine on a regular Core i7-4790 CPU to solve the two problems sequentially," reports Kawahara, excited about the results.

In the future, these cutting-edge developments will pave the way to scalable Ising machines suitable for real-world applications such as faster molecular simulations to accelerate drug and materials discovery. Moreover, improving the efficiency of data centers and the electrical power grid is also feasible to use cases, which align well with global sustainability goals of reducing the carbon footprint of emerging technologies like electric vehicles and 5G/6G telecommunications. As innovations continue to unfold, scalable Ising machines may soon become invaluable tools across industries, transforming how we tackle some of the world's most complex optimization challenges.

Solving Complex Problems Faster: Innovations in Ising Machine Technology

Image title: Structure of a fully coupled neural network
Image caption: (a) This diagram depicts fully connected neurons or spins, where each element interacts with every other. (b) Although each spin can only take one of two values, the activation function used to update it is based on the sum of all its interactions, with state transitions aimed at decreasing the overall energy of the network. (c) Different types of networks use different mechanisms to handle state transitions. Ising machines are stochastic, unlike Hopfield networks.
Image credit: Takayuki Kawahara from Tokyo University of Science, Japan
License type: Original content
Usage restrictions: Cannot be reused without permission.

Solving Complex Problems Faster: Innovations in Ising Machine Technology

Image title: Practical demonstration of the proposed technique
Image caption: The circuit developed as a demo could solve two classic combinatorial optimization problems simultaneously, namely the max-cut problem (top) and the four-color problem (bottom).
Image credit: Takayuki Kawahara from Tokyo University of Science, Japan
License type: Original content
Usage restrictions: Cannot be reused without permission.

Reference
Title of original paper  : Implementation and Evaluation of Two Independent Ising Machines on Same FPGA Board by Reducing Number of Interactions Inside Ising Machine
Journal  : IEEE Access
DOI  : 10.1109/ACCESS.2024.3471695
About The Tokyo University of Science

Tokyo University of Science (TUS) is a well-known and respected university, and the largest science-specialized private research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Established in 1881, the university has continually contributed to Japan's development in science through inculcating the love for science in researchers, technicians, and educators.

With a mission of "Creating science and technology for the harmonious development of nature, human beings, and society," TUS has undertaken a wide range of research from basic to applied science. TUS has embraced a multidisciplinary approach to research and undertaken intensive study in some of today's most vital fields. TUS is a meritocracy where the best in science is recognized and nurtured. It is the only private university in Japan that has produced a Nobel Prize winner and the only private university in Asia to produce Nobel Prize winners within the natural sciences field.

Tokyo University of Science(About TUS)

Research List

Press Releases List

About Professor Takayuki Kawahara
from Tokyo University of Science

Dr.Takayuki Kawahara is a Professor in the Department of Electrical Engineering at Tokyo University of Science, Japan. He earned his Ph.D. from Kyushu University in 1993. With over 8,500 citations, Prof. Kawahara's current research is dedicated to sustainable electronics, with a specific focus on low-power AI devices and circuits, sensors, spin current applications, and quantum computing techniques. He has won several awards, including the 2014 IEICE Electronics Society Award and the Prize for Science and Technology (Development Category) at the FY2017 Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science, and Technology of Japan.
Official TUS website

Funding information

This work was supported in part by the Japan Society for the Promotion of Science (JSPS) KAKENHI under Grant 22H01559 and Grant 23K22829.

Back

Contact Us

Public Relations Division, Tokyo University of Science

e-mail: mediaoffice(at sign)admin.tus.ac.jp

1-3, KAGURAZAKA SHINJUKU-KU TOKYO 162-8601 JAPAN