The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.4 pp.495-508

- Publication Date
- 2023/04/01

- Publicized
- 2023/01/12

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2022EDP7017

- Type of Manuscript
- PAPER

- Category
- Fundamentals of Information Systems

Yuta YACHI

Waseda University

Masashi TAWADA

Waseda University

Nozomu TOGAWA

Waseda University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yuta YACHI, Masashi TAWADA, Nozomu TOGAWA, "An Efficient Combined Bit-Width Reducing Method for Ising Models" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 4, pp. 495-508, April 2023, doi: 10.1587/transinf.2022EDP7017.

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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7017/_p

Copy

@ARTICLE{e106-d_4_495,

author={Yuta YACHI, Masashi TAWADA, Nozomu TOGAWA, },

journal={IEICE TRANSACTIONS on Information},

title={An Efficient Combined Bit-Width Reducing Method for Ising Models},

year={2023},

volume={E106-D},

number={4},

pages={495-508},

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.},

keywords={},

doi={10.1587/transinf.2022EDP7017},

ISSN={1745-1361},

month={April},}

Copy

TY - JOUR

TI - An Efficient Combined Bit-Width Reducing Method for Ising Models

T2 - IEICE TRANSACTIONS on Information

SP - 495

EP - 508

AU - Yuta YACHI

AU - Masashi TAWADA

AU - Nozomu TOGAWA

PY - 2023

DO - 10.1587/transinf.2022EDP7017

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E106-D

IS - 4

JA - IEICE TRANSACTIONS on Information

Y1 - April 2023

AB - 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.

ER -