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 [10]. In this setting, the hiding conjecture states that a o(√M)× o(√M) submatrix of an M× M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M→∞. 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].
Related
- Uniform Hiding and Two Routes to Relative Accuracy in Gaussian Boson Sampling
- Log-depth entanglement transition in hypercube Gaussian boson sampling
- Phase-noise induced many-body interference suppression in Gaussian Boson Sampling
- Anticoncentration and entanglement in Gaussian boson sampling
- Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
BibTeX
@article{shou2026proof,
title = {{Proof of hiding conjecture in Gaussian boson sampling}},
author = {Laura Shou and Sarah H. Miller and Victor Galitski},
journal = {Quantum},
year = {2026},
month = oct,
doi = {10.22331/q-2026-10-27-2248},
url = {https://quantum-journal.org/papers/q-2026-10-27-2248/},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Proof of hiding conjecture in Gaussian boson sampling
AU - Laura Shou
AU - Sarah H. Miller
AU - Victor Galitski
PY - 2026
DA - 2026/10/27
JO - Quantum
DO - 10.22331/q-2026-10-27-2248
UR - https://quantum-journal.org/papers/q-2026-10-27-2248/
AB - 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(√M)× o(√M) submatrix of an M× M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M→∞. 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].
SN - 2521-327X
ER -