1Inštitut za kvantno računalništvo, Univerza v Waterlooju, Kanada
2Oddelek za računalništvo in tehniko ter Oddelek za matematiko Univerze v Kaliforniji, San Diego, ZDA
3Instituto de Física, Universidade Federal Fluminense, Niterói, RJ, 24210-340, Brazilija
4Xanadu, Toronto, ON, M5G 2C8, Kanada
5Oddelek za inženirsko fiziko, École Polytechnique de Montréal, Montréal, QC, H3T 1JK, Kanada
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Vzorčenje Gaussovih bozonov je model fotonskega kvantnega računalništva, ki je pritegnil pozornost kot platforma za gradnjo kvantnih naprav, ki so sposobne opravljati naloge, ki so za klasične naprave nedosegljive. Zato obstaja veliko zanimanje z vidika teorije računalniške kompleksnosti za utrjevanje matematičnih temeljev za trdoto simulacije teh naprav. Pokažemo, da v skladu s standardnimi domnevami o antikoncentraciji in trajnem Gaussovem sistemu ni učinkovitega klasičnega algoritma za vzorčenje iz idealnih porazdelitev vzorčenja Gaussovih bozonov (tudi približno), razen če se polinomska hierarhija zruši. Dokaz trdote velja v režimu, kjer se število načinov kvadratno spreminja s številom fotonov, kar je nastavitev, za katero se je na splošno verjelo, da trdota drži, vendar kljub temu ni bilo dokončnega dokaza.
Bistvenega pomena za dokaz je nova metoda za programiranje naprave za vzorčenje Gaussovih bozonov, tako da so izhodne verjetnosti sorazmerne s permanenti podmatrik poljubne matrike. Ta tehnika je posplošitev Scattershot BosonSampling, ki jo imenujemo BipartiteGBS. Napredujemo tudi proti cilju dokazovanja trdote v režimu, kjer je manj kot kvadratno več modusov kot fotonov (tj. režim visokih trkov), tako da pokažemo, da zmožnost približevanja permanentov matrik s ponavljajočimi se vrsticami/stolpci daje sposobnost za aproksimacijo permanentov matrik brez ponovitev. Zmanjšanje zadostuje za dokaz, da je GBS trd v režimu stalnega trka.
[Vgrajeni vsebina]
[Vgrajeni vsebina]
► BibTeX podatki
► Reference
[1] Scott Aaronson and Alex Arkhipov. “The computational complexity of linear optics”. 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 in Philip Walther. "Eksperimentalno vzorčenje bozonov". 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 G. R. Smith, and Ian A. Walmsley. “Boson sampling on a photonic chip”. Science 339, 798–801 (2013).
https: / / doi.org/ 10.1126 / znanost.1231692
[4] Andrea Crespi, Roberto Osellame, Roberta Ramponi, Daniel J Brod, Ernesto F Galvao, Nicolo Spagnolo, Chiara Vitelli, Enrico Maiorino, Paolo Mataloni, and Fabio Sciarrino. “Integrated multimode interferometers with arbitrary designs for photonic boson sampling”. 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, and Andrew G. White. “Photonic boson sampling in a tunable circuit”. Science 339, 794–798 (2013).
https: / / doi.org/ 10.1126 / znanost.1231440
[6] Austin P Lund, Anthony Laing, Saleh Rahimi-Keshari, Terry Rudolph, Jeremy L O’Brien, and Timothy C Ralph. “Boson sampling from a Gaussian state”. 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, and Igor Jex. “Gaussian boson sampling”. 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, and Fabio Sciarrino. “Experimental 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, and Jian-Wei Pan. “High-efficiency multiphoton boson sampling”. 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, and Jian-Wei Pan. “Experimental Gaussian boson sampling”. 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, and Igor Jex. “Detailed study of Gaussian boson sampling”. 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 in Nathan Killoran. "Uporaba fotonskih kvantnih računalnikov v kratkem času: programska oprema in algoritmi". Kvantna znanost in tehnologija 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 in Y. Zhang. "Kvantna vezja z veliko fotoni na programabilnem nanofotoničnem čipu". Narava 591, 54–60 (2021).
https://doi.org/10.1038/s41586-021-03202-1
[14] Jianwei Wang, Fabio Sciarrino, Anthony Laing in Mark G. Thompson. “Integrirane fotonske kvantne tehnologije”. 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, and J.E. Sipe. “Scalable squeezed-light source for continuous-variable quantum sampling”. Phys. Rev. Applied 12, 064024 (2019).
https: / / doi.org/ 10.1103 / PhysRevApplied.12.064024
[16] Joonsuk Huh, Gian Giacomo Guerreschi, Borja Peropadre, Jarrod R. McClean, and Alán Aspuru-Guzik. “Boson sampling for molecular vibronic spectra”. Nature Photonics 9, 615–620 (2015).
https: / / doi.org/ 10.1038 / nphoton.2015.153
[17] Juan Miguel Arrazola and Thomas R. Bromley. “Using Gaussian boson sampling to find dense subgraphs”. Phys. Rev. Lett. 121, 030503 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.030503
[18] Leonardo Banchi, Mark Fingerhuth, Tomas Babej, Christopher Ing, and Juan Miguel Arrazola. “Molecular docking with Gaussian boson sampling”. Science Advances 6, eaax1950 (2020).
https: / / doi.org/ 10.1126 / sciadv.aax1950
[19] Soran Jahangiri, Juan Miguel Arrazola, Nicolás Quesada, and Nathan Killoran. “Point processes with Gaussian boson sampling”. Phys. Rev. E 101, 022134 (2020).
https: / / doi.org/ 10.1103 / PhysRevE.101.022134
[20] Maria Schuld, Kamil Brádler, Robert Israel, Daiqin Su, and Brajesh Gupt. “Measuring the similarity of graphs with a Gaussian 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, and Alain Delgado. “Quantum algorithm for simulating molecular vibrational excitations”. Physical Chemistry Chemical Physics 22, 25528–25537 (2020).
https:///doi.org/10.1039/D0CP03593A
[22] Leonardo Banchi, Nicolás Quesada, and Juan Miguel Arrazola. “Training Gaussian boson sampling distributions”. 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 in Jonathan Lavoie. "Kvantna računalniška prednost s programirljivim fotonskim procesorjem". Narava 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 in Jian-Wei Pan. "Kvantna računalniška prednost z uporabo fotonov". Znanost 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. “Phase-programmable Gaussian boson sampling using stimulated squeezed light”. 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 in Ish Dhand. "Kvantna računska prednost prek visokodimenzionalnega vzorčenja Gaussovih bozonov". Znanstveni napredek 8, eabi7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
[27] Raúl García-Patrón, Jelmer J Renema, and Valery Shchesnovich. “Simulating boson sampling in lossy architectures”. Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169
[28] Haoyu Qi, Daniel J. Brod, Nicolás Quesada, and Raúl García-Patrón. “Regimes of classical simulability for noisy Gaussian boson sampling”. Phys. Rev. Lett. 124, 100502 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.100502
[29] Michael Reck, Anton Zeilinger, Herbert J. Bernstein in Philip Bertani. "Eksperimentalna realizacija katerega koli diskretnega unitarnega operaterja". 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, and Ian A Walsmley. “Optimal design for universal multiport interferometers”. Optica 3, 1460–1465 (2016).
https: / / doi.org/ 10.1364 / OPTICA.3.001460
[31] Hubert de Guise, Olivia Di Matteo, and Luis L. Sánchez-Soto. “Simple factorization of unitary transformations”. Phys. Rev. A 97, 022328 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022328
[32] Bryn A Bell and Ian A Walmsley. “Further compactifying linear optical unitaries”. APL Photonics 6, 070804 (2021).
https: / / doi.org/ 10.1063 / 5.0053421
[33] Tiefeng Jiang. “How many entries of a typical orthogonal matrix can be approximated by independent normals?”. The Annals of Probability 34, 1497–1529 (2006).
https: / / doi.org/ 10.1214 / 009117906000000205
[34] Alexander I Barvinok. “Two algorithmic results for the traveling salesman problem”. Mathematics of Operations Research 21, 65–84 (1996).
https: / / doi.org/ 10.1287 / moor.21.1.65
[35] Daniel Grier and Luke Schaeffer. “New hardness results for the permanent using linear optics”. In 33rd Computational Complexity Conference (CCC 2018). Volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:29. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018).
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2018.19
[36] Scott Aaronson and Daniel J. Brod. “BosonSampling with lost photons”. 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 in Seth Lloyd. "Gaussova kvantna informacija". Rev. Mod. Phys. 84, 621–669 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[38] Eduardo R Caianiello. “On quantum field theory—I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs”. Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[39] Alexander Barvinok. “Combinatorics and complexity of partition functions”. Volume 276. Springer. (2016).
https://doi.org/10.1007/978-3-319-51829-9
[40] Andreas Björklund, Brajesh Gupt, and Nicolás Quesada. “A faster hafnian formula for complex matrices and its benchmarking on a supercomputer”. Journal of Experimental Algorithmics (JEA) 24, 11 (2019).
https: / / doi.org/ 10.1145 / 3325111
[41] L. Chakhmakhchyan and N. J. Cerf. “Boson sampling with Gaussian measurements”. Phys. Rev. A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
[42] Jianhong Shen. “On the singular values of Gaussian random matrices”. Linear Algebra and its Applications 326, 1–14 (2001).
https://doi.org/10.1016/S0024-3795(00)00322-0
[43] Uffe Haagerup and Steen Thorbjørnsen. “Random matrices with complex Gaussian entries”. Expositiones Mathematicae 21, 293–337 (2003).
https://doi.org/10.1016/S0723-0869(03)80036-1
[44] Brajesh Gupt, Josh Izaac, and Nicolás Quesada. “The Walrus: a library for the calculation of hafnians, Hermite polynomials and Gaussian boson sampling”. Journal of Open Source Software 4, 1705 (2019).
https: / / doi.org/ 10.21105 / joss.01705
[45] Alex Arkhipov and Greg Kuperberg. “The bosonic birthday paradox”. Geometry & Topology Monographs 18, 1–7 (2012).
https: / / doi.org/ 10.2140 / gtm.2012.18.1
[46] Antonia M Tulino and Sergio Verdú. “Random matrix theory and wireless communications”. Now Publishers Inc. (2004).
https: / / doi.org/ 10.1561 / 0100000001
[47] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy”. 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. “The complexity of approximate counting”. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. Page 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, and Raúl García-Patrón. “Quadratic speed-up for simulating Gaussian boson sampling”. 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. “The boundary for quantum advantage in Gaussian boson sampling”. Science Advances 8, eabl9236 (2022).
https:///doi.org/10.1126/sciadv.abl9236
[51] Herbert John Ryser. “Combinatorial mathematics”. Volume 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, and Anthony Laing. “Classical boson sampling algorithms with superior performance to near-term experiments”. Nature Physics 13, 1153–1157 (2017).
https: / / doi.org/ 10.1038 / nphys4270
[53] Peter Clifford and Raphaël Clifford. “The classical complexity of boson sampling”. Pages 146–155. Society for Industrial and Applied Mathematics. (2018).
https: / / doi.org/ 10.1137 / 1.9781611975031.10
[54] Peter Clifford and Raphaël Clifford. “Faster classical boson sampling” (2020). arXiv:2005.04214.
arXiv: 2005.04214
[55] Philip J Hanlon, Richard P Stanley, and John R Stembridge. “Some combinatorial aspects of the spectra of normally distributed random matrices”. Contemporary Math 138, 151–174 (1992).
https: / / doi.org/ 10.1090 / conm / 138/1199126
[56] D Maiwald and D Kraus. “Calculation of moments of complex Wishart and complex inverse Wishart distributed matrices”. IEE Proceedings – Radar, Sonar and Navigation 147, 162–168 (2000).
https:///doi.org/10.1049/ip-rsn:20000493
[57] S.M. Barnett and P.M. Radmore. “Methods in theoretical quantum optics”. Clarendon Press. (2002).
https: / / doi.org/ 10.1093 / acprof: oso / 9780198563617.001.0001
[58] Nathaniel R Goodman. “Statistical analysis based on a certain multivariate complex Gaussian distribution (an introduction)”. The Annals of Mathematical Statistics 34, 152–177 (1963).
https: / / doi.org/ 10.1214 / aoms / 1177704250
[59] Irina Shevtsova. “On the absolute constants in the Berry-Esseen-type inequalities”. Doklady Mathematics 89, 378–381 (2014).
https: / / doi.org/ 10.1134 / S1064562414030338
[60] Alessio Serafini. “Quantum continuous variables: A primer of theoretical methods”. CRC Press. (2017).
https: / / doi.org/ 10.1201 / 9781315118727
[61] Nicolás Quesada, Juan Miguel Arrazola, and Nathan Killoran. “Gaussian boson sampling using threshold detectors”. Phys. Rev. A 98, 062322 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.062322
[62] Nicolás Quesada and Juan Miguel Arrazola. “Exact simulation of Gaussian boson sampling in polynomial space and exponential time”. Phys. Rev. Research 2, 023005 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.023005
[63] Peter D. Drummond, Bogdan Opanchuk, A. Dellios, and M. D. Reid. “Simulating complex networks in phase space: Gaussian boson sampling”. Phys. Rev. A 105, 012427 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.012427
[64] Alan Edelman. “Eigenvalues and condition numbers of random matrices”. SIAM journal on matrix analysis and applications 9, 543–560 (1988).
https: / / doi.org/ 10.1137 / 0609045
Navedel
[1] Jacob F. F. 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, and Anthony Laing, “The boundary for quantum advantage in Gaussian boson sampling”, Znanstveni napredek 8 4, eabl9236 (2022).
[2] Martin Houde and Nicolás Quesada, “Waveguided sources of consistent, single-temporal-mode squeezed light: the good, the bad, and the ugly”, arXiv: 2209.13491.
[3] Javier Martínez-Cifuentes, K. M. Fonseca-Romero, and Nicolás Quesada, “Classical models are a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model”, arXiv: 2207.10058.
[4] Joseph T. Iosue, Adam Ehrenberg, Dominik Hangleiter, Abhinav Deshpande, and Alexey V. Gorshkov, “Page curves and typical entanglement in linear optics”, arXiv: 2209.06838.
[5] Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski, and Nicolás Quesada, “Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions”, Fizični pregled A 105 5, 052412 (2022).
[6] Serge Massar, Fabrice Devaux, and Eric Lantz, “Mulitphoton Correlations between Quantum Images”, arXiv: 2211.08674.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-11-30 05:53:10). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.
On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2022-11-30 05:53:09).
Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.
