Proof of hiding conjecture in Gaussian boson sampling

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 [Madsen et al., Nature 606, 75 (2022)]. 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)].

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Mathematical Physics (math-ph)

arXiv:2508.00983 [quant-ph]

(or arXiv:2508.00983v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2508.00983 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.