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

研究成果: Conference contribution

抄録

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.

本文言語English
ホスト出版物のタイトルProceedings - 2023 IEEE 36th International System-on-Chip Conference, SOCC 2023
編集者Jurgen Becker, Andrew Marshall, Tanja Harbaum, Amlan Ganguly, Fahad Siddiqui, Kieran McLaughlin
出版社IEEE Computer Society
ISBN(電子版)9798350300116
DOI
出版ステータスPublished - 2023
イベント36th IEEE International System-on-Chip Conference, SOCC 2023 - Santa Clara, United States
継続期間: 2023 9月 52023 9月 8

出版物シリーズ

名前International System on Chip Conference
2023-September
ISSN(印刷版)2164-1676
ISSN(電子版)2164-1706

Conference

Conference36th IEEE International System-on-Chip Conference, SOCC 2023
国/地域United States
CitySanta Clara
Period23/9/523/9/8

ASJC Scopus subject areas

  • ハードウェアとアーキテクチャ
  • 制御およびシステム工学
  • 電子工学および電気工学

フィンガープリント

「A Bit-Width Reducing Method for Ising Models Guaranteeing the Ground-State Output」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル