| Item type |
SIG Technical Reports(1) |
| 公開日 |
2023-03-06 |
| タイトル |
|
|
タイトル |
分割統治量子探索アルゴリズムを用いた組合せ最適化問題の実行可能解の解法 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
株式会社KDDI総合研究所／東京理科大学 |
| 著者所属 |
|
|
|
株式会社KDDI総合研究所 |
| 著者所属 |
|
|
|
東京理科大学 |
| 著者所属 |
|
|
|
芝浦工業大学 |
| 著者所属(英) |
|
|
|
en |
|
|
KDDI Research, Inc. / Tokyo University of Science |
| 著者所属(英) |
|
|
|
en |
|
|
KDDI Research, Inc. |
| 著者所属(英) |
|
|
|
en |
|
|
Tokyo University of Science |
| 著者所属(英) |
|
|
|
en |
|
|
Shibaura Institute of Technology |
| 著者名 |
佐藤, 嶺
齋藤, 和広
二国, 徹郎
渡部, 昌平
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Grover アルゴリズムをはじめとする量子探索アルゴリズムは，制約付き組合せ最適化問題を効率的に解くための有効な手段の一つである．量子探索アルゴリズムで制約付き組合せ最適化問題を解く場合，実行可能解の数に応じてオラクル演算子を量子回路上に埋め込む必要がある．しかし，この埋込に指数関数の計算量を要するため，量子探索アルゴリズムで大規模な制約付き組合せ最適化問題を高速に解くことは困難であった．そこで本研究では，分割統治法を従来の量子探索アルゴリズムに適用した，分割統治量子探索アルゴリズムを提案する．組合せ最適化問題の各制約項を小問題に分割し，小問題ごとに量子探索を行う量子回路を設計する．巡回セールスマン問題の実行可能解を求める問題を例として，提案手法と Grover アルゴリズム及び古典計算量と比較する．その結果，提案手法の分割統治量子探索アルゴリズムを使用することで，実行可能解の取得に必要な計算量を大幅に削減できることがわかった． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA12894105 |
| 書誌情報 |
研究報告量子ソフトウェア（QS）
巻 2023-QS-8,
号 35,
p. 1-9,
発行日 2023-03-06
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2435-6492 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-QS23008035.pdf (1.7 MB)
