Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC)

Solving Circuit Partitioning Based on Ising Model Mapping and High-Order Reduction

Haiyang Zhang, Rui Zhou, Yanglu She, Hao Wang, Sheng Chang

Published Jun 1, 2026• 0 citations
Publisher

Abstract

This paper addresses the Circuit Partitioning Problem by mapping it to an Ising model and proposing a high-order reduction algorithm. By introducing auxiliary variables via gadget units, high-order hypergraph interactions are systematically converted into standard quadratic forms suitable for Ising machines. We detail an FPGA implementation featuring linear annealing and optimized random number generation. Experimental results on various hypergraphs confirm that the reduced second-order model preserves the ground state of the original high-order model, accurately solving partitioning tasks while demonstrating significant hardware resource efficiency and feasibility for large-scale combinatorial optimization.

DOI
10.1109/edssc70455.2026.11736685

Related papers

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.

IEEE Transactions on Computers•Jan 24, 2023•13 citations

How to Reduce the Bit-Width of an Ising Model by Adding Auxiliary Spins

Daisuke Oku, Masashi Tawada, Shu Tanaka +1 more

Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.

IEEE Transactions on Computers•Dec 15, 2020•25 citations

A Bit-Width Reducing Method for Ising Models Guaranteeing the Ground-State Output

Yuta Yachi, Masashi Tawada, Nozomu Togawa

Ising machines are being developed as an efficient computing alternative for solving combinatorial optimization problems. Ising machines solve a combinatorial optimization problem by transforming it into a data structure called an Ising model. However, Ising machines have hardware limitations and hence the input Ising model coefficients must be limited to a certain range. Existing coefficient bit-width reducing methods do not guarantee that the output solution is optimum without adding too many extra spins. In this paper, we propose a new bit-width reducing method for Ising models. In this method, we first partition an original Ising model into several Ising models, each of which has the same graph topology, and the coefficient bit-width is reduced to be dealt with by the target Ising machine. Next, we obtain a ground-state solution for every partitioned Ising model. At that time, we can theoretically prove that, if all the partitioned Ising models have a common ground-state solution, it also gives a ground-state solution for the original non-bit-width-reduced Ising model. Experimental results demonstrate that the theorem is empirically true.

IEEE International System-on-Chip Conference (SOCC)•Sep 5, 2023•2 citations

Implementation and Evaluation of Two Independent Ising Machines on Same FPGA Board by Reducing Number of Interactions Inside Ising Machine

Shinjiro Kitahara, Taichi Megumi, Akari Endo +1 more

The development of annealing processors has progressed as a solution to large-scale combinatorial optimization problems. Inside a fully-coupled annealing machine that can handle a wide range of combinatorial optimization problems, there are elements called interactions that indicate the force between spins, the number of which is the square of the number of spins. However, the area of the circuit is greatly restricted. Therefore, we focus on the symmetry of interactions and propose a method for reducing the number of interactions by giving regularity to the two-dimensional arrangement of interactions. The interaction halving method has a high affinity with the previously published scalable fully-coupled annealing machine, and the interaction proposed this time for the 384-spin full-coupled annealing machine using 16 Field Programmable Gate Array chips shown in previous research. By applying the reduction method, we succeeded in implementing two independent 384-spin fully coupled annealing machines with 16 chips.

IEEE Access•Jan 1, 2024•1 citation

Bit-Width Reduction for Ising Models Proving the Ground State by Topologically Isomorphic n-Partition

Shu Tomita, Raio Aoki, Shinnosuke Inaba +2 more

Many consumer applications can be formulated as combinatorial optimization problems (COPs) and Ising machines can efficiently solve them, once they are transformed into Ising models. However, Ising machines have a limitation on the coefficient bit width of the input Ising model, requiring a reduction of these coefficient bit widths. In this paper, we propose a bit-width reduction method based on a topologically isomorphic n-partition. The proposed method first calculates the number, n, of partitions required to satisfy the bit-width limit, and then partitions the original Ising model into n topologically isomorphic Ising models. Furthermore, we prove that, if these n Ising models share a common ground state, that state is also the ground state of the original Ising model. Experimental results confirm the empirical correctness of the theorem and demonstrate the effectiveness of the proposed method.

International Conference on Consumer Electronics•Feb 3, 2026•0 citations

Efficient Coefficient Bit-Width Reduction Method for Ising Machines

Yuta Yachi, Yousuke Mukasa, Masashi Tawada +1 more

Ising machines such as quantum annealing machines and semiconductor-based annealing machines can solve various combinatorial optimization problems very efficiently by transforming it into a data structure called an Ising model. At that time, the bit-widths of the coefficients of the Ising model have to be kept within the range that an Ising machine can deal with. However, by reducing the Ising-model bit-widths, its minimum energy state, or ground state, may become different from that of the original one and hence the targeted combinatorial optimization problem cannot be well solved. This paper proposes an effective method for reducing Ising-model bit-widths. The proposed method is composed of the two processes: First, given an Ising model with large coefficient bit-widths, the shift method is applied to reduce its bit-widths roughly. Second, the spin-adding method is applied to further reduce its bit-widths to those that Ising machines can deal with. Without adding too many extra spins, we efficiently reduce the coefficient bit-widths of the original Ising model. Furthermore, the ground state before and after reducing the coefficient bit-widths is not much changed in most of the practical cases. Experimental evaluations demonstrate the effectiveness of the proposed method, compared to existing methods.

International Conference on Consumer Electronics•Jan 7, 2022•5 citations
This paper addresses the Circuit Partitioning Problem by mapping it to an Ising model and proposing a high-order reduction algorithm. By introducing auxiliary variables via gadget units, high-order hypergraph interactions are systematically converted into standard quadratic forms suitable for Ising machines. We detail an FPGA implementation featuring linear annealing and optimized random number generation. Experimental results on various hypergraphs confirm that the reduced second-order model preserves the ground state of the original high-order model, accurately solving partitioning tasks while demonstrating significant hardware resource efficiency and feasibility for large-scale combinatorial optimization.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.
Ising machines are being developed as an efficient computing alternative for solving combinatorial optimization problems. Ising machines solve a combinatorial optimization problem by transforming it into a data structure called an Ising model. However, Ising machines have hardware limitations and hence the input Ising model coefficients must be limited to a certain range. Existing coefficient bit-width reducing methods do not guarantee that the output solution is optimum without adding too many extra spins. In this paper, we propose a new bit-width reducing method for Ising models. In this method, we first partition an original Ising model into several Ising models, each of which has the same graph topology, and the coefficient bit-width is reduced to be dealt with by the target Ising machine. Next, we obtain a ground-state solution for every partitioned Ising model. At that time, we can theoretically prove that, if all the partitioned Ising models have a common ground-state solution, it also gives a ground-state solution for the original non-bit-width-reduced Ising model. Experimental results demonstrate that the theorem is empirically true.
The development of annealing processors has progressed as a solution to large-scale combinatorial optimization problems. Inside a fully-coupled annealing machine that can handle a wide range of combinatorial optimization problems, there are elements called interactions that indicate the force between spins, the number of which is the square of the number of spins. However, the area of the circuit is greatly restricted. Therefore, we focus on the symmetry of interactions and propose a method for reducing the number of interactions by giving regularity to the two-dimensional arrangement of interactions. The interaction halving method has a high affinity with the previously published scalable fully-coupled annealing machine, and the interaction proposed this time for the 384-spin full-coupled annealing machine using 16 Field Programmable Gate Array chips shown in previous research. By applying the reduction method, we succeeded in implementing two independent 384-spin fully coupled annealing machines with 16 chips.
Many consumer applications can be formulated as combinatorial optimization problems (COPs) and Ising machines can efficiently solve them, once they are transformed into Ising models. However, Ising machines have a limitation on the coefficient bit width of the input Ising model, requiring a reduction of these coefficient bit widths. In this paper, we propose a bit-width reduction method based on a topologically isomorphic n-partition. The proposed method first calculates the number, n, of partitions required to satisfy the bit-width limit, and then partitions the original Ising model into n topologically isomorphic Ising models. Furthermore, we prove that, if these n Ising models share a common ground state, that state is also the ground state of the original Ising model. Experimental results confirm the empirical correctness of the theorem and demonstrate the effectiveness of the proposed method.
Ising machines such as quantum annealing machines and semiconductor-based annealing machines can solve various combinatorial optimization problems very efficiently by transforming it into a data structure called an Ising model. At that time, the bit-widths of the coefficients of the Ising model have to be kept within the range that an Ising machine can deal with. However, by reducing the Ising-model bit-widths, its minimum energy state, or ground state, may become different from that of the original one and hence the targeted combinatorial optimization problem cannot be well solved. This paper proposes an effective method for reducing Ising-model bit-widths. The proposed method is composed of the two processes: First, given an Ising model with large coefficient bit-widths, the shift method is applied to reduce its bit-widths roughly. Second, the spin-adding method is applied to further reduce its bit-widths to those that Ising machines can deal with. Without adding too many extra spins, we efficiently reduce the coefficient bit-widths of the original Ising model. Furthermore, the ground state before and after reducing the coefficient bit-widths is not much changed in most of the practical cases. Experimental evaluations demonstrate the effectiveness of the proposed method, compared to existing methods.