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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2023 IEEE 36th International System-on-Chip Conference, SOCC 2023
EditorsJurgen Becker, Andrew Marshall, Tanja Harbaum, Amlan Ganguly, Fahad Siddiqui, Kieran McLaughlin
PublisherIEEE Computer Society
ISBN (Electronic)9798350300116
DOIs
Publication statusPublished - 2023
Event36th IEEE International System-on-Chip Conference, SOCC 2023 - Santa Clara, United States
Duration: 2023 Sept 52023 Sept 8

Publication series

NameInternational System on Chip Conference
Volume2023-September
ISSN (Print)2164-1676
ISSN (Electronic)2164-1706

Conference

Conference36th IEEE International System-on-Chip Conference, SOCC 2023
Country/TerritoryUnited States
CitySanta Clara
Period23/9/523/9/8

Keywords

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

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Bit-Width Reducing Method for Ising Models Guaranteeing the Ground-State Output'. Together they form a unique fingerprint.

Cite this