著者
Daisuke OKU Kotaro TERADA Masato HAYASHI Masanao YAMAOKA Shu TANAKA Nozomu TOGAWA
出版者
The Institute of Electronics, Information and Communication Engineers
雑誌
IEICE TRANSACTIONS on Information and Systems (ISSN:09168532)
巻号頁・発行日
vol.E102-D, no.9, pp.1696-1706, 2019-09-01
被引用文献数
23

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.

言及状況

外部データベース (DOI)

Twitter (9 users, 11 posts, 28 favorites)

早稲田大学・戸川研究室と日立製作所との共同研究の論文が論文誌に掲載されました。NEDO事業「組合せ最適化処理に向けた革新的アニーリングマシンの研究開発」の成果です。 A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines https://t.co/pPoa9zWNIG
論文がパブリッシュされました。 A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines https://t.co/jB3VFFKmLd

収集済み URL リスト