Computers are essential for solving complex problems in fields such as 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.
A research team from the Tokyo University of Science, Japan, has been working toward 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 1, 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.
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). © Takayuki Kawahara from Tokyo University of Science, Japan
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.
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 such as 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.
More information:
Shinjiro Kitahara et al, Implementation and Evaluation of Two Independent Ising Machines on Same FPGA Board by Reducing Number of Interactions Inside Ising Machine, IEEE Access (2024). DOI: 10.1109/ACCESS.2024.3471695
Provided by
Tokyo University of Science
Citation:
Solving complex problems faster: Innovations in Ising machine technology (2024, November 13)
