The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les problèmes d’optimisation combinatoire avec un grand espace de solutions sont difficiles à résoudre uniquement à l’aide d’ordinateurs de von Neumann. Des machines d'Ising ou de recuit ont été développées pour résoudre ces problèmes en tant qu'ordinateur prometteur Non-von Neumann. Afin d'utiliser ces machines de recuit, chaque problème d'optimisation combinatoire est mappé sur le physique Modèle Ising, qui consiste en des spins, des interactions entre eux et de leurs champs magnétiques externes. Ensuite, les machines de recuit fonctionnent de manière à rechercher l'état fondamental du modèle physique d'Ising, qui correspond à la solution optimale du problème d'optimisation combinatoire original. Un problème d'optimisation combinatoire peut être d'abord décrit par un modèle d'Ising idéal entièrement connecté, mais il est très difficile de l'intégrer à la topologie du modèle d'Ising physique d'une machine de recuit particulière, ce qui pose l'un des problèmes les plus importants dans les machines de recuit. Dans cet article, nous proposons une méthode d'intégration de modèle Ising entièrement connectée ciblant la machine de recuit CMOS. L'idée clé est que la méthode proposée reproduit chaque spin logique dans un modèle d'Ising entièrement connecté et intègre chaque spin logique dans les spins physiques avec la même longueur de chaîne. Les résultats expérimentaux à travers un problème combinatoire réel montrent que la méthode proposée obtient des plongements de spin supérieurs à la méthode standard de facto conventionnelle, en termes de temps d'intégration et de probabilité d'obtention d'une solution réalisable.
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.
Copier
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
Copier
@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},}
Copier
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 -