The search functionality is under construction.

The search functionality is under construction.

Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical *Ising model*, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.9 pp.1696-1706

- Publication Date
- 2019/09/01

- Publicized
- 2019/06/10

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2018EDP7411

- Type of Manuscript
- PAPER

- Category
- Fundamentals of Information Systems

Daisuke OKU

Waseda University

Kotaro TERADA

Waseda University

Masato HAYASHI

Hitachi, Ltd.

Masanao YAMAOKA

Hitachi, Ltd.

Shu TANAKA

Waseda University,Japan Science and Technology Agency

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

Daisuke OKU, Kotaro TERADA, Masato HAYASHI, Masanao YAMAOKA, Shu TANAKA, Nozomu TOGAWA, "A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 9, pp. 1696-1706, September 2019, doi: 10.1587/transinf.2018EDP7411.

Abstract: Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical *Ising model*, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7411/_p

Copy

@ARTICLE{e102-d_9_1696,

author={Daisuke OKU, Kotaro TERADA, Masato HAYASHI, Masanao YAMAOKA, Shu TANAKA, Nozomu TOGAWA, },

journal={IEICE TRANSACTIONS on Information},

title={A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines},

year={2019},

volume={E102-D},

number={9},

pages={1696-1706},

abstract={Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical *Ising model*, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.},

keywords={},

doi={10.1587/transinf.2018EDP7411},

ISSN={1745-1361},

month={September},}

Copy

TY - JOUR

TI - A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines

T2 - IEICE TRANSACTIONS on Information

SP - 1696

EP - 1706

AU - Daisuke OKU

AU - Kotaro TERADA

AU - Masato HAYASHI

AU - Masanao YAMAOKA

AU - Shu TANAKA

AU - Nozomu TOGAWA

PY - 2019

DO - 10.1587/transinf.2018EDP7411

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E102-D

IS - 9

JA - IEICE TRANSACTIONS on Information

Y1 - September 2019

AB - Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical *Ising model*, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

ER -