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
대규모 솔루션 공간의 조합 최적화 문제는 폰 노이만 컴퓨터만으로는 해결하기 어렵습니다. 유망한 Non-von Neumann 컴퓨터로서 이러한 문제를 해결하기 위해 이징 기계 또는 어닐링 기계가 개발되었습니다. 이러한 어닐링 기계를 사용하기 위해 모든 조합 최적화 문제는 물리적인 문제에 매핑됩니다. Ising 모델, 이는 스핀, 이들 사이의 상호 작용 및 외부 자기장으로 구성됩니다. 그런 다음 어닐링 기계는 원래 조합 최적화 문제의 최적 솔루션에 해당하는 물리적 Ising 모델의 바닥 상태를 검색하도록 작동합니다. 조합 최적화 문제는 먼저 이상적인 완전 연결형 Ising 모델로 설명할 수 있지만 이를 특정 어닐링 기계의 물리적 Ising 모델 토폴로지에 삽입하는 것은 매우 어렵습니다. 이는 어닐링 기계에서 가장 큰 문제 중 하나를 야기합니다. 본 논문에서는 CMOS 어닐링 장비를 대상으로 하는 완전 연결형 Ising 모델 임베딩 방법을 제안합니다. 핵심 아이디어는 제안된 방법이 완전히 연결된 Ising 모델의 모든 논리적 스핀을 복제하고 각 논리적 스핀을 동일한 체인 길이를 가진 물리적 스핀에 삽입한다는 것입니다. 실제 조합 문제를 통한 실험 결과, 제안한 방법은 기존의 사실상 표준 방법에 비해 임베딩 시간과 실현 가능한 해를 얻을 확률 측면에서 우수한 스핀 임베딩을 얻을 수 있음을 보여주었다.
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.
부
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
부
@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},}
부
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 -