2026-03-13T01:30:09Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00233705 2025-01-19T10:01:00Z 1164:10193:11470:11538

イジングマシンによる並列アニーリングを用いた複数列生成法の提案 山下, 将司 松浦, 巧 高畠, 和輝 岩崎, 元一 鈴木, 貴大 福島, 優 藤原, 幹生 佐々木, 雅英 田中, 宗 近年，イジングマシンを列生成法の一部に用いたハイブリッドアルゴリズムの研究がなされている．イジングマシンは組合せ最適化問題に対する高効率専用計算機であり，列生成法は制約条件の多い問題に対して有効とされる近似解法である．多数の制約条件がある問題においても，実質的に有効な制約条件の個数は限られてくる．そこで，列生成法では無駄な制約条件を省くために有効な制約条件を徐々に追加しながら問題を解く．このとき，有効な制約条件を見つける問題が子問題として定義される．先行研究におけるハイブリッドアルゴリズムでは，子問題をイジングマシンで解くことで効率的に有効な制約条件を見つけ，少ない制約条件の中で元の問題の解を探索する．このとき，複数の有効な制約条件を一度に追加する方法を複数列生成法と呼ぶ．複数列生成法に関する先行研究では，中性原子 QPU を用いて一度に複数個の解をサンプリングすることで複数列生成法を実現する方法が提案されており，この方法は制約条件を一度に一つずつ追加する場合と比べて全体の総計算時間が短縮されるという報告がされている．一方で，この方法では同じ子問題に対して複数回のサンプリングを行うという冗長な操作が必要となってしまう．本研究ではイジングマシンによる並列アニーリングを用いることで一回の子問題探索の中で複数の有効な制約条件を見つける方法を提案する．並列アニーリングとは，イジングマシン内部で利用可能なビット数以下で定義される問題に対して，イジングスピンを複製することで同時に複数の問題を解く手法である．この手法を応用し，本研究ではイジングマシンによる複数列生成法を構築した．ノードを共有しない K 本の最短経路探索問題に対して本提案手法を適用し，提案手法をナイーブにイジングマシンを用いた場合（ナイーブ手法）と比較した．その結果，ナイーブ手法に比べて提案手法の方が同程度の計算時間でより短い経路を探索することができた． technical report 情報処理学会 2024-03-21 application/pdf 研究報告量子ソフトウェア（QS） 31 2024-QS-11 1 11 2435-6492 AA12894105 https://ipsj.ixsq.nii.ac.jp/record/233705/files/IPSJ-QS24011031.pdf jpn