0-1整数計画問題に対する量子緩和を用いた分枝限定法フレームワーク

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-21
• タイトル: 0-1整数計画問題に対する量子緩和を用いた分枝限定法フレームワーク
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 株式会社Jij
• 著者所属: 株式会社Jij
• 著者所属: 株式会社Jij
• 著者所属: 株式会社Jij
• 著者名: 松山, 洋道; 黄, 威豪; 西村, 光嗣; 山城, 悠
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 0-1 整数計画問題は, 制約条件を満たし，目的関数を最小化するバイナリ列を求める問題である．この問題を解くために，誤り耐性を持たない量子デバイス上でも適用可能な Quantum Approximate Optimization Algorithm などの手法が盛んに研究されている．これらの手法では，0-1 整数計画問題の制約条件を Penalty 法を用いて Quadratic Unconstrained Binary Optimization の形へと緩和し，対応するハミルトニアンの基底状態をヒューリスティックに探索する．しかし，特に制約の多い問題では制約を満たした解を得ることが困難であり，最適解の保証も提供されない．そこで，本研究では近年提案された，量子緩和と呼ばれる手法に着目した．量子緩和は，最適化問題の中の複数の古典ビットを一つの量子ビットに埋め込むことで量子ハミルトニアンを構成する手法であり，その基底エネルギーは緩和前の問題の目的関数値の下界を与える．緩和問題を解くことは古典的な厳密解法である分枝限定法においては主要な役割を果たす．そこで，我々は，分枝限定法と量子緩和を組み合わせた Quantum Relaxation based Branch-and-Bound を提案する．この手法は，制約付き 2 次 0-1 整数最適化問題に対する厳密解法である量子古典ハイブリッドアルゴリズムである．このアルゴリズムは，量子緩和の基底エネルギーが厳密に求まる限り，厳密解を与える．さらに，古典的な分枝操作を通して，制約条件を適切に扱うことが可能になる．本研究では，制約なしと制約付き最適化問題の例として最大カット問題と巡回セールスマン問題に対して実験を行ない，量子緩和の最適値を用いた場合には，実験を行なった全てのインスタンスで厳密解を与えることを示した．また，制約条件を有効に使うことで，分枝限定法の収束を速めることができることを示した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2024-QS-11, 号 23, p. 1-7, 発行日 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
• 出版者: 情報処理学会