1加拿大滑铁卢大学量子计算研究所
2美国加州大学圣地亚哥分校计算机科学与工程系和数学系
3巴西弗里米嫩斯联邦大学Física研究所，巴西尼特拉伊，RJ，24210-340，
4Xanadu，多伦多，ON，M5G 2C8，加拿大
5工程物理系，École Polytechnique de Montréal，蒙特利尔，QC，H3T 1JK，加拿大
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
高斯玻色子采样是一种光子量子计算模型，作为构建能够执行经典设备无法完成的任务的量子设备的平台而备受关注。 因此，从计算复杂性理论的角度来看，巩固模拟这些设备的难度的数学基础具有重要意义。 我们表明，在标准的反集中和永久高斯猜想下，没有有效的经典算法可以从理想的高斯玻色子采样分布（甚至近似）中采样，除非多项式层次崩溃。 硬度证明适用于模式数量与光子数量呈二次方关系的情况，人们普遍认为这种情况下硬度适用，但仍然没有明确的证据。
证明的关键是一种对高斯玻色子采样设备进行编程的新方法，以便输出概率与任意矩阵的子矩阵的永久值成正比。 这种技术是我们称之为 BipartiteGBS 的 Scattershot BosonSampling 的推广。 我们还通过证明近似具有重复行/列的矩阵的永久性的能力赋予能力，在模式比光子少二次方（即高碰撞制度）的情况下证明硬度的目标取得了进展近似无重复矩阵的常量。 减少足以证明 GBS 在不断碰撞的情况下是困难的。
[嵌入的内容]
[嵌入的内容]
►BibTeX数据
►参考
[1] 斯科特·阿伦森和亚历克斯·阿尔希波夫。 “线性光学的计算复杂性”。 计算理论 9, 143–252 (2013)。
https：///doi.org/10.4086/toc.2013.v009a004
[2] Max Tillmann、Borivoje Dakić、René Heilmann、Stefan Nolte、Alexander Szameit 和 Philip Walther。 “实验玻色子采样”。 自然光子学 7, 540–544 (2013)。
https：///doi.org/10.1038/nphoton.2013.102
[3] Justin B. Spring、Benjamin J. Metcalf、Peter C. Humphreys、W. Steven Kolthammer、Xian-Min Jin、Marco Barbieri、Animesh Datta、Nicholas Thomas-Peter、Nathan K. Langford、Dmytro Kundys、James C. Gates、Brian J. Smith、Peter GR Smith 和 Ian A. Walmsley。 “光子芯片上的玻色子采样”。 科学 339, 798–801 (2013)。
https：/ / doi.org/ 10.1126 / science.1231692
[4] Andrea Crespi、Roberto Osellame、Roberta Ramponi、Daniel J Brod、Ernesto F Galvao、Nicolo Spagnolo、Chiara Vitelli、Enrico Maiorino、Paolo Mataloni 和 Fabio Sciarrino。 “用于光子玻色子采样的具有任意设计的集成多模干涉仪”。 自然光子学 7, 545–549 (2013)。
https：///doi.org/10.1038/nphoton.2013.112
[5] Matthew A. Broome、Alessandro Fedrizzi、Saleh Rahimi-Keshari、Justin Dove、Scott Aaronson、Timothy C. Ralph 和 Andrew G. White。 “可调谐电路中的光子玻色子采样”。 科学 339, 794–798 (2013)。
https：/ / doi.org/ 10.1126 / science.1231440
[6] Austin P Lund、Anthony Laing、Saleh Rahimi-Keshari、Terry Rudolph、Jeremy L O'Brien 和 Timothy C Ralph。 “来自高斯状态的玻色子采样”。 物理。 牧师莱特。 113, 100502 (2014)。
https：/ / doi.org/ 10.1103 / PhysRevLett.113.100502
[7] Craig S. Hamilton、Regina Kruse、Linda Sansoni、Sonja Barkhofen、Christine Silberhorn 和 Igor Jex。 “高斯玻色子采样”。 物理。 牧师莱特。 119, 170501 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevLett.119.170501
[8] Marco Bentivegna、Nicolò Spagnolo、Chiara Vitelli、Fulvio Flamini、Niko Viggianiello、Ludovico Latmiral、Paolo Mataloni、Daniel J Brod、Ernesto F Galvão、Andrea Crespi、Roberta Ramponi、Roberto Osellame 和 Fabio Sciarrino。 “实验散射玻色子采样”。 科学进展 1，e1400255 (2015)。
https：/ / doi.org/ 10.1126 / sciadv.1400255
[9] Hui Wang, Yu He, Yu-Huai Li, Zu-En Su, Bo Li, He-Liang Huang, Xing Ding, Ming-Cheng Chen, Chang Liu, Jian Qin, Jin-Peng Li, Yu-Ming He, Christian Schneider , Martin Kamp, Cheng-Zhi Peng, Sven Höfling, Chao-Yang Lu, and Jian-Wei Pan. “高效多光子玻色子采样”。 自然光子学 11, 361 (2017)。
https：///doi.org/10.1038/nphoton.2017.63
[10] 钟汉森、彭立超、李元、胡一、李伟、秦健、吴典、张伟军、李浩、张璐、王振、游立行、蒋晓、李丽、刘奈乐, Jonathan P. Dowling、Chao-Yang Lu 和 Jian-Wei Pan。 “实验高斯玻色子采样”。 科学公告 64, 511–515 (2019)。
https：///doi.org/10.1016/j.scib.2019.04.007
[11] Regina Kruse、Craig S. Hamilton、Linda Sansoni、Sonja Barkhofen、Christine Silberhorn 和 Igor Jex。 “高斯玻色子采样的详细研究”。 物理。 修订版 A 100, 032326 (2019)。
https：/ / doi.org/ 10.1103 / PhysRevA.100.032326
[12] Thomas R Bromley、Juan Miguel Arrazola、Soran Jahangiri、Josh Izaac、Nicolás Quesada、Alain Delgado Gran、Maria Schuld、Jeremy Swinarton、Zeid Zabaneh 和 Nathan Killoran。 “近期光子量子计算机的应用：软件和算法”。 量子科学与技术 5, 034010 (2020).
https：/ / doi.org/ 10.1088 / 2058-9565 / ab8504
[13] JM Arrazola、V. Bergholm、K. Brádler、TR Bromley、MJ Collins、I. Dhand、A. Fumagalli、T. Gerrits、A. Goussev、LG Helt、J. Hundal、T. Isacsson、RB Israel、J. Izaac , S. Jahangiri, R. Janik, N. Killoran, SP Kumar, J. Lavoie, AE Lita, DH Mahler, M. Menotti, B. Morrison, SW Nam, L. Neuhaus, HY Qi, N. Quesada, A. Repingon、KK Sabapathy、M. Schuld、D. Su、J. Swinarton、A. Száva、K. Tan、P. Tan、VD Vaidya、Z. Vernon、Z. Zabaneh 和 Y. Zhang。 “在可编程纳米光子芯片上具有许多光子的量子电路”。 自然 591, 54–60 (2021)。
https://doi.org/10.1038/s41586-021-03202-1
[14] Jianwei Wang、Fabio Sciarrino、Anthony Laing 和 Mark G. Thompson。 “集成光子量子技术”。 自然光子学 14, 273–284 (2020)。
https://doi.org/10.1038/s41566-019-0532-1
[15] Z. Vernon、N. Quesada、M. Liscidini、B. Morrison、M. Menotti、K. Tan 和 JE Sipe。 “用于连续可变量子采样的可缩放压缩光源”。 物理。 Rev. Applied 12, 064024 (2019)。
https：/ / doi.org/ 10.1103 / PhysRevApplied.12.064024
[16] Joonsuk Huh、Gian Giacomo Guerreschi、Borja Peropadre、Jarrod R. McClean 和 Alán Aspuru-Guzik。 “分子电子振动光谱的玻色子采样”。 自然光子学 9, 615–620 (2015)。
https：///doi.org/10.1038/nphoton.2015.153
[17] 胡安·米格尔·阿拉佐拉和托马斯·R·布罗姆利。 “使用高斯玻色子采样找到密集子图”。 物理。 牧师莱特。 121, 030503 (2018)。
https：/ / doi.org/ 10.1103 / PhysRevLett.121.030503
[18] Leonardo Banchi、Mark Fingerhuth、Tomas Babej、Christopher Ing 和 Juan Miguel Arrazola。 “与高斯玻色子采样的分子对接”。 科学进展 6，eaax1950 (2020)。
https:/ / doi.org/ 10.1126/ sciadv.aax1950
[19] Soran Jahangiri、Juan Miguel Arrazola、Nicolás Quesada 和 Nathan Killoran。 “高斯玻色子采样的点过程”。 物理。 修订版 E 101, 022134 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevE.101.022134
[20] Maria Schuld、Kamil Brádler、Robert Israel、Daiqin Su 和 Brajesh Gupt。 “用高斯玻色子采样器测量图形的相似性”。 物理。 修订版 A 101, 032314 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevA.101.032314
[21] Soran Jahangiri、Juan Miguel Arrazola、Nicolás Quesada 和 Alain Delgado。 “模拟分子振动激发的量子算法”。 物理化学化学物理 22, 25528–25537 (2020)。
https:/ / doi.org/ 10.1039/ D0CP03593A
[22] Leonardo Banchi、Nicolás Quesada 和 Juan Miguel Arrazola。 “训练高斯玻色子采样分布”。 物理。 修订版 A 102, 012417 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevA.102.012417
[23] Lars S. Madsen、Fabian Laudenbach、Mohsen Falamarzi。 Askarani、Fabien Rortais、Trevor Vincent、Jacob FF Bulmer、Filippo M. Miatto、Leonhard Neuhaus、Lukas G. Helt、Matthew J. Collins、Adriana E. Lita、Thomas Gerrits、Sae Woo Nam、Varun D. Vaidya、Matteo Menotti、 Ish Dhand、Zachary Vernon、Nicolás Quesada 和 Jonathan Lavoie。 “可编程光子处理器的量子计算优势”。 自然 606, 75–81 (2022)。
https：///doi.org/10.1038/s41586-022-04725-x
[24] 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, 1460–1463 (2020)。
https：/ / doi.org/ 10.1126 / science.abe8770
[25] Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, 等。 “使用受激压缩光的相位可编程高斯玻色子采样”。 物理。 牧师莱特。 127、180502（2021 年）。
https：/ / doi.org/ 10.1103 / PhysRevLett.127.180502
[26] Abhinav Deshpande、Arthur Mehta、Trevor Vincent、Nicolás Quesada、Marcel Hinsche、Marios Ioannou、Lars Madsen、Jonathan Lavoie、Haoyu Qi、Jens Eisert、Dominik Hangleiter、Bill Fefferman 和 Ish Dhand。 “通过高维高斯玻色子采样的量子计算优势”。 科学进展 8，eabi7894 (2022)。
https://doi.org/10.1126/sciadv.abi7894
[27] Raúl García-Patrón、Jelmer J Renema 和 Valery Shchesnovich。 “在有损架构中模拟玻色子采样”。 量子 3, 169 (2019)。
https://doi.org/10.22331/q-2019-08-05-169
[28] Haoyu Qi、Daniel J. Brod、Nicolás Quesada 和 Raúl García-Patrón。 “噪声高斯玻色子采样的经典可模拟性机制”。 物理。 牧师莱特。 124、100502（2020 年）。
https：/ / doi.org/ 10.1103 / PhysRevLett.124.100502
[29] Michael Reck、Anton Zeilinger、Herbert J. Bernstein 和 Philip Bertani。 “任何离散酉算子的实验实现”。 物理。 牧师莱特。 73, 58–61 (1994)。
https：/ / doi.org/ 10.1103 / PhysRevLett.73.58
[30] William R Clements、Peter C Humphreys、Benjamin J Metcalf、W Steven Kolthammer 和 Ian A Walsmley。 “通用多端口干涉仪的优化设计”。 光学 3, 1460–1465 (2016)。
https：///doi.org/10.1364/OPTICA.3.001460
[31] Hubert de Guise、Olivia Di Matteo 和 Luis L. Sánchez-Soto。 “酉变换的简单因式分解”。 物理。 修订版 A 97, 022328 (2018)。
https：/ / doi.org/ 10.1103 / PhysRevA.97.022328
[32] 布林·贝尔和伊恩·沃尔姆斯利。 “进一步紧凑化线性光学单元”。 APL 光子学 6, 070804 (2021)。
https：/ / doi.org/10.1063/ 5.0053421
[33] 蒋铁峰。 “一个典型的正交矩阵有多少项可以用独立法线近似？”。 概率年鉴 34, 1497–1529 (2006)。
https：/ / doi.org/10.1214/ 009117906000000205
[34] 亚历山大一世巴尔维诺克。 “旅行商问题的两个算法结果”。 运筹学数学 21, 65–84 (1996)。
https：/ / doi.org/ 10.1287 / moor.21.1.65
[35] 丹尼尔·格里尔和卢克·谢弗。 “使用线性光学的永久性材料的新硬度结果”。 在第 33 届计算复杂性会议 (CCC 2018) 中。 莱布尼茨国际信息学论文集 (LIPIcs) 第 102 卷，第 19:1–19:29 页。 Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018)。
https：///doi.org/10.4230/LIPIcs.CCC.2018.19
[36] Scott Aaronson 和 Daniel J. Brod。 “丢失光子的玻色子采样”。 物理。 修订版 A 93, 012335 (2016)。
https：/ / doi.org/ 10.1103 / PhysRevA.93.012335
[37] Christian Weedbrook、Stefano Pirandola、Raúl García-Patrón、Nicolas J. Cerf、Timothy C. Ralph、Jeffrey H. Shapiro 和 Seth Lloyd。 “高斯量子信息”。 牧师国防部。 物理。 84, 621–669 (2012)。
https：/ / doi.org/ 10.1103 / RevModPhys.84.621
[38] 爱德华多·R·卡亚尼罗。 “论量子场论——I：不使用费曼图的电动力学戴森方程的显式解”。 Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953)。
https：/ / doi.org/ 10.1007 / BF02781659
[39] 亚历山大·巴维诺克。 “分区函数的组合学和复杂性”。 第 276 卷。斯普林格。 (2016)。
https://doi.org/10.1007/978-3-319-51829-9
[40] Andreas Björklund、Brajesh Gupt 和 Nicolás Quesada。 “复杂矩阵的更快哈夫尼公式及其在超级计算机上的基准测试”。 实验算法学杂志 (JEA) 24, 11 (2019)。
https：/ / doi.org/10.1145/ 3325111
[41] L. Chakhmakhchyan 和 NJ Cerf。 “使用高斯测量的玻色子采样”。 物理。 修订版 A 96, 032326 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevA.96.032326
[42] 沉建宏。 “关于高斯随机矩阵的奇异值”。 线性代数及其应用 326, 1–14 (2001)。
https://doi.org/10.1016/S0024-3795(00)00322-0
[43] Uffe Haagerup 和 Steen Thorbjørnsen。 “具有复杂高斯项的随机矩阵”。 Expositiones Mathematicae 21, 293–337 (2003)。
https://doi.org/10.1016/S0723-0869(03)80036-1
[44] Brajesh Gupt、Josh Izaac 和 Nicolás Quesada。 “海象：用于计算哈夫尼、厄米多项式和高斯玻色子采样的库”。 开源软件杂志 4, 1705 (2019)。
https：///doi.org/10.21105/joss.01705
[45] Alex Arkhipov 和 Greg Kuperberg。 “玻色子生日悖论”。 几何与拓扑专论 18, 1–7 (2012)。
https：///doi.org/10.2140/gtm.2012.18.1
[46] Antonia M Tulino 和 Sergio Verdú。 “随机矩阵理论和无线通信”。 现在出版公司 (2004)。
https：/ / doi.org/10.1561/ 0100000001
[47] Michael J. Bremner、Richard Jozsa 和 Dan J. Shepherd。 “通勤量子计算的经典模拟意味着多项式层次结构的崩溃”。 伦敦皇家学会会刊 A：数学、物理和工程科学（2010 年）。
https：/ / doi.org/ 10.1098 / rspa.2010.0301
[48] 拉里斯托克迈尔。 “近似计数的复杂性”。 在第十五届年度 ACM 计算理论研讨会论文集中。 第 118-126 页。 斯托克 '83。 计算机协会 (1983)。
https：/ / doi.org/10.1145/ 800061.808740
[49] Nicolás Quesada、Rachel S. Chadwick、Bryn A. Bell、Juan Miguel Arrazola、Trevor Vincent、Haoyu Qi 和 Raúl García-Patrón。 “模拟高斯玻色子采样的二次加速”。 PRX 量子 3, 010306 (2022)。
https：/ / doi.org/ 10.1103 / PRXQuantum.3.010306
[50] Jacob FF Bulmer、Bryn A Bell、Rachel S Chadwick、Alex E Jones、Diana Moise、Alessandro Rigazzi、Jan Thorbecke、Utz-Uwe Haus、Thomas Van Vaerenbergh、Raj B Patel 等。 “高斯玻色子采样中量子优势的边界”。 科学进展 8，eabl9236 (2022)。
https:// / doi.org/ 10.1126/ sciadv.abl9236
[51] 赫伯特·约翰·莱瑟。 《组合数学》。 第 14 卷。美国数学学会。 (1963)。
https：///doi.org/10.5948/UPO9781614440147
[52] Alex Neville、Chris Sparrow、Raphaël Clifford、Eric Johnston、Patrick M Birchall、Ashley Montanaro 和 Anthony Laing。 “具有优于近期实验性能的经典玻色子采样算法”。 自然物理学 13, 1153–1157 (2017)。
https：/ / doi.org/ 10.1038 / nphys4270
[53] 彼得克利福德和拉斐尔克利福德。 “玻色子采样的经典复杂性”。 第 146-155 页。 工业和应用数学学会。 (2018)。
https：/ / doi.org/10.1137/ 1.9781611975031.10
[54] 彼得克利福德和拉斐尔克利福德。 “更快的经典玻色子采样”（2020 年）。 arXiv:2005.04214。
的arXiv：2005.04214
[55] Philip J Hanlon、Richard P Stanley 和 John R Stembridge。 “正态分布随机矩阵谱的某些组合方面”。 当代数学 138, 151–174 (1992)。
https：/ ‐ / doi.org/10.1090/conm/138/1199126
[56] D 迈瓦尔德和 D 克劳斯。 “复杂 Wishart 和复杂逆 Wishart 分布矩阵矩的计算”。 IEE 会议记录 – 雷达、声纳和导航 147、162–168 (2000)。
https://doi.org/10.1049/ip-rsn:20000493
[57] SM 巴尼特和 PM 拉德莫尔。 “理论量子光学中的方法”。 克拉伦登出版社。 (2002)。
https：///doi.org/10.1093/acprof：oso / 9780198563617.001.0001
[58] 纳撒尼尔·R·古德曼。 《基于某多元复高斯分布的统计分析（导论）》。 数理统计年鉴 34, 152–177 (1963)。
https：/ / doi.org/ 10.1214 / aoms / 1177704250
[59] 伊琳娜舍夫佐娃。 “关于 Berry-Esseen 型不等式中的绝对常数”。 Doklady 数学 89, 378–381 (2014)。
https：/ / doi.org/ 10.1134 / S1064562414030338
[60] 阿莱西奥·塞拉菲尼。 “量子连续变量：理论方法入门”。 CRC出版社。 (2017)。
https：/ / doi.org/10.1201/ 9781315118727
[61] 尼古拉斯·克萨达、胡安·米格尔·阿拉佐拉和内森·基洛兰。 “使用阈值检测器的高斯玻色子采样”。 物理。 修订版 A 98, 062322 (2018)。
https：/ / doi.org/ 10.1103 / PhysRevA.98.062322
[62] 尼古拉斯·奎萨达和胡安·米格尔·阿拉佐拉。 “多项式空间和指数时间内高斯玻色子采样的精确模拟”。 物理。 牧师研究 2, 023005 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevResearch.2.023005
[63] Peter D. Drummond、Bogdan Opanchuk、A. Dellios 和 MD Reid。 “模拟相空间中的复杂网络：高斯玻色子采样”。 物理。 修订版 A 105, 012427 (2022)。
https：/ / doi.org/ 10.1103 / PhysRevA.105.012427
[64] 艾伦·埃德尔曼。 “随机矩阵的特征值和条件数”。 SIAM 矩阵分析和应用杂志 9, 543–560 (1988)。
https：/ / doi.org/10.1137/ 0609045
被引用
[1] Jacob FF Bulmer、Bryn A. Bell、Rachel S. Chadwick、Alex E. Jones、Diana Moise、Alessandro Rigazzi、Jan Thorbecke、Utz-Uwe Haus、Thomas Van Vaerenbergh、Raj B. Patel、Ian A. Walmsley、和 Anthony Laing，“高斯玻色子采样中量子优势的边界”， 科学进展 8 4, eabl9236 (2022).
[2] Martin Houde 和 Nicolás Quesada，“一致的单时间模式压缩光的波导源：好的、坏的和丑陋的”， 的arXiv：2209.13491.
[3] Javier Martínez-Cifuentes、KM Fonseca-Romero 和 Nicolás Quesada，“经典模型比其目标压缩光模型更好地解释了九丈 1.0 高斯玻色子采样器”， 的arXiv：2207.10058.
[4] Joseph T. Iosue、Adam Ehrenberg、Dominik Hangeiter、Abhinav Deshpande 和 Alexey V. Gorshkov，“线性光学中的页面曲线和典型纠缠”， 的arXiv：2209.06838.
[5] Haoyu Qi、Diego Cifuentes、Kamil Brádler、Robert Israel、Timjan Kalajdzievski 和 Nicolás Quesada，“具有局部相互作用的浅层高斯量子光学电路的高效采样”， 物理评论A 105 5，052412（2022）.
[6] Serge Massar、Fabrice Devaux 和 Eric Lantz，“量子图像之间的多光子相关性”， 的arXiv：2211.08674.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-11-30 05:53:10）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-11-30 05:53:09）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
