Boson sampling beyond the dilute regime: second moments and anti-concentration

1. Problem Statement

Boson sampling is a leading candidate for demonstrating quantum advantage in photonic systems. However, a complete characterization of its output statistics remains incomplete, particularly outside the dilute regime (where the number of modes $m$ scales quadratically or faster with the number of photons $n$, i.e., $m = \Omega(n^2)$).

In the saturated regime (where $m = \Theta(n)$ or more generally sub-quadratic), photon collisions and bunching become significant. In this regime:

• The "hiding property" (which allows approximating submatrices of random unitaries as independent Gaussian matrices) breaks down.
• Existing techniques for analyzing output statistics and proving computational hardness fail.
• Anti-concentration (the property that output probabilities are not exponentially small for a non-negligible fraction of outcomes) remains poorly understood. This property is crucial for bridging the gap between average-case hardness conjectures and rigorous complexity-theoretic proofs.

The paper addresses the gap in understanding second moments of output distributions and establishing anti-concentration in these experimentally relevant, collision-dominated regimes.

2. Methodology

The authors develop a novel representation-theoretic framework for passive linear optics, moving away from random matrix theory and the hiding property.

A. Representation-Theoretic Framework

• Operator Space Decomposition: They analyze the space $\mathcal{W}$ of particle-number-preserving bosonic operators. This space is decomposed into fixed photon-number sectors $W_n$.
• $U(m)$ Action: The adjoint action of the unitary group $U(m)$ (representing linear interferometers) on $W_n$ is shown to decompose into a direct sum of inequivalent, multiplicity-free irreducible representations (irreps) labeled by an index $k$ ($0 \le k \le n$).
• $\mathfrak{sl}_2(\mathbb{C})$ Structure: The authors identify an additional symmetry generated by raising ($R$) and lowering ($L$) maps that connect different photon-number sectors. These maps, along with their commutator $H$, generate an $\mathfrak{sl}_2(\mathbb{C})$ Lie algebra action.
• Howe Duality: The commuting actions of $U(m)$ and $\mathfrak{sl}_2(\mathbb{C})$ form a Howe duality. This organizes the operator space into a "ladder" of irreducible components. Specifically, irreps with the same label $k$ appearing in different sectors are connected via the raising map $R$, starting from a primitive component (the kernel of $L$) in the lowest sector.

B. Recursive Projection and Second Moments

• Iterative Projection: Instead of using computationally expensive Clebsch-Gordan coefficients, the authors derive a recursive method to project operators onto specific irreducible components using the $L$ and $R$ maps.
• Closed-Form Second Moments: They derive a closed-form expression for the second moment of expectation values of particle-number-preserving observables averaged over Haar-random interferometers. This expression depends on the Hilbert-Schmidt norms of the projections of the state and observable onto the irreducible components.
• Norm Calculation: They provide a recursive formula to compute these projection norms analytically, avoiding explicit basis construction.

3. Key Contributions

1. General Second Moment Formula: A derivation of closed-form expressions for the second moments of generic particle-number-preserving bosonic observables, valid for any system size and regime (dilute or saturated).
2. Anti-Concentration Proof: A rigorous proof of the anti-concentration conjecture for Boson sampling in the saturated regime (linear scaling $m = cn$), where photon collisions are prevalent.
3. Normalized Average Collision Probability ($P_2$): The derivation of a compact, closed-form expression for the normalized average outcome collision probability, a key metric for anti-concentration and linear cross-entropy benchmarking.
4. Asymptotic Analysis: A detailed analysis of the asymptotic scaling of $P_2(m, n)$ across different regimes ($m \sim n^\beta$).

4. Key Results

A. Second Moment Expression

For a particle-number-preserving observable $O$ and state $\rho$ on $n$ photons, the second moment over Haar-random $U \in U(m)$ is:
$$\mathbb{E}_{U} [f_U(\rho, O)^2] = \sum_{k=0}^n \frac{1}{d_k^{(n)}} \| P_k^{(n)}(\rho) \|_2^2 \| P_k^{(n)}(O) \|_2^2$$
where $P_k^{(n)}$ is the projection onto the $k$-th irreducible component and $d_k^{(n)}$ is its dimension.

B. Normalized Average Collision Probability ($P_2$)

The authors derive an exact expression for $P_2(m, n)$, defined as the average probability of sampling the same outcome twice:
$$P_2(m, n) = \sum_{k=0}^n \frac{(m+k-1)_k}{(m+n)_k} {}_2F_1(-k, n-k+1; 2-m-2k; -1)$$
where $(x)_p$ is the Pochhammer symbol and ${}_2F_1$ is the hypergeometric function.

C. Asymptotic Scaling and Anti-Concentration

By analyzing the asymptotic behavior of $P_2(m, n)$ as $n \to \infty$ with $m = c n^\beta$:

• Dilute Regime ($\beta \ge 2$): $P_2(m, n) \sim \kappa n$. This recovers known results but without relying on the hiding property.
• Saturated/Linear Regime ($1 \le \beta < 2$): $P_2(m, n) \sim \frac{m}{n} + 1$.
  • Specifically, for the linear regime $m = cn$, $P_2(m, n) \to c + 1$.

Anti-Concentration Result:
Using the Paley-Zygmund inequality, they prove that for $m = c n^\beta$ with $1 \le \beta < 2$:
$$\Pr \left[ p_U(S) \ge \frac{\alpha}{|\Phi_n^m|} \right] \ge \frac{(1-\alpha)^2}{1 + m/n + o(1)}$$
This confirms that the output distribution is anti-concentrated in the linear regime. The probability of observing a "large" outcome scales as $(1 + m/n)^{-1}$, which is constant (non-vanishing) in the linear regime ($m \propto n$).

5. Significance

• Bridging the Hardness Gap: The results provide the missing analytical ingredient (anti-concentration) required to strengthen complexity-theoretic hardness arguments for Boson sampling in the saturated regime. This complements recent work (e.g., Bouland et al.) that established hardness assumptions for this regime.
• Experimental Relevance: The linear regime ($m \propto n$) is the most experimentally feasible setting for current photonic devices. Proving anti-concentration here validates the quantum advantage claims for these specific experimental parameters.
• General Toolkit: The representation-theoretic tools developed (recursive projection, Howe duality in linear optics) are general and applicable to other problems, such as:
  • Linear cross-entropy benchmarking (XEB).
  • Randomized benchmarking for linear optics.
  • Classical shadows for photonic states.
  • Analysis of concentration phenomena in variational quantum algorithms.
• Beyond Hiding Property: The work demonstrates that rigorous statistical analysis of Boson sampling does not strictly require the hiding property or Gaussian approximations, opening the door to analyzing more complex, collision-heavy quantum systems.

In summary, the paper resolves a long-standing open problem regarding the statistical properties of Boson sampling in the experimentally critical saturated regime, providing rigorous evidence for its hardness and establishing a powerful new mathematical framework for analyzing linear optical quantum systems.