テキサス大学オースティン校コンピュータサイエンス学部、オースティン、テキサス州78712、米国
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
ノイズの多いランダム量子回路での短期的な量子超越性実験を検証するための主要な提案は、線形クロスエントロピーベンチマークです。 $ n $キュービットの量子回路$ C $と{0,1} ^ n $のサンプル$ zの場合、ベンチマークには$ | langle z | C | 0 ^ n rangle | ^ 2 $、つまり確率の計算が含まれます。すべてゼロの入力での$ C $の出力分布から$ z $を測定します。 量子回路の出力確率を推定する古典的な硬さについての強い推測の下では、$ C $が与えられた多項式時間の古典的なアルゴリズムは、$ | langle z | C | 0 ^ nrangle | ^ 2 $が次のような文字列$ z $を出力できません。 $ frac {1} {2 ^ n} $よりも大幅に大きい（Aaronson and Gunn、2019）。 一方、ランダム量子回路$ C $の場合、$ C $の出力分布から$ z $をサンプリングすると、$ | langle z | C | 0 ^ nrangle | ^ 2約frac {2} {2 ^ n}が得られます。平均$（Arute et al。、2019）。
量子非局所相関からのTsirelson不等式と同様に、次のように質問します。多項式時間量子アルゴリズムは$ frac {2} {2 ^ n} $よりも大幅に優れているでしょうか？ この質問は、量子アルゴリズムに$ C $へのオラクルアクセスが与えられるクエリ（またはブラックボックス）モデルで研究します。 $ varepsilon ge frac {1} {mathrm {poly}（n）} $について、$ | langle z | C | 0 ^ nrangle | ^ 2 ge frac {2+となるようなサンプル$ z $を出力することを示します。 varepsilon} {2 ^ n} $は、平均して$ C $に対して少なくとも$ Omegaleft（frac {2 ^ {n / 4}} {mathrm {poly}（n）} right）$クエリを必要としますが、$ Oleft以下である必要があります。 （2 ^ {n / 3} right）$は、$ C $がHaar-random $ n $ -qubitユニタリであるか、Haar-random $ n $ -qubitの正規状態準備オラクルである場合、$ C $にクエリを実行します。州。 また、$ C $がランダムブール関数のフーリエ分布からサンプリングする場合、$ C $からサンプリングする単純なアルゴリズムが、$ | langle z | C | 1 ^ nrangle | ^ 0を最大化するための最適な2クエリアルゴリズムであることも示します。平均して$。
人気の要約
線形XEBの古典的アルゴリズムの能力のこの上限は、非局所相関におけるベルの不等式に類似していると主張します。どちらも、量子設定で違反する可能性のある古典的情報と計算の能力に関する固有の制限をキャプチャします。 この関係に動機付けられて、私たちは尋ねます：Tsirelson不平等の量子超越性類似物は何ですか？ つまり、効率的な量子アルゴリズムによって達成可能な最高の線形XEBスコアは何ですか？ ベンチマークに合格するための素朴な量子アルゴリズムがこの点で本質的に最適であるという証拠を示します。
►BibTeXデータ
►参照
【1] スコットアーロンソン。 ランダム回路サンプリング：考えと未解決の問題。 コンピューティングにおける量子波、2020年。URLhttps：/ / simons.berkeley.edu/ talks / tbd-124。
https：/ / simons.berkeley.edu/ talks / tbd-124
【2] スコットアーロンソンとリジーチェン。 量子超越性実験の複雑性理論的基礎。 Ryan O'Donnell、編集者、第32回計算複雑性会議（CCC 2017）、Leibniz International Proceedings in Informatics（LIPIcs）の79巻、22：1–22：67ページ、ドイツ、ダグストゥール、2017年。SchlossDagstuhl–Leibniz-Zentrum fuerInformatik。 ISBN978-3-95977-040-8。 10.4230 /LIPIcs.CCC.2017.22。 URL http：/ / drops.dagstuhl.de/ opus / volltexte / 2017/7527。
https：/ / doi.org/ 10.4230 / LIPIcs.CCC.2017.22
http：/ / drops.dagstuhl.de/ opus / volltexte / 2017/7527
【3] スコットアーロンソンとサムガン。 スプーフィング線形クロスエントロピーベンチマークの古典的な硬さについて。 計算理論、16（11）：1–8、2020。10.4086 /toc.2020.v016a011。 URL http：/ / www.theoryofcomputing.org/ articles / v016a011。
https：/ / doi.org/ 10.4086 / toc.2020.v016a011
http：/ / www.theoryofcomputing.org/ articles / v016a011
【4] スコットアーロンソン、ロビンコタリ、ウィリアムクレッチマー、ジャスティンターラー。 ローラン多項式による近似カウントのための量子下限。 Shubhangi Saraf、編集者、第35回計算複雑性会議（CCC 2020）、Leibniz International Proceedings in Informatics（LIPIcs）の169巻、7：1–7：47ページ、ドイツ、ダグストゥール、2020年。SchlossDagstuhl–Leibniz-ZentrumfürInformatik 。 ISBN978-3-95977-156-6。 10.4230 /LIPIcs.CCC.2020.7。 URL https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/12559。
https：/ / doi.org/ 10.4230 / LIPIcs.CCC.2020.7
https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/12559
【5] ドリット・アハラノフ、アレクセイ・キタエフ、ノアム・ニサン。 混合状態の量子回路。 コンピューティング理論に関する第98回ACMシンポジウムの議事録、STOC '20、30〜1998ページ、ニューヨーク、ニューヨーク、米国、0897919629年。AssociationforComputingMachinery。 ISBN10.1145。276698.276708/ 10.1145。 URL https：/ / doi.org/ 276698.276708 /XNUMX。
https：/ / doi.org/ 10.1145 / 276698.276708
【6] アンドリス・アンバイニス。 クエリの複雑さによる量子アルゴリズムの理解。 2018 International Congress of Mathematicians、volume 3、pages 3249–3270、2018の議事録。10.1142/ 9789813272880_0181。
https：/ / doi.org/ 10.1142 / 9789813272880_0181
【7] アンドリス・アンバイニス、ロイック・マグニン、マーティン・ロッテラー、ジェレミー・ローランド。 量子状態生成のための対称性支援の敵。 計算の複雑さに関する2011年IEEE第26回年次会議の議事録、CCC '11、167〜177ページ、米国、2011年。IEEEComputerSociety。 ISBN9780769544113。10.1109/ CCC.2011.24。 URL https：/ / doi.org/ 10.1109 /CCC.2011.24。
https：/ / doi.org/ 10.1109 / CCC.2011.24
【8] アンドリス・アンバイニス、アンシス・ロスマニス、ドミニク・ウンルー。 古典的な証明システムに対する量子攻撃：量子巻き戻しの硬さ。 2014 IEEE 55th Annual Symposium on Foundations of Computer Science、FOCS '14、page 474–483、USA、2014の議事録。IEEEComputerSociety。 ISBN9781479965175。10.1109/ FOCS.2014.57。 URL https：/ / doi.org/ 10.1109 /FOCS.2014.57。
https：/ / doi.org/ 10.1109 / FOCS.2014.57
【9] Srinivasan Arunachalam、Aleksandrs Belovs、Andrew M. Childs、Robin Kothari、Ansis Rosmanis、およびRonald deWolf。 量子クーポンコレクター。 スティーブン・T・フラミア、編集者、第15回量子計算、通信、暗号化の理論に関する会議（TQC 2020）、ライプニッツ国際情報学会議（LIPIcs）の第158巻、10：1〜10：17ページ、ドイツ、ダグストゥール、 2020. Schloss Dagstuhl–Leibniz-ZentrumfürInformatik。 ISBN978-3-95977-146-7。 10.4230 /LIPIcs.TQC.2020.10。 URL https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/12069。
https：/ / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/12069
【10] Frank Arute、Kunal Arya、Ryan Babbush、他。 プログラム可能な超伝導プロセッサを使用した量子超越性。 Nature、574（7779）：505–510、2019。10.1038 / s41586-019-1666-5。 URL https：/ / doi.org/ 10.1038 / s41586-019-1666-5。
https://doi.org/10.1038/s41586-019-1666-5
【11] ロバート・ビールス、ハリー・バーマン、リチャード・クリーブ、ミシェル・モスカ、ロナルド・デ・ウルフ。 多項式による量子の下限。 J. ACM、48（4）：778–797、2001年0004月。ISSN5411-10.1145。 502090.502097 /10.1145。 URL https：/ / doi.org/ 502090.502097 /XNUMX。
https：/ / doi.org/ 10.1145 / 502090.502097
【12] ジョン・ベル。 アインシュタイン-ポドルスキー-ローゼンのパラドックスについて。 Physics、1：195–200、1964年10.1103月。1.195/ PhysicsPhysiqueFizika.10.1103。 URL https：/ / link.aps.org/ doi / 1.195 /PhysicsPhysiqueFizika.XNUMX。
https：/ / doi.org/ 10.1103 / PhysicsPhysiqueFizika.1.195
【13] アレクサンダースベロフス。 量子敵のバリエーション、2015年。
arXiv：1504.06943
【14] AleksandrsBelovsとAnsisRosmanis。 量子状態による近似カウントの厳密な量子下限、2020年。
arXiv：2002.06879
【15] フェルナンドGSLブランダン、アラムW.ハロー、ミハウホロデッキ。 局所ランダム量子回路は近似多項式設計です。 Communications in Mathematical Physics、346（2）：397–434、2016。10.1007 / s00220-016-2706-8。 URL https：/ / doi.org/ 10.1007 / s00220-016-2706-8。
https://doi.org/10.1007/s00220-016-2706-8
【16] ジル・ブラッサール、ピーター・ホイヤー、アラン・タップ。 ハッシュおよびクローフリー関数の量子暗号解読。 SIGACT News、28（2）：14–19、1997年0163月。ISSN5700-10.1145。 261342.261346 /10.1145。 URL https：/ / doi.org/ 261342.261346 /XNUMX。
https：/ / doi.org/ 10.1145 / 261342.261346
【17] ジル・ブラッサール、ピーター・ホイヤー、ミシェル・モスカ、アラン・タップ。 量子振幅の増幅と推定。 量子計算と量子情報、現代数学の第305巻、53〜74ページ。 American Mathematical Society、2002年。ISBN9780821821404。10.1090/ conm / 305。
https：/ / doi.org/ 10.1090 / conm / 305
【18] マーク・バンとジャスティン・ターラー。 近似度とマルコフ-ベルンシュタイン不等式の二重下限。 Inf。 Comput。、243（C）：2–25、2015年0890月。ISSN5401-10.1016。 2014.12.003 /j.ic.10.1016。 URL https：/ / doi.org/ 2014.12.003 /j.ic.XNUMX。
https：/ / doi.org/ 10.1016 / j.ic.2014.12.003
【19] ボリス・チレルソン（チレルソン）。 ベルの不等式の量子一般化。 Letters in Mathematical Physics、4（2）：93–100、1980。10.1007 / BF00417500。 URL https：/ / doi.org/ 10.1007 / BF00417500。
https：/ / doi.org/ 10.1007 / BF00417500
【20] ジョン・F・クラウザー、マイケル・A・ホーン、アブナー・シモニー、リチャード・A・ホルト。 局所的な隠れた変数理論をテストするために提案された実験。 物理学Rev. Lett。、23：880–884、1969年10.1103月。23.880/ PhysRevLett.10.1103。 URL https：/ / link.aps.org/ doi / 23.880 /PhysRevLett.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevLett.23.880
【21] リチャード・クリーブ、ピーター・ホイヤー、ベンジャミン・トナー、ジョン・ワトラス。 非ローカル戦略の結果と限界。 計算の複雑さに関する第19回IEEE年次会議の議事録、CCC '04、236〜249ページ、米国、2004年。IEEEComputerSociety。 ISBN0769521207。10.1109/ CCC.2004.1313847。
https：/ / doi.org/ 10.1109 / CCC.2004.1313847
【22] アラム・ハーローとサイード・メラバン。 最近傍ゲートと長距離ゲートを使用した短いランダム量子回路による近似ユニタリーt設計、2018年。
arXiv：1809.06957
【23] ノーマンL.ジョンソンとサミュエルコッツ。 壺モデルとその応用：現代の離散確率論へのアプローチ。 Wiley、1977年。ISBN9780471446309。
【24] シェルビー・キンメル、セドリック・イェン・ユー・リン、グアン・ハオ・ロウ、マリス・オゾルズ、セオドア・J・ヨーダー。 最適なサンプルの複雑さを備えたハミルトニアンシミュレーション。 npj Quantum Information、3（1）：13、2017。10.1038 / s41534-017-0013-7。 URL https：/ / doi.org/ 10.1038 / s41534-017-0013-7。
https://doi.org/10.1038/s41534-017-0013-7
【25] ウィリアム・クレッチマー。 量子超越性Tsirelsonの不平等。 James R. Lee、編集者、理論計算機科学会議の第12回イノベーション（ITCS 2021）、Leibniz International Proceedings in Informatics（LIPIcs）の第185巻、13：1–13：13ページ、ドイツ、ダグストゥール、2021年。SchlossDagstuhl– Leibniz-ZentrumfürInformatik。 ISBN978-3-95977-177-1。 10.4230 /LIPIcs.ITCS.2021.13。 URL https：/ / drops.dagstuhl.de/ opus / volltexte / 2021/13552。
https：/ / doi.org/ 10.4230 / LIPIcs.ITCS.2021.13
https：/ / drops.dagstuhl.de/ opus / volltexte / 2021/13552
【26] Troy Lee、Rajat Mittal、Ben W. Reichardt、RobertŠpalek、MarioSzegedy。 状態変換の量子クエリの複雑さ。 コンピュータサイエンスの基礎に関する2011年IEEE第52回年次シンポジウムの議事録、FOCS '11、344〜353ページ、米国、2011年。IEEEComputerSociety。 ISBN9780769545714。10.1109/ FOCS.2011.75。 URL https：/ / doi.org/ 10.1109 /FOCS.2011.75。
https：/ / doi.org/ 10.1109 / FOCS.2011.75
【27] ネイサンリンジーとアンシスロスマニス。 非コヒーレントインデックス消去のためのタイトな下限。 Thomas Vidick、編集者、理論計算機科学会議の第11回イノベーション（ITCS 2020）、Leibniz International Proceedings in Informatics（LIPIcs）の第151巻、59：1–59：37ページ、ドイツ、ダグストゥール、2020年。SchlossDagstuhl–Leibniz- Zentrum fuerInformatik。 ISBN978-3-95977-134-4。 10.4230 /LIPIcs.ITCS.2020.59。 URL https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/11744。
https：/ / doi.org/ 10.4230 / LIPIcs.ITCS.2020.59
https：/ / drops.dagstuhl.de/ opus / volltexte / 2020/11744
【28] フレデリック・マグニエス、アシュウィン・ナヤック、ジェレミー・ローランド、ミクロス・サンサ。 量子ウォークを介して検索します。 コンピューティング理論に関する第07回ACMシンポジウムの議事録、STOC '575、584〜2007ページ、ニューヨーク、ニューヨーク、米国、9781595936318年。AssociationforComputingMachinery。 ISBN10.1145。1250790.1250874/ 10.1145。 URL https：/ / doi.org/ 1250790.1250874 /XNUMX。
https：/ / doi.org/ 10.1145 / 1250790.1250874
【29] ライアンオドネル。 ブール関数の分析。 ケンブリッジ大学出版局、米国、2014年。ISBN1107038324。10.1017/ CBO9781139814782。
https：/ / doi.org/ 10.1017 / CBO9781139814782
【30] マーティン・ラーブとアンゲリカ・スティーガー。 「ボールをビンに入れる」–シンプルで厳密な分析。 コンピュータサイエンスにおけるランダム化と近似技術に関する第98回国際ワークショップの議事録、ランダム'159、170〜1998ページ、ベルリン、ハイデルベルク、354065142年。Springer-Verlag。 ISBN10.1007X。 3 / 540-49543-6-13_XNUMX。
https://doi.org/10.1007/3-540-49543-6_13
【31] ベン・W・ライカート。 量子クエリアルゴリズムの反射。 離散アルゴリズムに関する第11回ACM-SIAMシンポジウムの議事録、SODA '560、569〜2011ページ、米国、10.1137年。SocietyforIndustrial and AppliedMathematics。 1.9781611973082.44 /XNUMX。
https：/ / doi.org/ 10.1137 / 1.9781611973082.44
【32] レーニ・アルフレニー。 順序統計量の理論について。 Acta Mathematica Academiae Scientiarum Hungarica、4（3）：191–231、1953。10.1007 / BF02127580。 URL https：/ / doi.org/ 10.1007 / BF02127580。
https：/ / doi.org/ 10.1007 / BF02127580
によって引用
[1]DanielStilckFrançaとRaulGarcia-Patron、「量子超越性のゲーム：検証とシミュレーションのリンク」、 arXiv：2011.12173.
[2] Nicholas LaRacuente、「複雑だが簡単に指定できる状態からの量子オラクル分離」、 arXiv：2104.07247.
[3] Scott Aaronson、「量子クエリの複雑さに関連する未解決の問題」、 arXiv：2109.06917.
上記の引用は SAO / NASA ADS （最後に正常に更新された2021-10-07 11:15:15）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
取得できませんでした クロスリファレンス被引用データ 最終試行2021-10-07 11:15:13：10.22331 / q-2021-10-07-560の被引用データをCrossrefから取得できませんでした。 DOIが最近登録された場合、これは正常です。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
PlatoAi。 Web3の再考。 増幅されたデータインテリジェンス。
アクセスするには、ここをクリックしてください。
