1Institute for Quantum Computing, University of Waterloo, Canada
2Department of Computer Science and Engineering og Department of Mathematics, University of California, San Diego, USA
3Instituto de Física, Universidade Federal Fluminense, Niterói, RJ, 24210-340, Brasilien
4Xanadu, Toronto, ON, M5G 2C8, Canada
5Institut for teknisk fysik, École Polytechnique de Montréal, Montréal, QC, H3T 1JK, Canada
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Gaussisk bosonsampling er en model af fotonisk kvanteberegning, der har tiltrukket sig opmærksomhed som en platform til at bygge kvanteenheder, der er i stand til at udføre opgaver, der er uden for rækkevidde for klassiske enheder. Der er derfor en betydelig interesse, set fra beregningsmæssig kompleksitetsteori, i at fastlægge det matematiske grundlag for hårdheden ved at simulere disse enheder. Vi viser, at der under standard-anti-koncentrations- og permanent-af-Gaussian-formodningerne ikke er nogen effektiv klassisk algoritme til at sample fra ideelle Gaussiske boson-samplingsfordelinger (endda tilnærmelsesvis), medmindre polynomhierarkiet kollapser. Hårdhedsbeviset gælder i det regime, hvor antallet af tilstande skaleres kvadratisk med antallet af fotoner, en indstilling, hvor hårdhed blev udbredt antaget at holde, men som ikke desto mindre ikke havde noget endeligt bevis.
Afgørende for beviset er en ny metode til programmering af en Gaussisk boson-samplingsenhed, således at outputsandsynlighederne er proportionale med permanenterne af submatricer af en vilkårlig matrix. Denne teknik er en generalisering af Scattershot BosonSampling, som vi kalder BipartiteGBS. Vi gør også fremskridt hen imod målet om at bevise hårdhed i regimet, hvor der er færre end kvadratisk flere tilstande end fotoner (dvs. højkollisionsregimet) ved at vise, at evnen til at tilnærme permanenter af matricer med gentagne rækker/kolonner giver evnen at tilnærme permanente matricer uden gentagelser. Reduktionen er tilstrækkelig til at bevise, at GBS er hårdt i det konstante kollisionsregime.
[Indlejret indhold]
[Indlejret indhold]
► BibTeX-data
► Referencer
[1] Scott Aaronson og Alex Arkhipov. "Den beregningsmæssige kompleksitet af lineær optik". Theory of Computing 9, 143-252 (2013).
https:///doi.org/10.4086/toc.2013.v009a004
[2] Max Tillmann, Borivoje Dakić, René Heilmann, Stefan Nolte, Alexander Szameit og Philip Walther. "Eksperimentel bosonprøvetagning". Nature Photonics 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 og Ian A. Walmsley. "Bosonsampling på en fotonisk chip". Science 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 og Fabio Sciarrino. "Integrerede multimode interferometre med vilkårlige designs til fotonisk bosonsampling". Nature photonics 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 og Andrew G. White. "Fotonisk bosonsampling i et afstembart kredsløb". Science 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 og Timothy C Ralph. "Bosonprøvetagning fra en Gaussisk stat". Phys. Rev. Lett. 113, 100502 (2014).
https:///doi.org/10.1103/PhysRevLett.113.100502
[7] Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn og Igor Jex. "Gaussisk bosonsampling". Phys. Rev. Lett. 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 og Fabio Sciarrino. "Eksperimentel scattershot boson-sampling". Science Advances 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 og Jian-Wei Pan. "Højeffektiv multifoton boson prøveudtagning". Nature Photonics 11, 361 (2017).
https:///doi.org/10.1038/nphoton.2017.63
[10] Han-Sen Zhong, Li-Chao Peng, Yuan Li, Yi Hu, Wei Li, Jian Qin, Dian Wu, Weijun Zhang, Hao Li, Lu Zhang, Zhen Wang, Lixing You, Xiao Jiang, Li Li, Nai-Le Liu , Jonathan P. Dowling, Chao-Yang Lu og Jian-Wei Pan. "Eksperimentel Gaussisk bosonprøvetagning". Science Bulletin 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 og Igor Jex. "Detaljeret undersøgelse af Gaussisk bosonprøvetagning". Phys. Rev. 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 og Nathan Killoran. "Anvendelser af kortsigtede fotoniske kvantecomputere: software og algoritmer". Quantum Science and Technology 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 og Y. Zhang. "Kvantekredsløb med mange fotoner på en programmerbar nanofotonisk chip". Nature 591, 54–60 (2021).
https://doi.org/10.1038/s41586-021-03202-1
[14] Jianwei Wang, Fabio Sciarrino, Anthony Laing og Mark G. Thompson. "Integrerede fotoniske kvanteteknologier". Nature Photonics 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 og JE Sipe. "Skalerbar kilde med klemt lys til kontinuerlig variabel kvanteprøvetagning". Phys. Rev. Ansøgt 12, 064024 (2019).
https:///doi.org/10.1103/PhysRevApplied.12.064024
[16] Joonsuk Huh, Gian Giacomo Guerreschi, Borja Peropadre, Jarrod R. McClean og Alán Aspuru-Guzik. "Bosonsampling for molekylære vibroniske spektre". Nature Photonics 9, 615–620 (2015).
https:///doi.org/10.1038/nphoton.2015.153
[17] Juan Miguel Arrazola og Thomas R. Bromley. "Brug af Gaussisk bosonsampling til at finde tætte subgrafer". Phys. Rev. Lett. 121, 030503 (2018).
https:///doi.org/10.1103/PhysRevLett.121.030503
[18] Leonardo Banchi, Mark Fingerhuth, Tomas Babej, Christopher Ing og Juan Miguel Arrazola. "Molekylær docking med Gaussisk bosonsampling". Science Advances 6, eaax1950 (2020).
https:///doi.org/10.1126/sciadv.aax1950
[19] Soran Jahangiri, Juan Miguel Arrazola, Nicolás Quesada og Nathan Killoran. "Punktprocesser med Gaussisk bosonsampling". Phys. Rev. E 101, 022134 (2020).
https:///doi.org/10.1103/PhysRevE.101.022134
[20] Maria Schuld, Kamil Brádler, Robert Israel, Daiqin Su og Brajesh Gupt. "Måling af ligheden mellem grafer med en Gaussisk boson-sampler". Phys. Rev. A 101, 032314 (2020).
https:///doi.org/10.1103/PhysRevA.101.032314
[21] Soran Jahangiri, Juan Miguel Arrazola, Nicolás Quesada og Alain Delgado. "Kvantealgoritme til simulering af molekylære vibrationsexcitationer". Physical Chemistry Chemical Physics 22, 25528–25537 (2020).
https:///doi.org/10.1039/D0CP03593A
[22] Leonardo Banchi, Nicolás Quesada og Juan Miguel Arrazola. "Træning af Gaussiske boson-prøveudtagningsfordelinger". Phys. Rev. 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 og Jonathan Lavoie. "Kvanteberegningsfordel med en programmerbar fotonisk processor". Nature 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 og Jian-Wei Pan. "Kvanteberegningsfordel ved hjælp af fotoner". Science 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, et al. "Fase-programmerbar Gaussisk boson prøvetagning ved hjælp af stimuleret klemt lys". Phys. Rev. Lett. 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 og Ish Dhand. "Kvanteberegningsfordel via højdimensionel Gaussisk bosonsampling". Science Advances 8, eabi7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
[27] Raúl García-Patrón, Jelmer J Renema og Valery Shchesnovich. "Simulering af bosonsampling i tabsgivende arkitekturer". Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169
[28] Haoyu Qi, Daniel J. Brod, Nicolás Quesada og Raúl García-Patrón. "Regimer af klassisk simulabilitet til støjende Gaussisk bosonsampling". Phys. Rev. Lett. 124, 100502 (2020).
https:///doi.org/10.1103/PhysRevLett.124.100502
[29] Michael Reck, Anton Zeilinger, Herbert J. Bernstein og Philip Bertani. "Eksperimentel realisering af enhver diskret enhedsoperatør". Phys. Rev. Lett. 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 og Ian A Walsmley. "Optimalt design til universelle multiport interferometre". Optica 3, 1460-1465 (2016).
https:///doi.org/10.1364/OPTICA.3.001460
[31] Hubert de Guise, Olivia Di Matteo og Luis L. Sánchez-Soto. "Simpel faktorisering af enhedstransformationer". Phys. Rev. A 97, 022328 (2018).
https:///doi.org/10.1103/PhysRevA.97.022328
[32] Bryn A Bell og Ian A Walmsley. "Yderligere komprimering af lineære optiske enheder". APL Photonics 6, 070804 (2021).
https:///doi.org/10.1063/5.0053421
[33] Tiefeng Jiang. "Hvor mange indgange i en typisk ortogonal matrix kan tilnærmes ved uafhængige normaler?". The Annals of Probability 34, 1497–1529 (2006).
https:///doi.org/10.1214/009117906000000205
[34] Alexander I Barvinok. "To algoritmiske resultater for det rejsende sælgerproblem". Mathematics of Operations Research 21, 65-84 (1996).
https:///doi.org/10.1287/moor.21.1.65
[35] Daniel Grier og Luke Schaeffer. "Ny hårdhed resulterer for permanent ved hjælp af lineær optik". I 33rd Computational Complexity Conference (CCC 2018). Bind 102 af Leibniz International Proceedings in Informatics (LIPIcs), side 19:1–19:29. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018).
https:///doi.org/10.4230/LIPIcs.CCC.2018.19
[36] Scott Aaronson og Daniel J. Brod. "BosonSampling med tabte fotoner". Phys. Rev. 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 og Seth Lloyd. "Gaussisk kvanteinformation". Rev. Mod. Phys. 84, 621-669 (2012).
https:///doi.org/10.1103/RevModPhys.84.621
[38] Eduardo R Caianiello. "Om kvantefeltteori - I: eksplicit løsning af Dysons ligning i elektrodynamik uden brug af Feynman-grafer". Il Nuovo Cimento (1943-1954) 10, 1634-1652 (1953).
https:///doi.org/10.1007/BF02781659
[39] Alexander Barvinok. "Kombinatorik og kompleksitet af partitionsfunktioner". Bind 276. Springer. (2016).
https://doi.org/10.1007/978-3-319-51829-9
[40] Andreas Björklund, Brajesh Gupt og Nicolás Quesada. "En hurtigere hafnsk formel for komplekse matricer og dens benchmarking på en supercomputer". Journal of Experimental Algorithmics (JEA) 24, 11 (2019).
https:///doi.org/10.1145/3325111
[41] L. Chakhmakhchyan og NJ Cerf. "Bosonprøvetagning med Gaussiske målinger". Phys. Rev. A 96, 032326 (2017).
https:///doi.org/10.1103/PhysRevA.96.032326
[42] Jianhong Shen. "Om de entalsværdier af Gaussiske tilfældige matricer". Linear Algebra and its Applications 326, 1-14 (2001).
https://doi.org/10.1016/S0024-3795(00)00322-0
[43] Uffe Haagerup og Steen Thorbjørnsen. "Tilfældige matricer med komplekse Gaussiske indtastninger". Expositiones Mathematicae 21, 293-337 (2003).
https://doi.org/10.1016/S0723-0869(03)80036-1
[44] Brajesh Gupt, Josh Izaac og Nicolás Quesada. "Hvalrossen: et bibliotek til beregning af hafnians, hermitpolynomier og Gaussisk bosonsampling". Journal of Open Source Software 4, 1705 (2019).
https://doi.org/10.21105/joss.01705
[45] Alex Arkhipov og Greg Kuperberg. "Det bosoniske fødselsdagsparadoks". Geometri & Topology Monographs 18, 1-7 (2012).
https:///doi.org/10.2140/gtm.2012.18.1
[46] Antonia M Tulino og Sergio Verdú. "Tilfældig matrixteori og trådløs kommunikation". Now Publishers Inc. (2004).
https:///doi.org/10.1561/0100000001
[47] Michael J. Bremner, Richard Jozsa og Dan J. Shepherd. "Klassisk simulering af pendlende kvanteberegninger indebærer kollaps af polynomiehierarkiet". Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (2010).
https:///doi.org/10.1098/rspa.2010.0301
[48] Larry Stockmeyer. "Kompleksiteten ved omtrentlig optælling". I Proceedings of the Femtende Annual ACM Symposium on Theory of Computing. Side 118–126. STOC '83. Association for Computing Machinery (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 og Raúl García-Patrón. "Kvadratisk hastighedsstigning til simulering af Gaussisk bosonprøvetagning". PRX Quantum 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, et al. "Grænsen for kvantefordel i Gaussisk bosonsampling". Science Advances 8, eabl9236 (2022).
https:///doi.org/10.1126/sciadv.abl9236
[51] Herbert John Ryser. "Kombinatorisk matematik". Bind 14. American Mathematical Soc. (1963).
https://doi.org/10.5948/UPO9781614440147
[52] Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M Birchall, Ashley Montanaro og Anthony Laing. "Klassiske bosonsamplingsalgoritmer med overlegen ydeevne i forhold til eksperimenter på kort sigt". Nature Physics 13, 1153-1157 (2017).
https://doi.org/10.1038/nphys4270
[53] Peter Clifford og Raphaël Clifford. "Den klassiske kompleksitet af bosonsampling". Side 146–155. Selskab for Industriel og Anvendt Matematik. (2018).
https:///doi.org/10.1137/1.9781611975031.10
[54] Peter Clifford og Raphaël Clifford. "Hurtigere klassisk bosonsampling" (2020). arXiv:2005.04214.
arXiv: 2005.04214
[55] Philip J Hanlon, Richard P Stanley og John R Stembridge. "Nogle kombinatoriske aspekter af spektrene af normalfordelte tilfældige matricer". Contemporary Math 138, 151-174 (1992).
https:///doi.org/10.1090/conm/138/1199126
[56] D Maiwald og D Kraus. "Beregning af momenter af komplekse Wishart og komplekse inverse Wishart distribuerede matricer". IEE Proceedings – Radar, Sonar and Navigation 147, 162–168 (2000).
https://doi.org/10.1049/ip-rsn:20000493
[57] SM Barnett og PM Radmore. "Metoder i teoretisk kvanteoptik". Clarendon Press. (2002).
https:///doi.org/10.1093/acprof:oso/9780198563617.001.0001
[58] Nathaniel R Goodman. "Statistisk analyse baseret på en bestemt multivariat kompleks Gauss-fordeling (en introduktion)". The Annals of Mathematical Statistics 34, 152–177 (1963).
https:///doi.org/10.1214/aoms/1177704250
[59] Irina Shevtsova. "Om de absolutte konstanter i ulighederne af Berry-Esseen-typen". Doklady Mathematics 89, 378-381 (2014).
https:///doi.org/10.1134/S1064562414030338
[60] Alessio Serafini. "Kvantekontinuerlige variabler: En primer af teoretiske metoder". CRC Tryk. (2017).
https:///doi.org/10.1201/9781315118727
[61] Nicolás Quesada, Juan Miguel Arrazola og Nathan Killoran. "Gaussisk bosonsampling ved hjælp af tærskeldetektorer". Phys. Rev. A 98, 062322 (2018).
https:///doi.org/10.1103/PhysRevA.98.062322
[62] Nicolás Quesada og Juan Miguel Arrazola. "Nøjagtig simulering af Gaussisk bosonsampling i polynomisk rum og eksponentiel tid". Phys. Rev. Research 2, 023005 (2020).
https:///doi.org/10.1103/PhysRevResearch.2.023005
[63] Peter D. Drummond, Bogdan Opanchuk, A. Dellios og MD Reid. "Simulering af komplekse netværk i faserum: Gaussisk bosonsampling". Phys. Rev. A 105, 012427 (2022).
https:///doi.org/10.1103/PhysRevA.105.012427
[64] Alan Edelman. "Eigenværdier og betingelsesnumre for tilfældige matricer". SIAM tidsskrift om matrixanalyse og applikationer 9, 543-560 (1988).
https:///doi.org/10.1137/0609045
Citeret af
[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, og Anthony Laing, "Grænsen for kvantefordel i Gaussisk bosonsampling", Science Advances 8 4, eabl9236 (2022).
[2] Martin Houde og Nicolás Quesada, "Bølgestyrede kilder til konsekvent, enkelt-temporal-mode klemt lys: det gode, det dårlige og det grimme", arXiv: 2209.13491.
[3] Javier Martínez-Cifuentes, KM Fonseca-Romero og Nicolás Quesada, "Klassiske modeller er en bedre forklaring på Jiuzhang 1.0 Gaussian Boson Sampler end dens målrettede squeezed light model", arXiv: 2207.10058.
[4] Joseph T. Iosue, Adam Ehrenberg, Dominik Hangleiter, Abhinav Deshpande og Alexey V. Gorshkov, "Sidekurver og typisk sammenfiltring i lineær optik", arXiv: 2209.06838.
[5] Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski og Nicolás Quesada, "Effektiv prøveudtagning fra lavvandede Gaussiske kvanteoptiske kredsløb med lokale interaktioner", Fysisk anmeldelse A 105 5, 052412 (2022).
[6] Serge Massar, Fabrice Devaux og Eric Lantz, "Mulifoton-korrelationer mellem kvantebilleder", arXiv: 2211.08674.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-11-30 05:53:10). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2022-11-30 05:53:09).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
