MathDB

The hiding conjecture for Gaussian boson sampling

About 1 year old · traced to

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 N≤K≤MN\leq K\leq M and either distribution of ZZ, there exist polynomials pp and rr such that, for every δ>0\delta>0 and M≥p(N)/r(δ)M\geq p(N)/r(\delta),

dTV(MK−1/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.

References

Primary source

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

gaussian-boson-samplingquantum-complexityrandom-matrices
Posted

Progress summary

Refreshed
Claimed solved

A new August 2026 preprint claims to prove the conjecture for any number of squeezed inputs, but the claim has not been independently verified.

The conjecture asserts that a matrix formed from a Haar-random optical transformation is statistically close to a Gaussian comparison matrix for N≤K≤MN\leq K\leq M. This approximation is a key ingredient in transferring average-case hardness to Gaussian boson sampling.

Known results

  • Maximal squeezing, K=MK=M: the Gaussian approximation was proved for N=o(M)N=o(\sqrt{M}), with error O(N/M)O(N/\sqrt{M}).
  • Sparse-squeezer regimes, including NK=o(M)NK=o(M), were established in earlier work, but these cases did not cover the full conjecture.
  • A related comparison with GGT/KGG^{T}/\sqrt{K} was known only in restricted parameter ranges.

August 21, 2026 arbitrary-input proof claim

Laura Shou, Alexey V. Gorshkov, Victor Galitski, and Sarah H. Miller claim a proof for arbitrary squeezed-input number. Their preprint states dTV(MK−1/2UNKUNKT,G)=O(N/K)d_{\mathrm{TV}}(MK^{-1/2}U_{NK}U_{NK}^{T},\mathbf{G})=O(N/\sqrt{K}) and combines this with earlier sparse-regime results to claim the full range; it also replaces a failing density-based hardness-reduction step with approximate instance generation. This remains an unverified preprint claim.

Current status (as of August 2026): The maximal-squeezing and previously known sparse regimes are established, while the claimed full arbitrary-input result remains unverified.

Sources

Solutions 0

No solutions have been posted yet.