Proof of hiding conjecture in Gaussian boson sampling

Technical Summary: Proof of the Hiding Conjecture in Gaussian Boson Sampling

1. Problem Statement

Gaussian Boson Sampling (GBS) is a leading candidate for demonstrating quantum computational advantage. The argument for the classical hardness of simulating GBS relies on two main components: the conjectured average-case hardness of approximating the hafnian of a matrix, and the hiding conjecture.

The hiding conjecture asserts that a complex Gaussian matrix (specifically one with independent entries) can be "hidden" as a submatrix within the symmetric product of a Haar-random unitary matrix, such that the two distributions are indistinguishable in total variation (TV) distance. This property is crucial because it allows one to embed a specific hard-to-compute matrix $Z$ into the GBS output distribution without an adversary (or a classical simulator) being able to identify the location of $Z$ to corrupt the probability estimate.

While the hiding property for standard (Fock) boson sampling was established for sparse regimes, the regime relevant to recent large-scale GBS experiments—where all $M$ input modes are squeezed ($K=M$)—remained unproven. In this regime, the relevant submatrix is an $N \times M$ rectangular block of a Haar unitary, which is known not to look like a Gaussian matrix in TV distance due to row normalization constraints. The open question was whether the symmetric product of this non-Gaussian submatrix ($U_{N,M}U_{N,M}^T$) nonetheless converges to a complex symmetric Gaussian matrix in TV distance.

2. Methodology

The authors provide a rigorous proof for the case where all input modes are squeezed ($K=M$). The core of the methodology involves:

• Random Matrix Theory Formulation: The problem is mapped to showing that the upper-left $N \times N$ submatrix $A$ of an $M \times M$ Circular Orthogonal Ensemble (COE) random matrix (distributed as $UU^T$ where $U$ is Haar-random) converges to a complex symmetric Gaussian matrix $G \sim \mathcal{G}^{\text{sym}}_N$ when scaled by $\sqrt{M}$.
• Total Variation Distance via KL Divergence: Instead of direct coupling, the authors bound the TV distance using Pinsker's inequality, which relates TV distance to the Kullback-Leibler (KL) divergence between the two distributions.
• Density Analysis:
  • The probability density function (PDF) of the COE submatrix is derived from existing literature (Hua, 1963; Kieburg et al., 2013), involving a determinant term $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$.
  • The PDF of the target Gaussian matrix is the standard complex symmetric Gaussian.
• Handling Normalization Constants: A key technical innovation is avoiding the explicit calculation of the complex normalization constant for the COE density. Instead, the authors introduce a scaling factor $\zeta$ and prove that $\zeta \to 1$ as $M \to \infty$ using bounds on the singular values of the matrices. This allows them to bypass the difficult asymptotic expansion of the normalization constant while maintaining the validity of the convergence proof.
• Moment Bounds: The proof utilizes Weingarten calculus to compute the moments of the singular values (eigenvalues of $A^\dagger A$) and employs concentration inequalities (subgaussian concentration) to bound the probability of large eigenvalues, ensuring the Taylor expansion of the log-density terms remains valid.

3. Key Contributions and Results

Theorem 1.1 / Theorem 1.2 (Main Result):
The authors prove the hiding conjecture for GBS with all input modes squeezed ($K=M$). Specifically, they show that for $N = o(\sqrt{M})$, the total variation distance between the scaled COE submatrix $\sqrt{M}A$ and the complex symmetric Gaussian matrix $G$ vanishes as $M \to \infty$:
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
This establishes that the symmetric product $U_{N,M}U_{N,M}^T$ is well-approximated by a complex symmetric Gaussian matrix in the experimentally relevant regime.

Corollary 1.1:
The authors demonstrate that the complex symmetric Gaussian matrix $G$ (with independent entries) and the symmetric product of rectangular Gaussian matrices $GG^T$ are close in the entrywise maximum norm (and thus in TV distance for sufficiently small $N$). This implies that the hardness of approximating $\text{Haf}(G)$ is essentially equivalent to approximating $\text{Haf}(GG^T)$ in the relevant regime.

Theorem 1.3 (Multiplicative Estimate):
The paper provides a multiplicative bound on the density functions: $f(Z) \leq (1 + O(N^3/M))g(Z)$. This result is necessary for the "instance generating" method used in hardness proofs, allowing the generation of a random unitary containing a specific Gaussian matrix as a hidden submatrix.

Theorem 1.5 & 1.6 (Sparse Regime Extension):
The paper extends the hiding property to the sparse regime ($NK = o(M)$), confirming that the hiding conjecture holds for $K < M$ in this regime and improving the known bounds for Fock boson sampling to the maximal size $N = o(\sqrt{M})$.

4. Significance and Claims

The paper claims to provide the first rigorous proof of the hiding property for Gaussian boson sampling in the experimentally relevant regime where the number of squeezed modes $K$ is proportional to the total number of modes $M$ (specifically $K=M$).

• Hardness Argument: By proving the hiding conjecture, the authors place the argument for the classical hardness of simulating GBS with maximum squeezed input modes on a "comparable level" to the hardness argument for conventional Fock boson sampling (Aaronson and Arkhipov, 2013).
• Experimental Relevance: The result directly supports the complexity-theoretic justification for recent large-scale GBS experiments (e.g., Madsen et al., Nature 2022) that utilize fully squeezed input states.
• Theoretical Nuance: The authors emphasize that the proof relies on the distribution of the symmetric product of the submatrix, not the submatrix itself. The submatrix $U_{N,M}$ is far from Gaussian in TV distance, but its symmetric product $U_{N,M}U_{N,M}^T$ converges to a Gaussian matrix. This distinction is critical, as previous attempts to derive GBS hardness from Fock boson sampling hiding properties failed in this dense regime.

The paper concludes by noting that while the $K=M$ case is resolved, the hiding conjecture for intermediate cases ($K=cM$ with $c<1$) remains open in this specific work (though the authors note it has been resolved in subsequent follow-up work [47]). The work strictly adheres to the collision-free regime ($N \ll M$) and relies on standard complexity-theoretic conjectures regarding the average-case hardness of hafnian approximation.