| 講演名 | 2022-10-21 イジングモデルにおけるスピンの2重化による高速求解の研究 福井 香純(東京農工大), 藤吉 邦洋(東京農工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | イジングモデルに基づいた組合せ最適化問題の解法は、組合せ最適化問題をイジングモデルにマッピングしてエネルギーが小さくなるようにスピンの状態を確率的に更新することで準最適解を求められると期待されているが、その一方で相互作用でつながっているスピンを同時に更新すると解の質が悪くなる可能性がある。そこで、スピンを二重化することでイジングモデルを相互作用を枝とすると二部グラフな構造とし、相互作用で繋がっていないという条件を満たしながら全スピンを2回で更新することを可能にし、問題を高速に解く手法を提案する。そして計算機実験により、二重化したスピンの間にどう相互作用を付けるのが好ましいかを検討する。本稿ではナップザック問題に適用して計算機実験を行い、相互作用は二重化することなく、できる限り均等に接続する方がより良い解が得られると考えられる。 |
| 抄録(英) | The solution of combinatorial optimization problems based on the Ising model may obtain a quasi-optimal solution by mapping the combinatorial optimization problem to the Ising model and stochastically updating the spin states so that the energy is reduced. On the other hand, updating the spins connected by interactions at the same time may result in a poor quality solution. Therefore, we propose a method to solve the problem quickly by making the Ising model a bipartite graph with the interaction as a edge by duplicating the spins, and updating all spins by updating them only by two times satisfying the condition that spins connected by interaction should not be updated at the same time. Then, by computer experiments, we investigate how the interaction should be put between the duplicated spins. In this paper, a computer experiment was conducted by applying it to the knapsack problem. Better solutions are obtained if interactions are connected as evenly as possible without duplication. |
| キーワード(和) | イジングモデル / イジングマシン / 量子アニーリング / 組合せ最適化問題 |
| キーワード(英) | Ising model / Ising computer / Quantum annealing / Combinatorial Optimization Problem |
| 資料番号 | CAS2022-30,NLP2022-50 |
| 発行日 | 2022-10-13 (CAS, NLP) |
| 研究会情報 | |
| 研究会 | CAS / NLP |
|---|---|
| 開催期間 | 2022/10/20(から2日開催) |
| 開催地（和） | 新潟大学駅南キャンパスときめいと |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 前田 義信(新潟大) / 常田 明夫(熊本大) |
| 委員長氏名（英） | Yoshinobu Maeda(Niigata Univ.) / Akio Tsuneda(Kumamoto Univ.) |
| 副委員長氏名（和） | 相原 康敏(オムニビジョン) / 鳥飼 弘幸(法政大) |
| 副委員長氏名（英） | Yasutoshi Aibara(OmniVision) / Hiroyuki Torikai(Hosei Univ.) |
| 幹事氏名（和） | 伊藤 尚(富山高専) / 鈴木 寛人(ルネサスエレクトロニクス) / 吉岡 大三郎(崇城大) / 伊藤 大輔(岐阜大) |
| 幹事氏名（英） | Nao Ito(NIT, Toyama college) / Hiroto Suzuki(Renesas Electronics) / Daizaburo Yoshioka(Sojo Univ.) / Daisuke Ito(Gifu Univ.) |
| 幹事補佐氏名（和） | 佐藤 隆英(山梨大) / 山口 基(テクノプロ) / 下田 真二(ソニーセミコンダクタソリューションズ) / 越田 俊介(八戸工大) / 横井 裕一(長崎大) / 山仲 芳和(宇都宮大) |
| 幹事補佐氏名（英） | Takahide Sato(Univ. of Yamanashi) / Motoi Yamaguchi(TECHNOPRO) / Shinji Shimoda(Sony Semiconductor Solutions) / Shunsuke Koshita(Hachinohe Inst. of Tech.) / Yuichi Yokoi(Nagasaki Univ.) / Yoshikazu Yamanaka(Utsunomiya Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Circuits and Systems / Technical Committee on Nonlinear Problems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | イジングモデルにおけるスピンの2重化による高速求解の研究 |
| サブタイトル（和） | |
| タイトル（英） | Rapid Solving by Duplicating Spins in Ising Model |
| サブタイトル（和） | |
| キーワード(1)（和/英） | イジングモデル / Ising model |
| キーワード(2)（和/英） | イジングマシン / Ising computer |
| キーワード(3)（和/英） | 量子アニーリング / Quantum annealing |
| キーワード(4)（和/英） | 組合せ最適化問題 / Combinatorial Optimization Problem |
| 第 1 著者 氏名（和/英） | 福井 香純 / Kasumi Fukui |
| 第 1 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro Fujiyoshi |
| 第 2 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 発表年月日 | 2022-10-21 |
| 資料番号 | CAS2022-30,NLP2022-50 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | CAS-219,NLP-220 |
| ページ範囲 | pp.56-59(CAS), pp.56-59(NLP), |
| ページ数 | 4 |
| 発行日 | 2022-10-13 (CAS, NLP) |