制約付き組合せ最適化向けの実行可能テンソルネットワークの機械的構築

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-21
• タイトル: 制約付き組合せ最適化向けの実行可能テンソルネットワークの機械的構築
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: （株）リクルート／慶應義塾大学理工学部物理情報工学科
• 著者所属: （株）リクルート
• 著者所属: 慶應義塾大学理工学部物理情報工学科
• 著者所属(英): en
• 著者所属(英): Recruit Co., Ltd. / Department of Applied Physics and Physico-Informatics, Keio University
• 著者所属(英): en
• 著者所属(英): Recruit Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Department of Applied Physics and Physico-Informatics, Keio University
• 著者名: 中田, 百科; 棚橋, 耕太郎; 田中, 宗
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，テンソルネットワークを用いた制約付きの組合せ最適化の新手法を提案する．近年，QAOA などの量子ゲートを用いた組合せ最適化手法が盛んに研究されている．ただし現状の量子ゲートはビット数の制限やエラーの問題により大規模な組合せ最適化は難しいとされている．そこで，量子状態を近似的に扱うことができるテンソルネットワークを用いることで，より大きい規模の問題を解こうとする試みがある．特に最近では，実用化の観点から不可欠な，制約付きの組合せ最適化問題に特化した手法が提案されている．制約を満たす状態を表現する特殊なテンソルネットワークを用意することで，ペナルティ関数法なしに実行可能解のみを効率的に探索する手法である．ただし，従来手法では対応できる制約の種類が少ないという課題があった．そこで本研究では，与えられた制約条件に対して適切なテンソルネットワークを機械的に構築する手法を考案した．1 つは，粒子数を保存する従来のテンソルネットワーク構造を，線形不等式及び等式制約に拡張する手法である．また，粒子数保存の物理学スキームに頼ることなく，テンソルのパラメータを代数的に設計する手法も開発した．提案手法の原理検証のため，多数の制約条件を有する施設配置問題を題材としてテンソルネットワークを構築し，虚時間発展を用いて厳密解の探索を行った．探索中常に実行可能解が得られること，及び厳密解に到達することを確認した．この手法によりこれまで扱えなかった様々な種類の制約条件に対して，テンソルネットワークを用いた組合せ最適化が実行できるようになると期待される．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2024-QS-11, 号 27, p. 1-8, 発行日 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
• 出版者: 情報処理学会