和风网标志

量子霸权 Tsirelson 不等式

日期:

威廉·克雷奇默

德克萨斯大学奥斯汀分校计算机科学系,奥斯汀,德克萨斯州 78712,美国

觉得本文有趣或想讨论? 在SciRate上发表评论或发表评论.

抽象

在嘈杂的随机量子电路上验证近期量子霸权实验的一个主要建议是线性交叉熵基准测试。 对于 $n$ 量子比特上的量子电路 $C$ 和 {0,1}^n$ 中的样本 $z,基准涉及计算 $|langle z|C|0^n rangle|^2$,即概率从全零输入上 $C$ 的输出分布测量 $z$。 在关于估计量子电路输出概率的经典难度的强烈猜想下,给定 $C$ 的多项式时间经典算法都不能输出字符串 $z$ 使得 $|langle z|C|0^nrangle|^2$ 是远大于 $frac{1}{2^n}$(Aaronson 和 Gunn,2019 年)。 另一方面,对于随机量子电路 $C$,从 $C$ 的输出分布中采样 $z$ 实现 $|langle z|C|0^nrangle|^2 近似 frac{2}{2^n} $ 平均(Arute 等人,2019 年)。
与量子非局域相关性中的 Tsirelson 不等式类似,我们问:多项式时间量子算法能否比 $frac{2}{2^n}$ 做得更好? 我们在查询(或黑盒)模型中研究这个问题,其中量子算法被授予 oracle 访问 $C$ 的权限。 我们证明,对于任何 $varepsilon ge frac{1}{mathrm{poly}(n)}$,输出一个样本 $z$ 使得 $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ 平均需要至少 $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$ 查询到 $C$,但不超过 $Oleft (2^{n/3}right)$ 查询 $C$,如果 $C$ 是 Haar-random $n$-qubit 幺元,或者 Haar-random $n$-qubit 的规范状态准备预言机状态。 我们还表明,当 $C$ 从随机布尔函数的傅立叶分布中采样时,从 $C$ 中采样的朴素算法是最大化 $|langle z|C|1^nrangle|^0 的最佳 2-query 算法美元平均。

最近的量子霸权实验使用称为“线性交叉熵基准”(或线性 XEB)的统计测试进行了验证。 之所以选择这个基准,是因为复杂性理论证据表明,与任何可能的高效经典算法相比,高效的量子算法可以获得更高的线性 XEB 分数。

我们认为,线性 XEB 经典算法的功率上限类似于非局部相关中的贝尔不等式:两者都捕获了经典信息和计算能力的内在限制,这在量子设置中可能会被违反。 受这种联系的启发,我们问:Tsirelson 不等式的量子霸权模拟是什么? 也就是说,有效的量子算法可达到的最高线性 XEB 分数是多少? 我们提供证据表明,通过基准的朴素量子算法在这方面本质上是最优的。

►BibTeX数据

►参考

[1] 斯科特·阿伦森。 随机电路采样:思想和开放问题。 计算领域的量子波,2020 年。URL https:// / simons.berkeley.edu/ talks/ tbd-124。
https:/ / simons.berkeley.edu/ talks/ tbd-124

[2] Scott Aaronson 和 Lijie Chen。 量子霸权实验的复杂性理论基础。 在 Ryan O'Donnell,编辑,第 32 届计算复杂性会议 (CCC 2017),Leibniz International Proceedings in Informatics (LIPIcs) 第 79 卷,第 22:1–22:67 页,德国达格斯图尔,2017 年。 Schloss Dagstuhl–Leibniz-Zent更信息化。 ISBN 978-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] Scott Aaronson、Robin Kothari、William Kretschmer 和 Justin Thaler。 通过洛朗多项式近似计数的量子下界。 在 Shubhangi Saraf,编辑,第 35 届计算复杂性会议 (CCC 2020),Leibniz International Proceedings in Informatics (LIPIcs) 第 169 卷,第 7:1–7:47 页,Dagstuhl,德国,2020 年。Schloss Dagstuhl–Leibniz-Zentikrum . ISBN 978-3-95977-156-6。 10.4230/ LIPics.CCC.2020.7。 网址 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 年。计算机协会。 ISBN 10.1145。276698.276708/ 10.1145。 网址 https:// / doi.org/ 276698.276708/ XNUMX。
https:/ / doi.org/10.1145/ 276698.276708

[6] 安德里斯·安巴尼斯。 通过查询复杂性理解量子算法。 在 2018 年国际数学家大会论文集,第 3 卷,第 3249-3270 页,2018 年。10.1142/ 9789813272880_0181。
https:/ / doi.org/ 10.1142 / 9789813272880_0181

[7] Andris Ambainis、Loïck Magnin、Martin Roetteler 和 Jeremie Roland。 用于量子态生成的对称辅助对手。 在 2011 年 IEEE 第 26 届计算复杂性年会的论文集,CCC '11,第 167-177 页,美国,2011 年。IEEE 计算机协会。 ISBN 9780769544113。10.1109/ CCC.2011.24。 网址 https:// / doi.org/ 10.1109/ CCC.2011.24。
https:///doi.org/10.1109/CCC.2011.24

[8] Andris Ambainis、Ansis Rosmanis 和 Dominique Unruh。 对经典证明系统的量子攻击:量子重绕的难度。 在 2014 年 IEEE 第 55 届计算机科学基础年度研讨会论文集,FOCS '14,第 474-483 页,美国,2014 年。IEEE 计算机协会。 ISBN 9781479965175. 10.1109/ FOCS.2014.57。 网址 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 de Wolf。 量子优惠券收集器。 在 Steven T. Flammia,编辑,第 15 届量子计算、通信和密码学理论会议 (TQC 2020),Leibniz International Proceedings in Informatics (LIPIcs) 第 158 卷,第 10:1–10:17 页,Dagstuhl,德国, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik。 ISBN 978-3-95977-146-7。 10.4230/ LIPIcs.TQC.2020.10。 网址 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. 网址 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 月。ISSN 5411-10.1145。 502090.502097/ 10.1145。 网址 https:// / doi.org/ 502090.502097/ XNUMX。
https:/ / doi.org/10.1145/ 502090.502097

[12] 约翰·贝尔。 关于爱因斯坦-波多尔斯基-罗森悖论。 物理学,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] Aleksandrs Belovs 和 Ansis Rosmanis。 2020 年量子态近似计数的严格量子下限。
的arXiv:2002.06879

[15] Fernando GSL Brandão、Aram W. Harrow 和 Michał Horodecki。 局部随机量子电路是近似多项式设计。 数学物理通讯,346 (2): 397–434, 2016. 10.1007/s00220-016-2706-8。 网址 https:/ / doi.org/ 10.1007/ s00220-016-2706-8。
https:/​/​doi.org/​10.1007/​s00220-016-2706-8

[16] 吉尔斯·布拉萨德、彼得·霍耶和阿兰·塔普。 散列和无爪函数的量子密码分析。 SIGACT 新闻,28 (2):14-19,1997 年 0163 月。ISSN 5700-10.1145。 261342.261346/ 10.1145。 网址 https:// / doi.org/ 261342.261346/ XNUMX。
https:/ / doi.org/10.1145/ 261342.261346

[17] 吉尔斯·布拉萨德、彼得·霍耶、米歇尔·莫斯卡和阿兰·塔普。 量子幅度放大和估计。 在 Quantum Computation and Quantum Information,《当代数学》第 305 卷,第 53-74 页。 美国数学学会,2002。ISBN 9780821821404。10.1090/ conm/ 305。
https:/ / doi.org/ 10.1090 / conm / 305

[18] 马克·邦和贾斯汀·塞勒。 近似度和 Markov-Bernstein 不等式的双重下界。 信息Comput., 243 (C): 2–25,2015 年 0890 月。ISSN 5401-10.1016。 2014.12.003/ j.ic.10.1016。 网址 https:// / doi.org/ 2014.12.003/ j.ic.XNUMX。
https:///doi.org/10.1016/j.ic.2014.12.003

[19] 鲍里斯·西雷尔森(Tsirelson)。 贝尔不等式的量子推广。 数学物理快报,4 (2): 93–100, 1980. 10.1007/ BF00417500。 网址 https:// / doi.org/ 10.1007/ BF00417500。
https:/ / doi.org/ 10.1007 / BF00417500

[20] John F. Clauser、Michael A. Horne、Abner Shimony 和 Richard A. Holt。 测试局部隐藏变量理论的拟议实验。 物理。 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] Richard Cleve、Peter Høyer、Benjamin Toner 和 John Watrous。 非本地策略的后果和局限性。 在第 19 届 IEEE 计算复杂性年会的论文集,CCC '04,第 236-249 页,美国,2004 年。IEEE 计算机协会。 ISBN 0769521207. 10.1109/ CCC.2004.1313847。
https:///doi.org/10.1109/CCC.2004.1313847

[22] 阿拉姆·哈罗和赛义德·梅赫拉班。 使用最近邻门和远程门,通过短随机量子电路进行近似酉 t 设计,2018 年。
的arXiv:1809.06957

[23] Norman L. Johnson 和 Samuel Kotz。 瓮模型及其应用:现代离散概率论的一种方法。 威利,1977 年。ISBN 9780471446309。

[24] Shelby Kimmel、Cedric Yen-Yu Lin、Guang Hao Low、Maris Ozols 和 Theodore J. Yoder。 具有最佳样本复杂度的哈密顿模拟。 npj Quantum Information, 3 (1): 13, 2017. 10.1038/ s41534-017-0013-7. 网址 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 年。Schloss Dagstuhl– Leibniz-Zentrum für Informatik。 ISBN 978-3-95977-177-1。 10.4230/ LIPIcs.ITCS.2021.13。 网址 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 和 Mario Szegedy。 状态转换的量子查询复杂度。 在 2011 年 IEEE 第 52 届计算机科学基础年度研讨会论文集,FOCS '11,第 344-353 页,美国,2011 年。IEEE 计算机协会。 ISBN 9780769545714. 10.1109/ FOCS.2011.75。 网址 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 年。Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik。 ISBN 978-3-95977-134-4。 10.4230/ LIPIcs.ITCS.2020.59。 网址 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] Frederic Magniez、Ashwin Nayak、Jeremie Roland 和 Miklos Santha。 通过量子行走搜索。 在第三十九届 ACM 计算理论研讨会论文集,STOC '07,第 575-584 页,纽约,纽约,美国,2007 年。计算机协会。 ISBN 9781595936318. 10.1145/ 1250790.1250874. 网址 https:// / doi.org/ 10.1145/ 1250790.1250874。
https:/ / doi.org/10.1145/ 1250790.1250874

[29] 瑞安·奥唐纳。 布尔函数分析。 美国剑桥大学出版社,2014 年。ISBN 1107038324。10.1017/ CBO9781139814782。
https:/ / doi.org/ 10.1017 / CBO9781139814782

[30] 马丁·拉布和安吉丽卡·斯蒂格。 “球进垃圾箱”——一个简单而严谨的分析。 在第二届计算机科学随机化和近似技术国际研讨会的会议记录中,RANDOM '98,第 159-170 页,柏林,海德堡,1998 年。Springer-Verlag。 ISBN 354065142X。 10.1007/ 3-540-49543-6_13。
https:/​/​doi.org/​10.1007/​3-540-49543-6_13

[31] 本·W·赖查特。 量子查询算法的思考。 在第二十二届 ACM-SIAM 离散算法研讨会论文集,SODA '11,第 560-569 页,美国,2011 年。工业和应用数学学会。 10.1137/ 1.9781611973082.44。
https:/ / doi.org/10.1137/ 1.9781611973082.44

[32] 阿尔弗雷德·雷尼。 序统计理论。 Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191–231, 1953. 10.1007/BF02127580。 网址 https:// / doi.org/ 10.1007/ BF02127580。
https:/ / doi.org/ 10.1007 / BF02127580

被引用

[1] Daniel Stilck França 和 Raul Garcia-Patron,“量子优势游戏:连接验证和模拟”, 的arXiv:2011.12173.

[2] Nicholas LaRacuente,“从复杂但容易指定的状态中分离出量子甲骨文”, 的arXiv:2104.07247.

[3] Scott Aaronson,“与量子查询复杂性相关的开放问题”, 的arXiv:2109.06917.

以上引用来自 SAO / NASA广告 (最近成功更新为2021-10-07 11:15:15)。 该列表可能不完整,因为并非所有发布者都提供合适且完整的引用数据。

无法获取 Crossref引用的数据 在上一次尝试2021-10-07 11:15:13期间:无法从Crossref获取10.22331 / q-2021-10-07-560的引用数据。 如果DOI是最近注册的,这是正常的。

柏拉图重新构想的 Web3。 数据智能放大。
单击此处访问。

资料来源:https://quantum-journal.org/papers/q-2021-10-07-560/

现货图片

学术风投

最新情报

现货图片