A Bit-Width Reducing Method for Ising Models Guaranteeing the Ground-State Output
Yuta Yachi, Masashi Tawada, Nozomu Togawa · 2023
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.