The hiding conjecture for Gaussian boson sampling

Let UNKU_{NK} be the top-left N×KN\times K submatrix of an M×MM\times M Haar-random unitary matrix. Let Z=ZN,KZ=Z_{N,K} be a random matrix distributed according to either GNsym\mathcal{G}_N^\mathrm{sym}, the ensemble of symmetric N×NN\times N matrices with independent entries modulo symmetry, diagonal entries distributed as CN(0,2)\mathcal{CN}(0,2), and off-diagonal entries as CN(0,1)\mathcal{CN}(0,1), or GGNKT\mathcal{G}\mathcal{G}^T_{NK}, the ensemble of matrices GGTGG^T for an N×KN\times K matrix GG with independent CN(0,1/K)\mathcal{CN}(0,1/\sqrt{K}) entries. Here dTVd_{\mathrm{TV}} denotes total variation distance. Hiding conjecture for Gaussian boson sampling. For NKMN\leq K\leq M and either distribution of ZZ, there exist polynomials pp and rr such that, for every δ>0\delta>0 and Mp(N)/r(δ)M\geq p(N)/r(\delta),

dTV(MK1/2UNKUNKT,Z)=O(δ).d_{\mathrm{TV}}\left(MK^{-1/2}U_{NK}U_{NK}^T,Z\right)=O(\delta).

This asserts that the relevant submatrix of a Haar unitary product can be hidden in total variation distance as a complex-Gaussian matrix, which is needed to transfer average-case hafnian hardness to approximate Gaussian boson sampling. The paper presents this formulation as adapted from an earlier conjecture and proves it for the maximal-squeezing regime, while the general statement remains the conjectural framework.

Sources & referencesView supporting material

Primary source

Laura Shou, Sarah H. Miller and Victor Galitski, “Proof of Hiding Conjecture in Gaussian Boson Sampling”, arXiv:2508.00983 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.