Combinatorial optimization problems (COPs) arise in various fields such as shift scheduling, traffic routing, and drug development. However, they are challenging to solve using traditional computers in a practical timeframe. Alternatively, annealing processors (APs), which are specialized hardware for solving COPs, have gained significant attention. They are based on the Ising model, in which COP variables are presented as magnetic spins and constraints as interactions between spins. Solutions are obtained by finding the spin state that minimizes the energy of the system.
There are two types of Ising models, the sparsely-coupled model and the fully-coupled model. Sparsely-coupled models offer high scalability by allowing more spins but require COPs to be transformed to fit the model. Fully-coupled models, on the other hand, allow any COP to be mapped directly without transformation, making them highly desirable. However, they are limited in capacity (number of spins) and precision (interaction bit width). While previous studies have implemented fully-Ising models using a scalable structure that can increase the capacity using application-specific integrated circuits (ASICs), their interaction bit-width is fixed, making certain COPs difficult to solve.
In a groundbreaking study, a research team from Japan, led by Professor Takayuki Kawahara from the Department of Electrical Engineering at Tokyo University of Science, Japan, developed an innovative dual scalable annealing processing system (DSAPS) that can simultaneously scale both capacity and precision using the same scalable structure. Their study was published online in the journal IEEE Access on March 21, 2025, and was published in Volume 13 on March 31, 2025, and presented at the 2024 International Conference on Microelectronics.
DSAPS achieves dual scalability by manipulating ∆E blocks, responsible for computing the energy of the system, using two structures. i.e., the conventional high-capacity structure and a novel high-precision structure. Each ∆E block is equivalent to a large-scale integrated (LSI) chip on a CMOS-based AP board and includes the interaction matrix and the spins. The high-capacity structure divides each ∆E block into smaller sub-blocks that are calculated separately and then added together by a control block on the AP board. This allows the number of spins to be increased by simply subdividing the ∆E block into more sub-blocks.
The high-precision structure enables multiple ∆E blocks, with the same spin numbers and interactions, to be calculated at different bit levels. The control block then combines their calculations by performing bit shifts, resulting in a higher overall interaction bit-width. For example, a system with four ∆E blocks operating at different bit levels with a single control block can handle four times the original interaction bit width.
“DSAPS is a revolutionary system that allows simultaneous expansion of the number of spins and interaction bit width by controlling multiple identical LSI chips with a single field programmable gate array control block,” highlights Prof. Kawahara. “Additionally, this system can be used for both sparsely-coupled and fully coupled Ising models.”
To demonstrate the system’s practicality, the researchers implemented two DSAPS configurations on a CMOS-AP board using spin threads: one with 2048 spins, with 10-bit interactions and four threads, and another with 1024 spins, 37-bit interactions, and two threads. This is a considerable improvement over ASICs, which typically have interaction bit widths of only 4 to 8 bits.
Validation tests on MAX-CUT problems showed that both DSAPS achieved over 99% accuracy compared to the best-known theoretical results. However, in the 0-1 knapsack problem, the DSAPS with 10-bit interaction showed a large average deviation of 99%, while the 37-bit configuration showed a much lower average deviation of only 0.73%, close to that seen in CPU-based emulations. This highlights the importance of selecting a DSAPS configuration that aligns with the characteristics of the target COP.
“This system will prove crucial in developing scalable APs for solving complex real-world COPs,” remarks Prof. Kawahara. “Our department has been promoting research on LSI implementation of fully-coupled Ising machines for the past 10 years. Starting in 2025, this system will be incorporated as one of the student experiments for all third-year students, enhancing semiconductor design education.”
Overall, this study marks a significant step forward for the development of scalable, high-precision, fully-coupled Ising machines, with promising applications in various fields.
