An Efficient Combined Bit-Width Reducing Method for Ising Models

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Annealing machines such as quantum annealing machines and semiconductor-based annealing machines have been attracting attention as an efficient computing alternative for solving combinatorial optimization problems. They solve original combinatorial optimization problems by transforming them 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 annealing 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's bit-widths. The proposed method is composed of 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 annealing 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.

Original languageEnglish
Pages (from-to)495-508
Number of pages14
JournalIEICE Transactions on Information and Systems
VolumeE106D
Issue number4
DOIs
Publication statusPublished - 2023 Apr

Keywords

  • Ising machine
  • Ising model
  • coefficient bit-width reduction
  • combinatorial optimization problem
  • quantum annealing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'An Efficient Combined Bit-Width Reducing Method for Ising Models'. Together they form a unique fingerprint.

Cite this