文献

J-GLOBAL ID：202002267049379923   整理番号：20A0117292

イジングモデルによる類似誘導部分グラフ同型問題の解法

著者 (9件)： 吉村夏一 (早稲田大 大学院基幹理工学研究科) ,  多和田雅師 (早稲田大 大学院基幹理工学研究科) ,  田中宗 (早稲田大 グリーン・コンピューティング・システム研究機構) ,  田中宗 (JST-さきがけ) ,  新井淳也 (NTT ソフトウェアイノベーションセ) ,  巴徳瑪 (NTT ソフトウェアイノベーションセ) ,  八木哲志 (NTT ソフトウェアイノベーションセ) ,  内山寛之 (NTT ソフトウェアイノベーションセ) ,  戸川望 (早稲田大 大学院基幹理工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 119  号： 282(VLD2019 29-53)  ページ： 103-108  発行年： 2019年11月06日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： イジングマシンを用いて組合せ最適化問題の準最適解を高速に得るためには,組合せ最適化問題からイジングモデルへのマッピングを考える必要がある.本研究では組合せ最適化問題のひとつである誘導部分グラフ同型問題に注目する.誘導部分グラフ同型問題は対象となるグラフ構造の中に特定の構造を持つ部分グラフが存在するか否かを判定する問題であり,集積回路から不正回路を探索する際や化学物質中における特定の化学結合パタンを探索する際など多くの現実問題に出現する.特にそれらの現実問題では厳密には特定のグラフ構造を持たないとき,近い構造を有する不正回路や化学結合パタンを探索したいという需要が存在する.本稿では,誘導部分グラフ同型問題をイジングマシンによって類似的に解く手法を提案する.グラフ構造の類似性の尺度としてグラフ辺編集距離を定義する.厳密に誘導部分グラフ同型性が成り立つときはグラフ辺編集距離が0であるとし,誘導部分グラフ同型性が成り立たないときはグラフ辺編集距離をもとに定量的に近いグラフを探索する.提案手法ではイジングモデルのエネルギー関数として,一方のグラフが他方のグラフに対して,最も近しい誘導部分グラフとなるときイジングモデルのエネルギーが最小となるよう定式化する.定式化されたイジングモデルにより,定義したグラフ辺編集距離のもと誘導部分グラフ同型に最も近いグラフを探索することを可能にする.提案手法により類似誘導部分グラフ同型問題を実際にイジングモデル上で求解した結果を報告する.(著者抄録)

シソーラス用語： *組合せ最適化問題 ,  *Ising模型 ,  アルゴリズム ,  同形写像 ,  グラフ理論 ,  *数値計算
準シソーラス用語： グラフ同型

分類 (1件)： 数値計算  (JE02000J)

引用文献 (18件)：

• P. I. Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolkacheva, F. Altomare, A. J. Berkley, R. Harris, J. P. Hilton, T. Lanting, A. J. Przybysz, J. Whittaker,“Architectural considerations in the design of a superconducting quantum annealing processor,” IEEE Transactions on Applied Superconductivity, vol. 24, pp. 1-10, 2014.
• V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Babbush, V. Smelyanskiy, J. Martinis, H. Neven,“What is the computational value of finite-range tunneling?” Physical Review X, vol. 6, no. 3, p. 031015, 2016.
• S. Fortin,“The graph isomorphism problem,” Department of Computing Science, University of Alberta, Tech. Rep., 1996.
• H. Goto, K. Tatsumura, A. R. Dixon,“Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems,” Science advances, vol. 5, no. 4, p.eaav2372, 2019.
• W. K. Hastings,“Monte Carlo sampling methods using Markov chains and their applications,” 1970.

タイトルに関連する用語 (6件)： イジングモデル ,  類似 ,  誘導 ,  グラフ同型 ,  問題 ,  解法