PaperlayerView exact revision on arXiv

Source-linked AI summary

Anticoncentration of Complex Gaussian Hafnians

Priyanshu Pant

arXiv:2609.35019v1math.PRcs.CC

TL;DR

Anticoncentration is one ingredient in hardness arguments for boson sampling, and the paper addresses local control of normalized complex Gaussian hafnians. It uses cofactor inverse-moment bounds to establish a density theorem and a stronger product-Gamma comparison; the resulting local bound provides a probabilistic input to Gaussian boson sampling, not a complete hardness result.

  • Problem

    Hardness arguments for boson sampling require anticoncentration, and the paper targets a uniform local bound for normalized Gaussian hafnians.

    Source: §1 · pp. 1–2

  • Method

    The proof reduces density control to a cofactor inverse-moment bound and uses Gaussian compression to obtain a recurrence and product-Gamma comparison.

    Source: §1 · pp. 2–3, §7 · p. 14

  • Results

    Theorem 1.1 establishes a radial, radially nonincreasing density for the normalized hafnian W_n.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The local bound transfers to COE hafnians in the stated hiding regimes and supplies a probabilistic input to the GBS hardness program.

    Source: §1 · p. 3, §6 · p. 13

    The probabilistic bound does not establish classical sampling hardness; average-case hardness for the corresponding random hafnians remains a separate requirement.

    Source: §6 · p. 13

Abstract

from arXiv · show

Let $G_{2n}$ be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let $H_n=\operatorname{haf}(G_{2n})$. We prove the uniform shifted anticoncentration bound $$ \Pr\!\left( \left| \frac{H_n}{\sqrt{(2n-1)!!}}-z \right| \le \varepsilon \right) \le 2\sqrt{\frac n\pi}\,\varepsilon^2 $$ for every $z\in\mathbb C$ and $\varepsilon>0$. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.

1 Introduction

The paper studies local, shifted anticoncentration for complex Gaussian hafnians, addressing a question not answered by moment-based control of GBS output probabilities. It proves a density theorem through cofactor inverse-moment bounds and Gaussian compression, and develops a stronger product-Gamma comparison with a GBS application.

1 Introduction

  • The hafnian is the perfect-matching polynomial for symmetric matrices, while GBS uses Gaussian squeezed states and collision-free probabilities involving squared hafnians [5, 7].Source: §1 · p. 1
  • Moment-based studies of GBS output probabilities do not provide local control near a prescribed complex value, motivating the shifted small-neighborhood question.Source: §1 · pp. 1–2
  • Theorem 1.1 establishes a radial, radially nonincreasing density for the normalized hafnian W_n, derived from an inverse-moment bound on A_n.Source: §1 · pp. 2–3
  • A one-vertex expansion reduces the small-ball problem to an inverse-norm problem for an odd hafnian cofactor vector.Source: §1 · p. 2
  • The two-vertex expansion introduces a shared-edge term whose nonnegative factor permits Gaussian interpolation and coordinate compression.Source: §1 · pp. 2–3
  • The compression argument also yields product-Gamma Laplace domination, whose odd Gamma shapes track successive cofactor-vector dimensions and imply fractional negative-moment bounds.Source: §1 · p. 3
  • The proof parallels Gaussian permanent anticoncentration work [6], while hafnian symmetry adds a shared-edge coupling; concurrent work also studies shifted Gaussian-hafnian anticoncentration [9].Source: §1 · p. 3
  • The independent symmetric Gaussian ensemble is relevant to maximally squeezed GBS, and hiding results transfer local ε^2 small-ball behavior to COE hafnians.This is a probabilistic input to the GBS hardness program, not a complete hardness theorem.Source: §1 · p. 3

2 From a Gaussian hafnian to one inverse moment

The proof reduces the hafnian to a conditional Gaussian linear combination of cofactors, then uses its mixture density to identify an inverse moment controlling anticoncentration.

2 From a Gaussian hafnian to one inverse moment

  • Expanding at one vertex expresses the hafnian as a sum over incident edges, each weighted by the hafnian of the matrix with that edge’s endpoints deleted.The expansion follows by grouping perfect matchings according to the partner of the exposed vertex.Source: §2 · p. 4
  • After adjoining a vertex with an independent Gaussian edge vector, the hafnian is conditionally complex Gaussian with variance given by the squared norm of its cofactor vector.The cofactor vector is nonzero almost surely, so this conditional variance is nonzero almost surely.Source: §2 · pp. 4–5
  • Mixing the conditional densities yields a radial, nonincreasing density, whose value at zero is controlled by the inverse squared norm of the cofactor vector.This identifies the inverse moment as the quantity carried forward into the anticoncentration argument.Source: §2 · p. 5

3 Two-vertex compression of hafnian cofactors

The section compresses the cofactor characteristic function toward a coordinate axis while preserving the coefficient norm. The key is that averaging the symmetry-specific shared edge leaves a positive weight compatible with Gaussian interpolation.

3.1 The two-vertex algebra

  • The two-vertex decomposition adds a shared-edge term absent from the analogous rectangular permanent calculation, and averaging that edge produces a nonnegative factor.This positive weight is the symmetry-specific feature that allows the compression argument to proceed.Source: §3.1 · p. 6, §3.3 · p. 8

3.2 A Gaussian interpolation lemma

  • Gaussian geometric interpolation bounds the joint-coordinate expectation by a weighted geometric mean of its endpoint expectations, and Hölder preserves this bound after averaging over a nonnegative weight.The interpolation applies to the Gaussian bilinear and linear terms arising in the two-vertex decomposition.Source: §3.2 · p. 7

3.3 Coordinate compression

  • At fixed Euclidean norm, the cofactor characteristic function is largest along a coordinate axis, enabling repeated compression of any coefficient vector.Each two-coordinate replacement preserves the norm and does not decrease the upper bound.Source: §3 · p. 5, §3.3 · p. 8
  • Iterating coordinate compression leaves one nonzero coordinate; exchangeability and circular symmetry let it be taken as the first coordinate with its phase removed.The first cofactor coordinate has the same law as the preceding-order hafnian.Source: §3.3 · p. 8

4 The inverse-moment recurrence and anticoncentration

An inverse-moment recurrence bounds the density at the origin, and radial monotonicity extends that control to disks centered anywhere. The resulting normalization supports a uniform shifted small-ball estimate.

4 The inverse-moment recurrence and anticoncentration

  • A_n ≤ 1/[2^(n−1)(n−1)!], giving the inverse-moment bound used to control the hafnian density.The recurrence starts from A_1 = 1; its iteration yields the displayed bound.Source: §4 · pp. 9–10
  • The second-moment normalization is (2n−1)!!, and rescaling by its square root converts the density bound into one for the normalized hafnian.The proof uses the orthogonality of distinct matching monomials and counts (2n−1)!! perfect matchings.Source: §4 · p. 10
  • Radial monotonicity lets the density bound control the mass of an ε-radius disk centered at any complex z.Integrating the density over such a disk gives the uniform shifted small-ball estimate.Source: §4 · p. 10

5 A stronger product-Gamma comparison

The paper strengthens its inverse-moment estimate to a full Laplace-transform comparison with a product-Gamma benchmark. That comparison also yields fractional negative-moment bounds, while the earlier recurrence appears as its q = 1 case.

5 A stronger product-Gamma comparison

  • The compression mechanism yields a full Laplace-transform comparison, of which the inverse-moment recurrence is only one consequence.The direct recurrence is identified as the q = 1 shadow of the stronger product-Gamma comparison.Source: §5 · pp. 11–12
  • The comparison uses a product of independent Gamma variables with odd integer shape parameters as its benchmark.The sequence begins with γ_1, γ_3, γ_5, and so on.Source: §5 · p. 11
  • Fractional negative-moment bounds hold for the product-Gamma benchmark when 0 < q < 3 and for the hafnian quantity when 0 < q < 1.The different ranges reflect the smallest Gamma shape parameters stated for the two comparisons.Source: §5 · p. 12

6 Application to Gaussian boson sampling

The application transfers the complex-Gaussian hafnian small-ball result to COE blocks in the maximally squeezed GBS setting when n=o(M^1/3). This probabilistic input is not a complete hardness theorem.

6 Application to Gaussian boson sampling

  • The physical output probabilities have additional squeezing-dependent prefactors, which do not affect the stated local random-matrix result.Source: §6 · p. 13
  • In the maximally squeezed setting, collision-free GBS amplitudes use a principal block of a COE matrix UUT, with U Haar distributed in U(M).A fixed N-mode output pattern corresponds to an N × N principal block.Source: §6 · p. 13
  • When n=o(M^1/3), Corollary 6.1 gives a COE hafnian small-ball bound uniform over z and ε.The passage does not provide the bound's explicit right-hand side.Source: §6 · p. 13
  • The proof uses degree-n homogeneity of the hafnian to rescale the COE block's hafnian before applying the density comparison over a small-ball event.The text gives the scaling as MA2n,M) = Mn/2 haf(A2n,M).Source: §6 · p. 13
  • The small-ball estimate is a probabilistic input to GBS hardness arguments, while exact or approximate average-case hardness for the corresponding random hafnians remains a separate ingredient.Source: §6 · p. 13

7 Discussion

The discussion identifies structural identities that drive the anticoncentration proof and a stochastic comparison that yields information beyond the density estimate at the origin.

7 Discussion

  • A one-vertex expansion represents a random hafnian as a one-dimensional Gaussian with random variance.Source: §7 · p. 14
  • A two-vertex expansion reduces a linear combination of cofactors to a Gaussian bilinear expression plus one shared-edge term.Source: §7 · p. 14
  • A final identity turns the symmetry obstruction into a positive weight, after which the proof uses Gaussian integration, Hölder interpolation, and Gamma calculus.Source: §7 · p. 14
  • The inverse-moment recurrence A_n+1 ≤ A_n/(2n) gives the cleanest consequence for the headline anticoncentration theorem.Source: §7 · p. 14
  • The compression also yields product-Gamma Laplace-transform domination, with fractional negative moments illustrating information beyond the density estimate at the origin.Source: §7 · p. 14
  • Further consequences of the stochastic comparison and analogous local bounds for other correlated hafnian ensembles remain directions for study.Source: §7 · p. 14
Loading 2609.35019v1…