受量子启发的永久身份

由柏拉图重新发布

关注： 0

¹加州理工学院量子信息与物质研究所，美国加利福尼亚州帕萨迪纳市91125
²计算机科学，塔夫茨大学，梅德福，MA 02155，美国

抽象

永久性对于复杂性理论和组合学都至关重要。在量子计算中，永久性出现在线性光学计算的输出幅度的表达式中，例如在玻色子采样模型中。利用这种联系，我们为许多现有的和新的非凡的永久身份提供了受量子启发的证明。最值得注意的是，我们给出了麦克马洪主定理的量子启发证明以及该定理的新推广的证明。该定理的先前证明使用了完全不同的想法。除了它们的纯组合应用之外，我们的结果证明了具有输入猫状态的线性光量子计算的精确和近似采样的经典难度。

特色图片：受量子启发的证明导致了关于具有猫状态输入的量子计算的新复杂性结果（使用 DALL.E 生成的抽象描述）。

►BibTeX数据

@文章{Chabaud2022量子启发， doi = {10.22331/q-2022-12-19-877}，网址 = {https://doi.org/10.22331/q-2022-12-19-877}， title = {受量子启发的永久身份},作者 = {Chabaud、Ulysse 和 Deshpande、Abhinav 和 Mehraban、Saeed}，期刊 = {{量子}}, issn = {2521-327X}，出版商 = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}，音量 = {6}，页数 = {877}，月 = 十二月，年 = {2022} }

►参考

[1] H. Minc，“永久物”，卷。 6. 剑桥大学出版社，1984 年。
https：/ / doi.org/ 10.1017 / CBO9781107340688

[2] JK Percus，“组合方法”，卷。 4. 施普林格科学与商业媒体，2012 年。
https://doi.org/10.1007/978-1-4612-6404-0

[3] LG Valiant，“计算永久的复杂性”，理论计算机科学 8，189-201（1979）。
https://doi.org/10.1016/0304-3975(79)90044-6

[4] ER Caianiello，“关于量子场论——I：不使用费曼图的电动力学戴森方程的显式解”，Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953)。
https：/ / doi.org/ 10.1007 / BF02781659

[5] S. Scheel，“线性光网络中的永久物”，quant-ph/0406127。
arXiv：quant-ph / 0406127

[6] S. Aaronson 和 A. Arkhipov，“线性光学的计算复杂性”，计算理论 9, 143 (2013)，arXiv:1011.3245。
https：/ / doi.org/10.1145/ 1993636.1993682
arXiv：arXiv：1011.3245

[7] S. Aaronson，“永久物是# P-hard 的线性光学证明”，皇家学会学报 A：数学、物理和工程科学 467，3393–3405 (2011)。
https：/ / doi.org/ 10.1098 / rspa.2011.0232

[8] S. Rahimi-Keshari、AP Lund 和 TC Ralph，“关于计算复杂性理论，量子光学能说些什么？”，Physical review letters 114, 060501 (2015)。
https：/ / doi.org/ 10.1103 / PhysRevLett.114.060501

[9] D. Grier 和 L. Schaeffer，“使用线性光学的永久性材料的新硬度结果”，arXiv：1610.04670。
arXiv：arXiv：1610.04670

[10] PP Rohde、DW Berry、KR Motes 和 JP Dowling，“一类多维积分的 $#$P 硬度的量子光学论证”，arXiv：1607.04960。
arXiv：arXiv：1607.04960

[11] L. Chakhmakhchyan、NJ Cerf 和 R. Garcia-Patron，“用于估计半正定矩阵永久性的受量子启发的算法”，Physical Review A 96, 022329 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevA.96.022329

[12] A. Meiburg，“正半定永久物和量子态层析成像的不可近似性”，arXiv：2111.03142。
arXiv：arXiv：2111.03142

[13] PA MacMahon，“组合分析，第一卷和第二卷”，卷。 137. 美国数学学会，2001 年。

[14] I. Good，“通过 MacMahon 的‘主定理’证明某些‘二项式’恒等式”，剑桥哲学会数学会刊，第 58 卷。 161，第 162-1962 页，剑桥大学出版社。 XNUMX.
https：/ / doi.org/ 10.1017 / S030500410003632X

[15] L. Carlitz，“MacMahon 主定理的应用”，SIAM 应用数学杂志 26, 431–436 (1974)。
https：/ / doi.org/10.1137/ 0126040

[16] L. Carlitz，“与 MacMahon 主定理相关的一些扩展和卷积公式”，SIAM 数学分析期刊 8, 320–336 (1977)。
https：/ / doi.org/10.1137/ 0508023

[17] HJ Ryser，“组合数学”，卷。 14. 美国数学学会，1963 年。

[18] K. Balasubramanian，矩阵的组合学和对角线。博士论文，印度统计研究所 - 加尔各答，1980 年。

[19] ET Bax，用于计数问题的有限差分算法。博士论文，加州理工学院，1998。

[20] DG Glynn，“方阵的永久性”，欧洲组合学杂志 31，1887-1891（2010 年）。
https：///doi.org/10.1016/j.ejc.2010.01.010

[21] PP Rohde、KR Motes、PA Knott、J. Fitzsimons、WJ Munro 和 JP Dowling，“用线性光学对广义猫状态进行采样的猜想的证据很难”，Physical Review A 91, 012342 (2015)。
https：/ / doi.org/ 10.1103 / PhysRevA.91.012342

[22] C. Weedbrook、S. Pirandola、R. García-Patrón、NJ Cerf、TC Ralph、JH Shapiro 和 S. Lloyd，“高斯量子信息”，现代物理学评论 84、621（2012 年）。
https：/ / doi.org/ 10.1103 / RevModPhys.84.621

[23] A. Leverrier，“$SU(p, q)$ coherent states and a Gaussian de Finetti theorem,” Journal of Mathematical Physics 59, 042202 (2018)。
https：/ / doi.org/10.1063/ 1.5007334

[24] T. Jiang 和 Y. Ma，“随机正交矩阵与独立正态矩阵之间的距离”，arXiv：1704.05205。
arXiv：arXiv：1704.05205

[25] AC Dixon，“关于二项式定理的某个展开式中系数的立方之和”，Messenger of Mathematics 20, 79–80 (1891)。

[26] I. Good，“麦克马洪‘主定理’的简短证明”，剑桥哲学学会数学会刊，卷。 58，第 160-160 页，剑桥大学出版社。 1962.
https：/ / doi.org/ 10.1017 / S0305004100036318

[27] S. Garoufalidis、TT Lê 和 D. Zeilberger，“量子麦克马洪主定理”，美国国家科学院院刊 103，13928–13931（2006 年）。
https：/ / doi.org/ 10.1073 / pnas.0606003103

[28] M. Konvalinka 和 I. Pak，“麦克马洪主定理的非交换扩展”，数学进展 216, 29–61 (2007)。
https:/ / doi.org/ 10.1016/ j.aim.2007.05.020

[29] MP Tuite，“麦克马洪主定理的一些概括”，组合理论杂志，系列 A 120，92–101（2013 年）。
https：///doi.org/10.1016/j.jcta.2012.07.007

[30] VV Kocharovsky、VV Kocharovsky 和 SV Tarasov，“哈夫尼主定理”，线性代数及其应用 144–161 (2022)。
https：///doi.org/10.1016/j.laa.2022.06.021

[31] WY Chen、H. Galbraith 和 J. Louck，“角动量理论、本影演算和组合学”，计算机与数学及其应用 41，1199–1214（2001 年）。
https://doi.org/10.1016/S0898-1221(01)00091-8

[32] BM Terhal 和 DP DiVincenzo，“非相互作用费米子量子电路的经典模拟”，物理评论 A 65，032325（2002 年）。
https：/ / doi.org/ 10.1103 / PhysRevA.65.032325

[33] V. Shchesnovich，“多端口设备中多光子实验的部分不可区分性理论”，Physical Review A 91, 013844 (2015)。
https：/ / doi.org/ 10.1103 / PhysRevA.91.013844

[34] D. Spivak、MY Niu、BC Sanders 和 H. de Guise，“费米子和玻色子的广义干涉”，Physical Review Research 4, 023013 (2022)。
https：/ / doi.org/ 10.1103 / PhysRevResearch.4.023013

[35] E.-J。 Kuo、Y. Xu、D. Hangeiter、A. Grankin 和 M. Hafezi，“广义玻色子的玻色子采样”，arXiv：2204.08389。
https：/ / doi.org/ 10.1103 / PhysRevResearch.4.043096
arXiv：arXiv：2204.08389

[36] A. Clément、N. Heurtel、S. Mansfield、S. Perdrix 和 B. Valiron，“LO$_text{v}$-Calculus：线性光量子电路的图形语言”，arXiv：2204.11787。
https：///doi.org/10.4230/LIPIcs.MFCS.2022.35
arXiv：arXiv：2204.11787

[37] G. De Felice 和 B. Coecke，“通过弦图的量子线性光学”，arXiv：2204.12985。
arXiv：arXiv：2204.12985

[38] B. Peropadre、GG Guerreschi、J. Huh 和 A. Aspuru-Guzik，“微波玻色子采样提案”，物理评论信 117，140505（2016 年）。
https：/ / doi.org/ 10.1103 / PhysRevLett.117.140505

[39] S. Girvin，“电路 qed 中的薛定谔猫状态”，arXiv：1710.03179。
arXiv：arXiv：1710.03179

[40] X. Gu、AF Kockum、A. Miranowicz、Y.-x。 Liu 和 F. Nori，“具有超导量子电路的微波光子学”，物理报告 718, 1–102 (2017)。
https：///doi.org/10.1016/j.physrep.2017.10.002

[41] J. Huh，“一种用于计算永久矩阵的快速量子算法”，arXiv：2205.01328。
arXiv：arXiv：2205.01328

[42] S. Aaronson 和 T. Hance，“Gurvits 的永久近似算法的一般化和去随机化”，Quantum Info。电脑。 14, 541–559 (2014)。
https：/ / doi.org/ 10.26421 / QIC14.7-8-1

[43] S. Chin 和 J. Huh，“玻色子采样中的广义同步”，《科学报告》8、1-9（2018 年）。
https://doi.org/10.1038/s41598-018-24302-5

[44] M.-H. Yung、X. Gao 和 J. Huh，“线性光学中采样玻色子的普遍界限及其计算意义”，《国家科学评论》6，719-729（2019 年）。
https://doi.org/10.1093/nsr/nwz048

[45] VS Shchesnovich，“关于从不可区分的玻色子的量子干涉中采样的经典复杂性，”国际量子信息杂志 18，2050044（2020 年）。
https：/ / doi.org/ 10.1142 / S0219749920500446

[46] DM Jackson，“序列的某些枚举问题的统一”，《组合理论杂志》，系列 A 22，92–96（1977 年）。
https://doi.org/10.1016/0097-3165(77)90066-8

[47] FR Cardoso、DZ Rossatto、GP Fernandes、G. Higgins 和 CJ Villas-Boas，“用于量子信息处理和量子传感的双模压缩态叠加”，Physical Review A 103, 062405 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevA.103.062405

[48] AP Lund、A. Laing、S. Rahimi-Keshari、T. Rudolph、JL O'Brien 和 TC Ralph，“从高斯态进行玻色子采样”，Physical review letters 113, 100502 (2014)。
https：/ / doi.org/ 10.1103 / PhysRevLett.113.100502

[49] JP Olson、KP Seshadreesan、KR Motes、PP Rohde 和 JP Dowling，“对任意增加光子或减少光子的压缩态进行采样与玻色子采样属于同一复杂性类别，”Physical Review A 91, 022317 (2015)。
https：/ / doi.org/ 10.1103 / PhysRevA.91.022317

[50] CS Hamilton、R. Kruse、L. Sansoni、S. Barkhofen、C. Silberhorn 和 I. Jex，“高斯玻色子采样”，物理评论信函 119、170501（2017 年）。
https：/ / doi.org/ 10.1103 / PhysRevLett.119.170501

[51] A. Lund、S. Rahimi-Keshari 和 T. Ralph，“使用高斯连续变量测量进行精确玻色子采样”，Physical Review A 96, 022301 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevA.96.022301

[52] L. Chakhmakhchyan 和 NJ Cerf，“使用高斯测量进行玻色子采样”，物理评论 A 96，032326（2017 年）。
https：/ / doi.org/ 10.1103 / PhysRevA.96.032326

[53] U. Chabaud、T. Douce、D. Markham、P. van Loock、E. Kashefi 和 G. Ferrini，“从光子添加或光子减去压缩状态进行连续变量采样”，物理评论 A 96，062307（ 2017）。
https：/ / doi.org/ 10.1103 / PhysRevA.96.062307

[54] N. Quesada、JM Arrazola 和 N. Killoran，“使用阈值检测器进行高斯玻色子采样”，Physical Review A 98, 062322 (2018)。
https：/ / doi.org/ 10.1103 / PhysRevA.98.062322

[55] A. Deshpande、A. Mehta、T. Vincent、N. Quesada、M. Hinsche、M. Ioannou、L. Madsen、J. Lavoie、H. Qi、J. Eisert 等，“Quantum computational advantage via high -dimensional Gaussian boson sampling”，Science advances 8, 7894 (2022)。
https://doi.org/10.1126/sciadv.abi7894