1物理学科、ETH チューリッヒ、スイス
2Institute for Theoretical Studies, ETH Zürich, スイス
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
量子性の証明は、従来の検証者が信頼されていない証明者の $textit{量子優位性}$ を効率的に証明できる一種のチャレンジ/レスポンス プロトコルです。 つまり、量子証明者は検証者の課題に正しく答えて受け入れられますが、多項式時間の古典的な証明者は、もっともらしい計算上の仮定に基づいて高い確率で拒否されます。 検証者の課題に答えるために、量子性の既存の証明では通常、量子証明者が多項式サイズの量子回路と測定の組み合わせを実行する必要があります。
この論文では、証明者が対数深度の古典的な計算とともに $textit{constant-depth quantum circuit}$ (および測定) を実行するだけでよい、XNUMX つの量子性構造の証明を示します。 最初の構築は、既存のすべての量子性の証明を一定の量子深度バージョンに変換できる汎用コンパイラです。 XNUMX 番目の構築は $textit{learning with rounding}$ 問題に基づいており、一般的な構築よりも深さが短く、必要な量子ビットが少ない回路を生成します。 さらに、XNUMX 番目の構造は、ノイズに対してもある程度の堅牢性を備えています。
►BibTeXデータ
►参照
【1] スコット・アーロンソンとアレックス・アルヒポフ。 線形光学の計算の複雑さ。 コンピューティングの理論に関する第 333 回年次 ACM シンポジウムの議事録、342 ～ 2011 ページ、XNUMX 年。
https：/ / doi.org/ 10.1145 / 1993636.1993682
【2] Frank Arute、Kunal Arya、Ryan Babbush、Dave Bacon、Joseph C Bardin、Rami Barends、Rupak Biswas、Sergio Boixo、Fernando GSL Brandao、David A Buell、他プログラム可能な超伝導プロセッサを使用した量子超越性。 ネイチャー、574(7779):505–510、2019 年。
https://doi.org/10.1038/s41586-019-1666-5
【3] MD SAJID ANIS、Abby-Mitchell、Héctor Abraham、AduOffei 他Qiskit: 量子コンピューティング用のオープンソース フレームワーク、2021 年。
【4] サンジーブアローラとボアズバラク。 計算の複雑さ：最新のアプローチ。 ケンブリッジ大学出版局、2009年。
【5] スコット・アーロンソンとリジェ・チェン。 量子超越性実験の複雑性理論的基礎。 第 32 回計算複雑性会議議事録、CCC '17、1 ～ 67 ページ、Dagstuhl、DEU、2017 年。Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik。
https：/ / doi.org/ 10.48550 / arXiv.1612.05903
【6] スコット・アーロンソンとサム・ガン。 スプーフィング線形クロスエントロピー ベンチマークの古典的な難しさについて。 コンピューティングの理論、16(11):1–8、2020 年。
https：/ / doi.org/ 10.4086 / toc.2020.v016a011
【7] B. Applebaum、Y. Ishai、および E. Kushilevitz。 ${NC}^0$ の暗号化。 コンピューター サイエンスの基礎に関する第 45 回年次 IEEE シンポジウム、166 ～ 175 ページ、2004 年。
https：/ / doi.org/ 10.1109 / FOCS.2004.20
【8] Joël Alwen、Stephan Krenn、Krzysztof Pietrzak、Daniel Wichs。 丸めの学習、再訪。 Advances in Cryptology – CRYPTO 2013、57 ～ 74 ページ、ベルリン、ハイデルベルク、2013 年。Springer Berlin Heidelberg。
https://doi.org/10.1007/978-3-642-40041-4_4
【9] デビッド・A・バリントン。 制限幅の多項式サイズの分岐プログラムは、${NC}^1$ 内の言語を正確に認識します。 Journal of Computer and System Sciences、38(1):150–164、1989 年。
https://doi.org/10.1016/0022-0000(89)90037-8
【10] Zvika Brakerski、Paul Christiano、Urmila Mahadev、Umesh Vazirani、Thomas Vidick。 単一の量子デバイスからの量子性と証明可能なランダム性の暗号テスト。 2018年IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)、320～331ページ。 IEEE、2018年。
https：/ / doi.org/ 10.1145 / 3441309
【11] Colin D. Bruzewicz、John Chiaverini、Robert McConnell、Jeremy M. Sage。 トラップ イオン量子コンピューティング: 進歩と課題。 応用物理学のレビュー、2019 年。
https：/ / doi.org/ 10.1063 / 1.5088164
【12] アダム・ブーランド、ビル・フェファーマン、チンメイ・ニルケ、ウメッシュ・ヴァジラニ。 量子ランダム回路サンプリングの複雑さと検証について。 Nature Physics、15(2):159–163、2019 年 XNUMX 月。
https://doi.org/10.1038/s41567-018-0318-2
【13] Sergio Boixo、Sergei V Isakov、Vadim N Smelyanskiy、Ryan Babbush、Nan Ding、Zhang Jiang、Michael J Bremner、John M Martinis、および Hartmut Neven。 近い将来のデバイスにおける量子超越性の特徴付け。 自然物理学、14(6):595–600、2018 年。
https：/ / doi.org/ 10.1038 / s41567-018-0124-x
【14] Zvika Brakerski、Venkata Koppula、Umesh Vazirani、Thomas Vidick。 より単純な量子性の証明。 第 15 回量子計算、通信、および暗号化の理論に関する会議 (TQC 2020)、Leibniz International Proceedings in Informatics (LIPICs)、第 158 巻、8:1–8:14、ドイツ、ダグシュトゥール、2020 年。Schloss Dagstuhl–Leibniz- Zentrum für Informatik。
https：/ / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
【15] アビシェク・バナジー、クリス・ペイカート、アロン・ローゼン。 疑似乱数関数と格子。 Advances in Cryptology – EUROCRYPT 2012、719 ～ 737 ページ。 スプリンガー ベルリン ハイデルベルク、2012 年。
https://doi.org/10.1007/978-3-642-29011-4_42
【16] ジョン・F・クラウザー、マイケル・A・ホーン、アブナー・シモニー、リチャード・A・ホルト。 局所隠れ変数理論をテストするために提案された実験。 Physical Review Letters、23(15):880、1969年。
https：/ / doi.org/ 10.1103 / PhysRevLett.23.880
【17] マシュー・クードロン、ジャレックス・スターク、トーマス・ヴィディック。 場所と時間の交換: 低深度回路からの認証可能なランダム性。 数理物理学におけるコミュニケーション、382(1):49–86、2021。
https：/ / doi.org/ 10.1007 / s00220-021-03963-w
【18] リチャード・クリーヴとジョン・ワトラス。 量子フーリエ変換用の高速並列回路。 Proceedings 41st Annual Symposium on Foundations of Computer Science、526 ～ 536 ページ。 IEEE、2000。
https：/ / doi.org/ 10.1109 / SFCS.2000.892140
【19] ピエール・デュサール。 Autour de la fonction qui compte le nombre de nombres プレミア。 博士論文、リモージュ大学、1998 年。
https:/ / www.unilim.fr/ laco/ theses/ 1998/ T1998_01.pdf
【20] オースティン・G・ファウラー、マッテオ・マリアントーニ、ジョン・M・マルティニス、アンドリュー・N・クレランド。 表面コード: 実用的な大規模量子計算に向けて. フィジカル レビュー A、86(3):032324、2012 年。
https：/ / doi.org/ 10.1103 / PhysRevA.86.032324
【21] フランソワ・ル・ガル。 私信、2022年。
【22] クレイグ・ギドニーとマーティン・エケロー。 2048 ビットの RSA 整数を 8 時間で 20 万のノイズの多い量子ビットを使用して因数分解する方法。 量子、5:433、2021 年。
https://doi.org/10.22331/q-2021-04-15-433
【23] アレクサンドル・ゲオルギウとマティ・J・ホーバン。 浅い回路出力のエントロピーを推定するのは困難です。 arXiv プレプリント arXiv:2002.12814, 2020.
https：/ / doi.org/ 10.48550 / arXiv.2002.12814
arXiv：2002.12814
【24] 平原修一とフランソワ・ル・ガル。 小深度量子回路による量子性のテスト。 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPICs), pages 59:1–59:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https：/ / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
【25] アラム・W・ハローとアシュリー・モンタナロ。 量子計算の覇権。 ネイチャー、549(7671):203–209、2017。
https：/ / doi.org/ 10.1038 / nature23458
【26] ピーター・ホイヤーとロバート・シュパレク。 量子ファンアウトは強力です。 コンピューティングの理論、1(5):81–103、2005。
https：/ / doi.org/ 10.4086 / toc.2005.v001a005
【27] Cupjin Huang、Fang Zhang、Michael Newman、Junjie Cai、Xun Gao、Zhengxiong Tian、Junyin Wu、Haihong Xu、Huanjun Yu、Bo Yuan、Mario Szegedy、Yaoyun Shi、Jianxin Chen。 量子超越回路の古典的シミュレーション。 arXiv プレプリント arXiv:2005.06787, 2020.
https：/ / doi.org/ 10.48550 / arXiv.2005.06787
arXiv：2005.06787
【28] グレゴリー・D・カハナモク＝マイヤー。 量子データの偽造: IQP ベースの量子テストを古典的に打ち負かします。 arXiv プレプリント arXiv:1912.05547, 2019.
https：/ / doi.org/ 10.48550 / arXiv.1912.05547
arXiv：1912.05547
【29] Gregory D. Kahanamoku-Meyer、Soonwon Choi、Umesh V. Vazirani、および Norman Y. Yao。 計算ベル テストからの古典的に検証可能な量子優位性。 自然物理学、18(8):918–924、2022 年。
https://doi.org/10.1038/s41567-022-01643-7
【30] Vadim Lyubashevsky、Chris Peikert、および Oded Regev。 理想的な格子と環上の誤差を伴う学習について。 暗号技術の理論と応用に関する年次国際会議、1 ～ 23 ページ。 スプリンガー、2010年。
https：/ / doi.org/ 10.1145 / 2535925
【31] ウルミラ・マハデフ。 量子計算の古典的検証。 2018 年 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)、259 ～ 267 ページ。 IEEE、2018年。
https：/ / doi.org/ 10.1109 / FOCS.2018.00033
【32] マイケル・A・ニールセンとアイザック・チュアン。 量子計算と量子情報、2002年。
【33] AS ポポワと AN ルブツォフ。 ガウス ボソン サンプリングの量子アドバンテージしきい値のクラック。 Quantum 2.0 Conference and Exhibition の QW2A.15 ページ。 Optica パブリッシング グループ、2022 年。
https:/ / doi.org/ 10.1364/ QUANTUM.2022.QW2A.15
【34] ジョン・プレスキル。 NISQ 時代以降の量子コンピューティング。 量子、2:79、2018 年。
https://doi.org/10.22331/q-2018-08-06-79
【35] マイケル・オー・ラビン。 素数性をテストするための確率的アルゴリズム。 Journal of Number Theory、12(1):128–138、1980 年。
https://doi.org/10.1016/0022-314X(80)90084-0
【36] オデッド・レジェフ。 ラティス、エラーによる学習、ランダムな線形コード、および暗号化。 ACM ジャーナル (JACM)、56(6):1–40、2009 年。
https：/ / doi.org/ 10.1145 / 1568318.1568324
【37] ダン・シェパードとマイケル・J・ブレムナー。 時間的に非構造化された量子計算。 王立協会の議事録 A: 数学、物理学および工学科学、465(2105):1413–1439、2009。
https：/ / doi.org/ 10.1098 / rspa.2008.0443
【38] ピーター・W・ショー。 量子計算のアルゴリズム: 離散対数と因数分解。 Proceedings 35th Annual Symposium on Foundations of Computer Science、124 ～ 134 ページ。 IEEE、1994 年。
https：/ / doi.org/ 10.1109 / SFCS.1994.365700
【39] Yulin Wu、Wan-Su Bao、Sirui Cao、Fusheng Chen、Ming-Cheng Chen、Xiawei Chen、Tung-Hsun Chung、Hui Deng、Yajie Du、Daojin Fan、Ming Gong、Cheng Guo、Chu Guo、Shaojun Guo、Lianchen Han 、 リンイン・ホン、ヘリャン・ファン、ヨンヘン・フオ、リピン・リー、ナ・リー、シャオウェイ・リー、ユアン・リー、フーティアン・リャン、チュン・リン、ジン・リン、ハオラン・チェン、ダン・チャオ、ハオ・ロン、ホン・スー、リフア・サン、 Liangyuan Wang、Shiyu Wang、Dachao Wu、Yu Xu、Kai Yan、Weifeng Yang、Yang Yang、Yangsen Ye、Jianghan Yin、Chong Ying、Jiale Yu、Chen Zha、Cha Zhang、Haibin Zhang、Kaili Zhang、Yiming Zhang、Han Zhao 、Youwei Zhao、Liang Zhou、Qingling Zhu、Chao-Yang Lu、Cheng-Zhi Peng、Xiaobo Zhu、およびJian-Wei Pan。 超伝導量子プロセッサを使用した強力な量子計算の利点。 物理。 Rev. Lett., 127:180501, 2021.
https：/ / doi.org/ 10.1103 / PhysRevLett.127.180501
【40] K Wright、KM Beck、Sea Debnath、JM Amini、Y Nam、N Grzesiak、JS Chen、NC Pisenti、M Chmielewski、C Collins 他11 キュービット量子コンピューターのベンチマーク。 ネイチャー コミュニケーション、10(1):1–6、2019 年。
https://doi.org/10.1038/s41467-019-13534-2
【41] G・ウェンディン。 超伝導回路による量子情報処理：レビュー。 物理学の進歩に関するレポート、80(10):106001、2017 年。
https://doi.org/10.1088/1361-6633/aa7e1a
【42] アダム・ベネ・ワッツ、ロビン・コタリ、ルーク・シェーファー、アビシェイ・タル。 浅い量子回路と無制限のファンインの浅い古典的回路との間の指数関数的分離。 コンピューティング理論に関する第 51 回 ACM SIGACT シンポジウムの議事録、515 ～ 526 ページ、2019 年。
https：/ / doi.org/ 10.1145 / 3313276.3316404
【43] アンドリュー・チーチー・ヤオ。 シークレットを生成して交換する方法。 第 27 回コンピュータ サイエンスの基礎に関する年次シンポジウム (sfcs 1986)、162 ～ 167 ページ。 IEEE、1986年。
https：/ / doi.org/ 10.1109 / SFCS.1986.25
【44] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang 、 呉大超、呉玉林、余徐、甲斐燕、楊維峰、楊陽、楊森葉、江漢陰、崇英、嘉楽宇、陳趙、車張、海浜張、張凱里、張逸明、趙漢、有威Zhao、Liang Zhou、Chao-Yang Lu、Cheng-Zhi Peng、Xiaobo Zhu、および Jian-Wei Pan。 60 キュービット 24 サイクルのランダム回路サンプリングによる量子計算の利点。 科学速報、67(3):240–245、2022 年。
https：/ / doi.org/ 10.1016 / j.scib.2021.10.017
【45] Daiwei Zhu、Gregory D. Kahanamoku-Meyer、Laura Lewis、Crystal Noel、Or Katz、Bahaa Harraz、Qingfeng Wang、Andrew Risinger、Lei Feng、Debopriyo Biswas、Laird Egan、Alexandru Gheorghiu、Yunseong Nam、Thomas Vidick、Umesh Vazirani、Norman Y. Yao、Marko Cetina、Christopher Monroe。 古典的に検証可能な量子アドバンテージのためのインタラクティブなプロトコル。 arXiv プレプリント arXiv:2112.05156, 2021.
https：/ / doi.org/ 10.48550 / arXiv.2112.05156
arXiv：2112.05156
【46] ハン・セン・ジョン、ホイ・ワン、ユ・ハオ・デン、ミン・チェン・チェン、リー・チャオ・ペン、イー・ハン・ルオ、ジャン・チン、ディアン・ウー、シン・ディン、イー・フー、ポン・フー、シャオ・ヤン・ヤン、ウェイ・Jun Zhang、Hao Li、Yuxuan Li、Xiao Jiang、Lin Gan、Guangwen Yang、Lixing You、Zhen Wang、Li Li、Nai-Le Liu、Chao-Yang Lu、および Jian-Wei Pan。 光子を使用した量子計算の利点。 科学、370(6523):1460–1463、2020 年。
https：/ / doi.org/ 10.1126 / science.abe8770
によって引用
[1] Nathanan Tantivasadakarn、Ashvin Vishwanath、および Ruben Verresen、「有限深度ユニタリー、測定およびフィードフォワードからのトポロジー秩序の階層」、 arXiv：2209.06202.
[2] Sergey Bravyi、Isaac Kim、Alexander Kliesch、Robert Koenig、「非アーベル エニオンを操作するための適応定深度回路」、 arXiv：2205.01933.
[3] Daiwei Zhu、Gregory D. Kahanamoku-Meyer、Laura Lewis、Crystal Noel、Or Katz、Bahaa Harraz、Qingfeng Wang、Andrew Risinger、Lei Feng、Debopriyo Biswas、Laird Egan、Alexandru Gheorghiu、Yunseong Nam、Thomas Vidick、Umesh Vazirani、Norman Y. Yao、Marko Cetina、Christopher Monroe、「古典的に検証可能な量子アドバンテージのためのインタラクティブなプロトコル」、 arXiv：2112.05156.
[4] Vipin Singh Sehrawat、Foo Yee Yeo、および Dmitriy Vassilyev、「線形回帰および極値集合論からのスター固有のキー準同型 PRF」、 arXiv：2205.00861.
[5] Gregory D. Kahanamoku-Meyer、Soonwon Choi、Umesh V. Vazirani、および Norman Y. Yao、「計算ベル テストからの古典的に検証可能な量子優位性」、 ネイチャーフィジクス18、8（918）.
[6] Roozbeh Bassirian、Adam Bouland、Bill Fefferman、Sam Gunn、および Avishay Tal、「量子アドバンテージ実験からの認定ランダム性について」、 arXiv：2111.14846.
[7] Nai-Hui Chia および Shih-Han Hung、「量子深度の古典的検証」、 arXiv：2205.04656.
[8] 水谷明宏、竹内由紀、広正亮、相川祐介、谷誠一郎、「絡み合った魔法状態の計算自己検査」、 フィジカルレビューA106 1、L010601（2022）.
[9] Yihui Quek、Mark M. Wilde、および Eneet Kaur、「一定の量子深度での多変量トレース推定」、 arXiv：2206.15405.
上記の引用は SAO / NASA ADS （最後に正常に更新された2022-09-21 12:16:02）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
On Crossrefの被引用サービス 作品の引用に関するデータは見つかりませんでした（最後の試行2022-09-21 12:16:00）。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
