Proof of hiding conjecture in Gaussian boson sampling

Laura Shou; Sarah H. Miller; Victor Galitski

doi:10.22331/q-2026-10-27-2248

Proof of hiding conjecture in Gaussian boson sampling

Laura Shou¹, Sarah H. Miller², and Victor Galitski¹

¹Joint Quantum Institute, Department of Physics, University of Maryland, College Park, Maryland 20742, USA
²Applied Research Laboratory for Intelligence and Security, University of Maryland, College Park, Maryland 20742, USA

Published:	2026-10-27, volume 10, page 2248
Editor:	Ulysse Chabaud
Eprint:	arXiv:2508.00983v3
Doi:	https://doi.org/10.22331/q-2026-10-27-2248
Citation:	Quantum 10, 2248 (2026).

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

Abstract

Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps in the argument for classical hardness of GBS is the so-called “hiding conjecture'', which asserts that one can “hide'' a complex Gaussian matrix as a submatrix of the symmetric product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with all input modes squeezed, which is a setup that has recently been realized experimentally [10]. In this setting, the hiding conjecture states that a $o(\sqrt{M})\times o(\sqrt{M})$ submatrix of an $M\times M$ circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as $M\to\infty$. This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with the maximum number of squeezed input modes on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)] [1].

► BibTeX data

@article{Shou2026proofofhiding,
  doi = {10.22331/q-2026-10-27-2248},
  url = {https://doi.org/10.22331/q-2026-10-27-2248},
  title = {Proof of hiding conjecture in {G}aussian boson sampling},
  author = {Shou, Laura and Miller, Sarah H. and Galitski, Victor},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2248},
  month = oct,
  year = {2026}
}

► References

[1] Scott Aaronson and Alex Arkhipov. ``The computational complexity of linear optics''. Theory Comput. 9, 143–252 (2013).
https://doi.org/10.4086/toc.2013.v009a004

[2] A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O'Brien, and T. C. Ralph. ``Boson sampling from a Gaussian state''. Phys. Rev. Lett. 113, 100502 (2014).
https://doi.org/10.1103/PhysRevLett.113.100502

[3] Saleh Rahimi-Keshari, Austin P. Lund, and Timothy C. Ralph. ``What can quantum optics say about computational complexity theory?''. Phys. Rev. Lett. 114, 060501 (2015).
https://doi.org/10.1103/PhysRevLett.114.060501

[4] 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

[5] 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

[6] 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''. Sci. Adv. 8, eabi7894 (2022).
https://doi.org/10.1126/sciadv.abi7894

[7] Dominik Hangleiter and Jens Eisert. ``Computational advantage of quantum random sampling''. Rev. Mod. Phys. 95, 035001 (2023).
https://doi.org/10.1103/RevModPhys.95.035001

[8] 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

[9] 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, 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, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan. ``Phase-programmable Gaussian boson sampling using stimulated squeezed light''. Phys. Rev. Lett. 127, 180502 (2021).
https://doi.org/10.1103/PhysRevLett.127.180502

[10] 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

[11] Yu-Hao Deng, Yi-Chao Gu, Hua-Liang Liu, Si-Qiu Gong, Hao Su, Zhi-Jiong Zhang, Hao-Yang Tang, Meng-Hao Jia, Jia-Min Xu, Ming-Cheng Chen, Jian Qin, Li-Chao Peng, Jiarong Yan, Yi Hu, Jia Huang, Hao Li, Yuxuan Li, Yaojian Chen, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Li Li, Han-Sen Zhong, Hui Wang, Nai-Le Liu, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan. ``Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage''. Phys. Rev. Lett. 131, 150601 (2023).
https://doi.org/10.1103/PhysRevLett.131.150601

[12] Hua-Liang Liu, Hao Su, Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Hao-Yang Tang, Meng-Hao Jia, Qian Wei, Yu-Kun Song, Dong-Zhou Wang, Ming-Yang Zheng, Fa-Xi Chen, Li-Bo Li, Si-Yu Ren, Xue-Zhi Zhu, Mei-Hong Wang, Yao-Jian Chen, Yan-Fei Liu, Long-Sheng Song, Peng-Yu Yang, Jun-Shi Chen, Hong An, Lei Zhang, Lin Gan, Guang-wen Yang, Jia-Min Xu, Yu-Ming He, Hui Wang, Han-Sen Zhong, Ming-Cheng Chen, Xiao Jiang, Li Li, Nai-Le Liu, Xiao-Long Su, Qiang Zhang, Chao-Yang Lu, and Jian-Wei Pan. ``Gaussian boson sampling with 1,024 squeezed states in 8,176 modes''. Nature 653, 687–692 (2026).
https://doi.org/10.1038/s41586-026-10523-6

[13] L.G. Valiant. ``The complexity of computing the permanent''. Theoret. Comput. Sci. 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6

[14] Scott Aaronson. ``A linear-optical proof that the permanent is #P-hard''. Proc. R. Soc. A 467, 3393–3405 (2011).
https://doi.org/10.1098/rspa.2011.0232

[15] Daniel Grier, Daniel J Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, and Nicolás Quesada. ``The complexity of bipartite Gaussian boson sampling''. Quantum 6, 863 (2022).
https://doi.org/10.22331/q-2022-11-28-863

[16] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernández, and Michał Oszmaniec. ``Complexity-theoretic foundations of BosonSampling with a linear number of modes''. Phys. Rev. X 16, 021059 (2026).
https://doi.org/10.1103/xc7b-sjm5

[17] Larry Stockmeyer. ``On approximation algorithms for #P''. SIAM J. Comput. 14, 849–861 (1985).
https://doi.org/10.1137/0214060

[18] Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande, Dominik Hangleiter, and Alexey V. Gorshkov. ``Transition of anticoncentration in Gaussian boson sampling''. Phys. Rev. Lett. 134, 140601 (2025).
https://doi.org/10.1103/PhysRevLett.134.140601

[19] Miklós Z. Rácz and Jacob Richey. ``A smooth transition from Wishart to GOE''. J. Theoret. Probab. 32, 898–906 (2019).
https://doi.org/10.1007/s10959-018-0808-2

[20] Adam Ehrenberg, Joseph T. Iosue, Abhinav Deshpande, Dominik Hangleiter, and Alexey V. Gorshkov. ``Second moment of hafnians in Gaussian boson sampling''. Phys. Rev. A 111, 042412 (2025).
https://doi.org/10.1103/PhysRevA.111.042412

[21] Freeman J. Dyson. ``The threefold way. Algebraic structure of symmetry groups and ensembles in quantum mechanics''. J. Math. Phys. 3, 1199–1215 (1962).
https://doi.org/10.1063/1.1703863

[22] W. A. Friedman and P. A. Mello. ``Marginal distribution of an arbitrary square submatrix of the $S$-matrix for Dyson's measure''. J. Phys. A 18, 425–436 (1985).
https://doi.org/10.1088/0305-4470/18/3/018

[23] Benoı̂t Collins and Michael Stolz. ``Borel theorems for random matrices from the classical compact symmetric spaces''. Ann. Probab. 36, 876–895 (2008).
https://doi.org/10.1214/07-AOP341

[24] Tiefeng Jiang. ``The entries of circular orthogonal ensembles''. J. Math. Phys. 50, 063302 (2009).
https://doi.org/10.1063/1.3152217

[25] Tiefeng Jiang. ``How many entries of a typical orthogonal matrix can be approximated by independent normals?''. Ann. Probab. 34, 1497–1529 (2006).
https://doi.org/10.1214/009117906000000205

[26] Tiefeng Jiang and Yutao Ma. ``Distances between random orthogonal matrices and independent normals''. Trans. Amer. Math. Soc. 372, 1509–1553 (2019).
https://doi.org/10.1090/tran/7470

[27] L. K. Hua. ``Harmonic analysis of functions of several complex variables in the classical domains''. American Mathematical Society, Providence, RI. (1963).
https://doi.org/10.1090/mmono/006

[28] Morris L. Eaton. ``Multivariate statistics: A vector space approach''. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York. (1983).
https://doi.org/10.1214/lnms/1196285102

[29] C. W. J. Beenakker. ``Random-matrix theory of quantum transport''. Rev. Mod. Phys. 69, 731–808 (1997).
https://doi.org/10.1103/RevModPhys.69.731

[30] Peter J. Forrester. ``Log-gases and random matrices''. Volume 34 of London Mathematical Society Monographs Series. Princeton University Press, Princeton, NJ. (2010).
https://doi.org/10.1515/9781400835416

[31] Benoı̂t Collins. ``Intégrales matricielles et probabilités non-commutatives''. PhD thesis. Université Pierre et Marie Curie - Paris VI. (2003). url: https://theses.hal.science/tel-00004306.
https://theses.hal.science/tel-00004306

[32] Tiefeng Jiang. ``Approximation of Haar distributed matrices and limiting distributions of eigenvalues of Jacobi ensembles''. Probab. Theory Related Fields 144, 221–246 (2009).
https://doi.org/10.1007/s00440-008-0146-x

[33] Persi W. Diaconis, Morris L. Eaton, and Steffen L. Lauritzen. ``Finite de Finetti theorems in linear models and multivariate analysis''. Scand. J. Statist. 19, 289–315 (1992). url: https://www.jstor.org/stable/4616249.
https://www.jstor.org/stable/4616249

[34] Morris L. Eaton. ``Group invariance applications in statistics''. Volume 1 of NSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA; American Statistical Association, Alexandria, VA. (1989).

[35] Elizabeth S. Meckes. ``The random matrix theory of the classical compact groups''. Volume 218 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge. (2019).
https://doi.org/10.1017/9781108303453

[36] Persi Diaconis and David Freedman. ``A dozen de Finetti-style results in search of a theory''. Ann. Inst. H. Poincaré Probab. Statist. 23, 397–423 (1987). url: https://www.numdam.org/item/AIHPB_1987__23_S2_397_0/.
https://www.numdam.org/item/AIHPB_1987__23_S2_397_0/

[37] Kathryn Stewart. ``Total variation approximation of random orthogonal matrices by Gaussian matrices''. J. Theoret. Probab. 33, 1111–1143 (2020).
https://doi.org/10.1007/s10959-019-00900-5

[38] Benoı̂t Collins. ``Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability''. Int. Math. Res. Not. 2003, 953–982 (2003).
https://doi.org/10.1155/S107379280320917X

[39] Benoı̂t Collins and Piotr Śniady. ``Integration with respect to the Haar measure on unitary, orthogonal and symplectic group''. Comm. Math. Phys. 264, 773–795 (2006).
https://doi.org/10.1007/s00220-006-1554-3

[40] M. S. Pinsker. ``Information and information stability of random variables and processes''. Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam. (1964).

[41] Roland Speicher. ``Lectures on random matrices''. EMS Series of Lectures in Mathematics. EMS Press, Berlin. (2024).
https://doi.org/10.4171/elm/35

[42] Martin J. Wainwright. ``High-dimensional statistics''. Volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. (2019).
https://doi.org/10.1017/9781108627771

[43] Sourav Chatterjee and Elizabeth Meckes. ``Multivariate normal approximation using exchangeable pairs''. ALEA Lat. Am. J. Probab. Math. Stat. 4, 257–283 (2008). url: https://alea.impa.br/articles/v4/04-13.pdf.
https://alea.impa.br/articles/v4/04-13.pdf

[44] Francesco Mezzadri. ``How to generate random matrices from the classical compact groups''. Notices Amer. Math. Soc. 54, 592–604 (2007). url: https://www.ams.org/journals/notices/200705/fea-mezzadri-web.pdf.
https://www.ams.org/journals/notices/200705/fea-mezzadri-web.pdf

[45] Torgny Lindvall. ``Lectures on the coupling method''. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York. (1992).

[46] Erhan Çinlar. ``Probability and stochastics''. Volume 261 of Graduate Texts in Mathematics. Springer, New York. (2011).
https://doi.org/10.1007/978-0-387-87859-1

[47] Laura Shou, Alexey V. Gorshkov, Victor Galitski, and Sarah Miller. ``Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes''. arXiv preprint arXiv:2608.19314 (2026).
https://doi.org/10.48550/arXiv.2608.19314
arXiv:2608.19314

[48] Karol Życzkowski and Hans-Jürgen Sommers. ``Truncations of random unitary matrices''. J. Phys. A 33, 2045–2057 (2000).
https://doi.org/10.1088/0305-4470/33/10/307

[49] Atle Selberg. ``Remarks on a multiple integral''. Norsk Mat. Tidsskr. 26, 71–78 (1944).

Cited by

[1] Hongru Zhao, "Uniform Hiding and Two Routes to Relative Accuracy in Gaussian Boson Sampling", arXiv:2609.01008, (2026).

[2] Byeongseon Go, Changhun Oh, and Hyunseok Jeong, "Sufficient conditions for hardness of lossy Gaussian boson sampling", arXiv:2511.07853, (2025).

[3] Michael Stefszky, Kai-Hong Luo, Jan-Lucas Eickmann, Simone Atzeni, Florian Lütkewitte, Cheeranjiv Pandey, Fabian Schlue, Jonas Lammers, Mikhail Roiz, Timon Schapeler, Laura Ares, Milad Yahyapour, Alexander Kastner, Joschua Martinek, Michael Mittermair, Carlos Sevilla-Gutiérrez, Marius Leyendecker, Oskar Kohout, Dmitriy Mitin, Ronald Holzwarth, Jan Sperling, Tim Bartley, Fabian Steinlechner, Benjamin Brecht, and Christine Silberhorn, "Benchmarking Gaussian and non-Gaussian input states with a hybrid sampling platform", arXiv:2512.08433, (2025).

[4] Laura Shou, Adam Ehrenberg, Yu-Xin Wang, Joseph T. Iosue, and Alexey V. Gorshkov, "Anticoncentration and entanglement in Gaussian boson sampling", arXiv:2609.01241, (2026).

[5] Hongru Zhao, "Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration", arXiv:2608.17065, (2026).

[6] Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, and Penghui Yao, "Classical Algorithms for Function Computation in Gaussian Boson Sampling", arXiv:2609.38882, (2026).

[7] Priyanshu Pant, "Anticoncentration of Complex Gaussian Hafnians", arXiv:2609.35019, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-10-28 01:40:40). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-10-28 01:40:36).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.