イジングマシンによる並列アニーリングを用いた複数列生成法の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-21
• タイトル: イジングマシンによる並列アニーリングを用いた複数列生成法の提案
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）／慶應義塾大学大学院理工学研究科基礎理工学専攻
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）
• 著者所属: 東芝デジタルソリューションズ株式会社
• 著者所属: 東芝デジタルソリューションズ株式会社
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）
• 著者所属: 国立研究開発法人情報通信研究機構（NICT）
• 著者所属: 慶應義塾大学大学院理工学研究科基礎理工学専攻／慶應義塾大学ヒト生物学―微生物叢―量子計算研究センター(WPI-Bio2Q)
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT) / Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT)
• 著者所属(英): en
• 著者所属(英): Toshiba Digital Solutions Corporation
• 著者所属(英): en
• 著者所属(英): Toshiba Digital Solutions Corporation
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT)
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT)
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT)
• 著者所属(英): en
• 著者所属(英): National Institute of Information and Communications Technology (NICT)
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University / Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q)
• 著者名: 山下, 将司; 松浦, 巧; 高畠, 和輝; 岩崎, 元一; 鈴木, 貴大; 福島, 優; 藤原, 幹生; 佐々木, 雅英; 田中, 宗
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，イジングマシンを列生成法の一部に用いたハイブリッドアルゴリズムの研究がなされている．イジングマシンは組合せ最適化問題に対する高効率専用計算機であり，列生成法は制約条件の多い問題に対して有効とされる近似解法である．多数の制約条件がある問題においても，実質的に有効な制約条件の個数は限られてくる．そこで，列生成法では無駄な制約条件を省くために有効な制約条件を徐々に追加しながら問題を解く．このとき，有効な制約条件を見つける問題が子問題として定義される．先行研究におけるハイブリッドアルゴリズムでは，子問題をイジングマシンで解くことで効率的に有効な制約条件を見つけ，少ない制約条件の中で元の問題の解を探索する．このとき，複数の有効な制約条件を一度に追加する方法を複数列生成法と呼ぶ．複数列生成法に関する先行研究では，中性原子 QPU を用いて一度に複数個の解をサンプリングすることで複数列生成法を実現する方法が提案されており，この方法は制約条件を一度に一つずつ追加する場合と比べて全体の総計算時間が短縮されるという報告がされている．一方で，この方法では同じ子問題に対して複数回のサンプリングを行うという冗長な操作が必要となってしまう．本研究ではイジングマシンによる並列アニーリングを用いることで一回の子問題探索の中で複数の有効な制約条件を見つける方法を提案する．並列アニーリングとは，イジングマシン内部で利用可能なビット数以下で定義される問題に対して，イジングスピンを複製することで同時に複数の問題を解く手法である．この手法を応用し，本研究ではイジングマシンによる複数列生成法を構築した．ノードを共有しない K 本の最短経路探索問題に対して本提案手法を適用し，提案手法をナイーブにイジングマシンを用いた場合（ナイーブ手法）と比較した．その結果，ナイーブ手法に比べて提案手法の方が同程度の計算時間でより短い経路を探索することができた．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2024-QS-11, 号 31, p. 1-11, 発行日 2024-03-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会