An Efficient Combined Bit-Width Reducing Method for Ising Models

Yuta YACHI; Masashi TAWADA; Nozomu TOGAWA

doi:10.1587/transinf.2022EDP7017

An Efficient Combined Bit-Width Reducing Method for Ising Models

Yuta YACHI, Masashi TAWADA, Nozomu TOGAWA

Full Text Views

13

Cite this

Summary :

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

Authors

Yuta YACHI
  Waseda University
Masashi TAWADA
  Waseda University
Nozomu TOGAWA
  Waseda University

Keyword

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

Cite this

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 -