1瑞士苏黎世联邦理工学院物理系
2瑞士苏黎世联邦理工学院理论研究所
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
量子性证明是一种挑战-响应协议，其中经典验证者可以有效地证明不受信任的证明者的 $textit{quantum advantage}$。 也就是说，量子证明者可以正确回答验证者的挑战并被接受，而任何多项式时间经典证明者都将根据合理的计算假设以高概率被拒绝。 为了应对验证者的挑战，现有的量子性证明通常需要量子证明者执行多项式大小的量子电路和测量的组合。
在这篇论文中，我们给出了两个量子结构的证明，其中证明者只需要执行 $textit{constant-depth quantum circuits}$（和测量）以及对数深度经典计算。 我们的第一个构造是一个通用编译器，它允许我们将所有现有的量子性证明转换为恒定量子深度版本。 我们的第二个构造基于 $textit{learning with rounding}$ 问题，与通用构造相比，它产生的电路深度更短且需要的量子位更少。 此外，第二种结构也具有一定的抗噪能力。
►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。 学习四舍五入，重新审视。 In 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$ 中的那些语言。 计算机与系统科学杂志，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 第 59 届计算机科学基础年度研讨会 (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] Adam Bouland、Bill Fefferman、Chinmay Nirkhe 和 Umesh Vazirani。 关于量子随机电路采样的复杂性和验证。 自然物理学，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)，莱布尼茨国际信息学论文集 (LIPIcs) 第 158 卷，第 8:1–8:14 页，Dagstuhl，德国，2020 年。Schloss Dagstuhl–Leibniz-信息中心。
https：/ / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] 阿布舍克·班纳吉、克里斯·佩克特和阿隆·罗森。 伪随机函数和格子。 In Advances in Cryptology – EUROCRYPT 2012，第 719-737 页。 施普林格柏林海德堡出版社，2012 年。
https://doi.org/10.1007/978-3-642-29011-4_42
[16] 约翰 F 克劳瑟、迈克尔 A 霍恩、艾伯纳希莫尼和理查德 A 霍尔特。 提议的实验来测试局部隐藏变量理论。 物理评论快报，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] 理查德·克利夫和约翰·瓦特鲁斯。 用于量子傅立叶变换的快速并行电路。 在第 41 届计算机科学基础年会会议记录中，第 526-536 页。 IEEE，2000 年。
https：///doi.org/10.1109/SFCS.2000.892140
[19] 皮埃尔·杜萨尔。 Autour de la fonction qui compte le nombre de nobres 总理。 博士论文，利摩日大学，1998 年。
https:/ / www.unilim.fr/ laco/ theses/ 1998/ T1998_01.pdf
[20] Austin G Fowler、Matteo Mariantoni、John M Martinis 和 Andrew N Cleland。 表面代码：迈向实用的大规模量子计算。 物理评论 A, 86(3):032324, 2012。
https：/ / doi.org/ 10.1103 / PhysRevA.86.032324
[21] 弗朗索瓦·勒加尔。 私人信件，2022 年。
[22] Craig Gidney 和 Martin Ekerå。 如何使用 2048 万个嘈杂的量子位在 8 小时内因式分解 20 位 RSA 整数。 量子，5:433，2021 年。
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu 和 Matty J Hoban。 估计浅层电路输出的熵是困难的。 arXiv 预印本 arXiv:2002.12814, 2020。
https://doi.org/10.48550/arXiv.2002.12814
的arXiv：2002.12814
[24] Shuichi Hirahara 和 François Le Gall。 用小深度量子电路测试量子性。 第 46 届计算机科学数学基础国际研讨会 (MFCS 2021)，莱布尼茨国际信息学论文集 (LIPIcs) 第 202 卷，第 59:1–59:15 页，Dagstuhl，德国，2021 年。Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https：///doi.org/10.4230/LIPIcs.MFCS.2021.59
[25] Aram W Harrow 和 Ashley Montanaro。 量子计算至上。 自然，549(7671):203–209, 2017。
https：/ / doi.org/10.1038/nature23458
[26] Peter Høyer 和 Robert Špalek。 量子扇出功能强大。 计算理论，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] Gregory D Kahanamoku-Meyer。 伪造量子数据：经典地击败基于 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 第 59 届计算机科学基础年度研讨会 (FOCS)，第 259-267 页。 IEEE，2018 年。
https：///doi.org/10.1109/FOCS.2018.00033
[32] Michael A Nielsen 和 Isaac Chuang。 量子计算与量子信息，2002。
[33] 作为 Popova 和 AN Rubtsov。 破解高斯玻色子采样的量子优势阈值。 在 Quantum 2.0 会议和展览中，第 QW2A.15 页。 光学出版集团，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] 迈克尔·奥·拉宾。 用于测试素数的概率算法。 数论杂志，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] Dan Shepherd 和 Michael J Bremner。 时间上非结构化的量子计算。 英国皇家学会学报 A：数学、物理和工程科学，465(2105):1413–1439, 2009。
https：/ / doi.org/ 10.1098 / rspa.2008.0443
[38] 彼得·W·肖尔。 量子计算算法：离散对数和因式分解。 在第 35 届计算机科学基础年会会议记录中，第 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, 连辰韩, 洪林银, 黄鹤亮, 霍永恒, 李丽萍, 李娜, 李少伟, 李元, 梁福田, 林春, 林锦, 钱昊然, 乔丹, 容浩, 苏红, 孙丽华,王良元、王世玉、吴大超、徐宇、闫凯、杨伟峰、杨洋、叶阳森、尹江汉、应冲、于佳乐、查晨、张查、张海滨、张凯丽、张一鸣、赵寒, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and 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] Adam Bene Watts、Robin Kothari、Luke Schaeffer 和 Avishay Tal。 浅量子电路和无界扇入浅经典电路之间的指数分离。 在第 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 Chung, 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] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei- 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（2022）.
[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] Akihiro Mizutani、Yuki Takeuchi、Ryo Hiromasa、Yusuke Aikawa 和 Seiichiro Tani，“纠缠魔法状态的计算自测试”， 物理评论 A 106 1, L010601 (2022).
[9] Yihui Quek、Mark M. Wilde 和 Eneet Kaur，“恒定量子深度中的多元迹估计”， 的arXiv：2206.15405.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-09-21 12:16:02）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-09-21 12:16:00）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
