1Institute for Quantum Computing, University of Waterloo, Kanada
2Számítástechnikai és Mérnöki Tanszék, valamint Matematikai Tanszék, Kaliforniai Egyetem, San Diego, USA
3Instituto de Física, Universidade Federal Fluminense, Niterói, RJ, 24210-340, Brazília
4Xanadu, Toronto, ON, M5G 2C8, Kanada
5Tanszék Mérnöki Fizika, École Polytechnique de Montréal, Montréal, QC, H3T 1JK, Kanada
Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.
Absztrakt
A Gauss-bozon mintavétel a fotonikus kvantumszámítás egy olyan modellje, amely a klasszikus eszközök számára elérhetetlen feladatok elvégzésére alkalmas kvantumeszközök építésének platformjaként keltette fel a figyelmet. Ezért a számítási komplexitás elmélete szempontjából jelentős érdeklődés mutatkozik ezen eszközök szimulációjának keménységének matematikai alapjainak megszilárdítása iránt. Megmutatjuk, hogy a standard Anti-koncentráció és a Gauss-permanens sejtések alapján nincs hatékony klasszikus algoritmus az ideális Gauss-bozon mintavételezési eloszlásokból való mintavételhez (még hozzávetőlegesen is), hacsak a polinomi hierarchia össze nem omlik. A keménység bizonyítása abban a rendszerben érvényes, ahol a módusok száma négyzetesen skálázódik a fotonok számával, egy olyan beállításban, amelyben a keménységet széles körben tartották, de ennek ellenére nem volt végleges bizonyíték.
A bizonyítás szempontjából kulcsfontosságú egy új módszer a Gauss-bozon mintavevő eszköz programozására úgy, hogy a kimeneti valószínűségek arányosak egy tetszőleges mátrix részmátrixainak állandóival. Ez a technika a Scattershot BosonSampling általánosítása, amelyet BipartiteGBS-nek nevezünk. Előrehaladást értünk el azon a cél felé is, hogy bizonyítsuk a keménységet abban a rezsimben, ahol négyzetesen kevesebb mód van, mint a fotonok (azaz a nagy ütközési rezsim), megmutatva, hogy a mátrixok állandóinak közelítésének képessége ismétlődő sorokkal/oszlopokkal megadja a képességet. az ismétlődés nélküli mátrixok állandóinak közelítése. A csökkentés elegendő annak bizonyítására, hogy a GBS kemény az állandó ütközési rendszerben.
[Beágyazott tartalmat]
[Beágyazott tartalmat]
► BibTeX adatok
► Referenciák
[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 és Philip Walther. „Kísérleti bozon-mintavétel”. 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/science.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/science.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 és Nathan Killoran. „Közeltávú fotonikus kvantumszámítógépek alkalmazásai: szoftverek és algoritmusok”. 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 és Y. Zhang. „Kvantumáramkörök sok fotonnal egy programozható nanofotonikus chipen”. Nature 591, 54–60 (2021).
https://doi.org/10.1038/s41586-021-03202-1
[14] Jianwei Wang, Fabio Sciarrino, Anthony Laing és Mark G. Thompson. „Integrált fotonikus kvantumtechnológiák”. 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 és Jonathan Lavoie. „Kvantumszámítási előny programozható fotonikus processzorral”. 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 és Jian-Wei Pan. „Kvantumszámítási előny fotonok használatával”. 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. “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, and Ish Dhand. “Quantum computational advantage via high-dimensional Gaussian boson sampling”. Science Advances 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 és Philip Bertani. „Bármely diszkrét egységes operátor kísérleti megvalósítása”. 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-Patron, Nicolas J. Cerf, Timothy C. Ralph, Jeffrey H. Shapiro és Seth Lloyd. „Gauss kvantuminformáció”. 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
Idézi
[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”, Science Advances 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”, Fizikai áttekintés A 105 5, 052412 (2022).
[6] Serge Massar, Fabrice Devaux, and Eric Lantz, “Mulitphoton Correlations between Quantum Images”, arXiv: 2211.08674.
A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2022-11-30 05:53:10). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.
On Crossref által idézett szolgáltatás művekre hivatkozó adat nem található (utolsó próbálkozás 2022-11-30 05:53:09).
Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.
