WEKO3
アイテム
量子と古典のハイブリッドな計算機構に関するオラクルによる最適な計算量クラスの分離
https://ipsj.ixsq.nii.ac.jp/records/225057
https://ipsj.ixsq.nii.ac.jp/records/225057a6256526-34c6-4808-9d97-e7806db12c8f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS23008021.pdf (700.8 kB)
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-03-06 | |||||||||
| タイトル | ||||||||||
| タイトル | 量子と古典のハイブリッドな計算機構に関するオラクルによる最適な計算量クラスの分離 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 東京大学大学院情報理工学系研究科 | ||||||||||
| 著者所属 | ||||||||||
| 名古屋大学大学院多元数理科学研究科 | ||||||||||
| 著者名 |
長谷川, 敦哉
× 長谷川, 敦哉
× ルガル, フランソワ
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 最近 Chia，Chung & Lai (STOC 2020) と Coudron & Menda (STOC 2020) は BQP と BPPBQNC ∪ BQNCBPP を分離するようなオラクルがあることを示した．実は Chia らはもっと強いことを示している．それは任意の自然数のパラメーター d に対して多項式時間の古典計算を組み合わせることを許した時，深さ d と 2d + 1 の量子回路の計算量クラスを分離するようなオラクルが存在することを示した．これはオラクルの存在を仮定することで，量子回路の深さを二倍にすることで量子と古典のハイブリッドな計算機構の計算能力を真に向上させることを示している．この論文では同じ事を深さ d と d + 1 の量子回路に対して示した．これは量子と古典のハイブリッドな計算機構に関するオラクルによる最適な計算量クラスの分離となる．この結果を示すために我々は d-Bijective Shuffling Simon's Problem という Chia らの論文で考えられた d-Shuffling Simon's Problem という問題の亜種を考え，また “in-place” 置換オラクルに着想を得たオラクルも考えた． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA12894105 | |||||||||
| 書誌情報 |
研究報告量子ソフトウェア（QS） 巻 2023-QS-8, 号 21, p. 1-4, 発行日 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 | |||||||||
| 出版者 | 情報処理学会 | |||||||||
