The Complexity of Bipartite Gaussian Boson Sampling

Daniel Grier1,2, Daniel J. Brod3, Juan Miguel Arrazola4, Marcos Benicio de Andrade Alonso3, and Nicolás Quesada5

1Institute for Quantum Computing, University of Waterloo, Canada
2Department of Computer Science and Engineering and Department of Mathematics, University of California, San Diego, US
3Instituto de Física, Universidade Federal Fluminense, Niterói, RJ, 24210-340, Brazil
4Xanadu, Toronto, ON, M5G 2C8, Canada
5Department of Engineering Physics, École Polytechnique de Montréal, Montréal, QC, H3T 1JK, Canada

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof.
Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

► BibTeX data

► References

[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, and Philip Walther. ``Experimental boson sampling''. 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, and Nathan Killoran. ``Applications of near-term photonic quantum computers: software and algorithms''. Quantum Science and Technology 5, 034010 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8504

[13] J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Bromley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Quesada, A. Repingon, K. K. Sabapathy, M. Schuld, D. Su, J. Swinarton, A. Száva, K. Tan, P. Tan, V. D. Vaidya, Z. Vernon, Z. Zabaneh, and Y. Zhang. ``Quantum circuits with many photons on a programmable nanophotonic chip''. Nature 591, 54–60 (2021).
https:/​/​doi.org/​10.1038/​s41586-021-03202-1

[14] Jianwei Wang, Fabio Sciarrino, Anthony Laing, and Mark G. Thompson. ``Integrated photonic quantum technologies''. 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 F. F. 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, and Jonathan Lavoie. ``Quantum computational advantage with a programmable photonic 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, and Jian-Wei Pan. ``Quantum computational advantage using photons''. 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, and Philip Bertani. ``Experimental realization of any discrete unitary operator''. 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, and Seth Lloyd. ``Gaussian quantum information''. 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

Cited by

[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] Jian-Wei Pan, Dialogues Between Physics and Mathematics 147 (2022) ISBN:978-3-031-17522-0.

[3] Joseph T. Iosue, Adam Ehrenberg, Dominik Hangleiter, Abhinav Deshpande, and Alexey V. Gorshkov, "Page curves and typical entanglement in linear optics", arXiv:2209.06838, (2022).

[4] 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, (2022).

[5] 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, (2022).

[6] Yanic Cardin and Nicolás Quesada, "Photon-number moments and cumulants of Gaussian states", arXiv:2212.06067, (2022).

[7] 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", Physical Review A 105 5, 052412 (2022).

[8] Serge Massar, Fabrice Devaux, and Eric Lantz, "Mulitphoton Correlations between Quantum Images", arXiv:2211.08674, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-02-07 14:51:21) and SAO/NASA ADS (last updated successfully 2023-02-07 14:51:22). The list may be incomplete as not all publishers provide suitable and complete citation data.