WEKO3
アイテム
群非所属問題の証拠生成に対する検証プロトコル
https://ipsj.ixsq.nii.ac.jp/records/225060
https://ipsj.ixsq.nii.ac.jp/records/22506052c2bdac-3668-4fdf-9632-ce74d322cc48
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS23008024.pdf (759.5 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 | |||||||||
| 著者所属 | ||||||||||
| 名古屋大学大学院情報学研究科 | ||||||||||
| 著者所属 | ||||||||||
| 名古屋大学大学院情報学研究科 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Informatics, Nagoya University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Informatics, Nagoya University | ||||||||||
| 著者名 |
川合, 達也
× 川合, 達也
× 西村, 治道
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 従来の量子計算複雑性の研究分野では主に判定問題自体の複雑性が注目されてきた．一方で，近年では量子計算や量子通信の研究が進む中で状態の生成や量子操作の複雑性に関する研究が行われてきている．そこで本研究では問題に対して与えられた答えがYesであるという証拠（witness）について，witness の正しさの検証，および正しい witness を出力するタスクを考えたとき，問題が NP や QCMA に属す場合は自明にタスクが実行可能であるのに対して，QMA では非自明である点に注目した．そこでこのタスクについて，NP オラクルへのアクセスが可能な場合に対して実行可能であるかを調査した．その結果この場合において QMA の代表的な問題である群非所属問題について，与えられた witness が正しい状態の多項式個のコピーに近いならば，かつその時に限って高確率で受理して正しい witness に近い状態を出力するプロトコルを示せた． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA12894105 | |||||||||
| 書誌情報 |
研究報告量子ソフトウェア（QS） 巻 2023-QS-8, 号 24, p. 1-8, 発行日 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 | |||||||||
| 出版者 | 情報処理学会 | |||||||||
