Let $\mathbb{K}\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$, put $β=\dim_{\mathbb{R}}\mathbb{K}$, and let $G_n^{\mathbb{K}}$ be an $n\times n$ matrix with i.i.d. standard $\mathbb{K}$-Gaussian entries, namely a standard $\mathbb{K}$-Ginibre matrix. We prove that the normalized row-ordered permanent $W_n^{\mathbb{K}}=\operatorname{per}_{\mathbb{K}}G_n^{\mathbb{K}}/\sqrt{n!}$ has a radial density $p_n^{\mathbb{K}}$ satisfying $\|p_n^{\mathbb{K}}\|_\infty=p_n^{\mathbb{K}}(0)\lesssim_βn^{(β+2)/4}$ and $\sup_{z\in\mathbb{K}}\mathbb{P}(|W_n^{\mathbb{K}}-z|\leq\varepsilon)\lesssim_βn^{(β+2)/4}\varepsilon^β$. In particular, for $\mathbb{K}=\mathbb{C}$, this resolves the Permanent Anticoncentration Conjecture of Aaronson and Arkhipov. The proof compares the squared Gaussian permanent with the squared (Study) determinant in Laplace-transform order.
Let K∈{R,C,H}, put β=dimRK, and let GnK be an n×n matrix with i.i.d. standard K-Gaussian entries, namely a standard K-Ginibre matrix. We prove that the normalized row-ordered permanent WnK=perKGnK/n! has a radial density pnK satisfying ∥pnK∥∞=pnK(0)≲βn(β+2)/4 and supz∈KP(∣WnK−z∣≤ε)≲βn(β+2)/4εβ. In particular, for K=C, this resolves the Permanent Anticoncentration Conjecture of Aaronson and Arkhipov. The proof compares the squared Gaussian permanent with the squared (Study) determinant in Laplace-transform order.
We report on a computational and experimental study of permanents. On the computational side, we use the GPU to greaatly accelerate the computation of permanents over C,R,Fp and Q. First, for Haar-distributed unitary matrices~U, the permanent $\perm(U)$ follows a circularly-symmetric complex Gaussian distribution CN(0,σ2) -- we confirm this via a number of tests for n up to~23 with 50,000 samples. The DFT matrix permanent is an extreme outlier for every prime n≥7. In contrast, for Haar-random \emph{orthogonal} matrices~O, the permanent $\perm(O)$ is approximately real Gaussian but with positive excess kurtosis that decays as~O(1/n), indicating slower convergence. For matrices with Gaussian entries (GUE, GOE, Ginibre), the permanent follows an α-stable distribution with stability index α≈1.0--1.4, well below the Gaussian value α=2. We test Aaronson's conjecture that $|\perm(X)|^2$ is asymptotically lognormal for Gaussian~X: it is plausible for the complex Ginibre and GOE ensembles, but appears to fail for GUE and real Ginibre, where the α-stable tails prevent convergence. Anti-concentration, however, holds for all Gaussian ensembles and is more robust than for Haar unitaries.
Secondly, we study the permanent along geodesics on the unitary group. For the geodesic from the identity to the n-cycle permutation matrix, we find a universal scaling function $f(t)=\frac{1}{n}\ln|\perm(γ(t))|$ that is independent of~n in the large-n limit, with a midpoint value \[
\perm(γ({\textstyle\frac12}))
= (-1)^{(n-1)/2}\cdot 2e^{-n}\bigl(1+\tfrac{1}{3n}+O(n^{-2})\bigr) \] for odd~n and zero for even~n. We also study the geodesic forom the identity to the DFT matrix.
We prove a uniform shifted anticoncentration theorem for the hafnian of a real Gaussian Gram matrix under an explicit condition on the row dimension. After normalization by its root mean square, the law has a bounded continuous density, maximal at zero, and every interval has probability bounded by an explicit coefficient times its radius. Under suitable growth conditions on the row dimension, this coefficient grows at most polynomially in the hafnian order, meaning half the dimension of the Gram matrix. We also compute the exact second moment. The proof exploits the perfect matching structure, combining conditional Gaussian representations, row suspension, and bilinear interpolation to control an inverse moment of the conditional variance. At fixed hafnian order, a rescaled limit as the row dimension grows yields corresponding bounds for the hafnian of a real symmetric Gaussian matrix with independent entries above the diagonal.
We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and \emph{boson sampling} (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial per(zJ+W), where J is the all-ones matrix and W is a random matrix with independent mean-zero entries.
We show that when the entries of W are standard complex Gaussians, all zeros of the random polynomial per(zJ+W) lie within a disk of radius O~(n−1/3), which yields an approximation algorithm when the bias of the entries is Ω~(n−1/3). Previously, there were no efficient algorithms at biases smaller than 1/polylog(n), and it was unknown whether there typically exist zeros z with ∣z∣≥1. As a complementary result, we show that the bulk of the zeros, namely (1−ε)n of them, have magnitude Θ(n−1/2). This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices W with i.i.d. subexponential entries.
Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.
Let G2n be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let Hn=haf(G2n). We prove the uniform shifted anticoncentration bound Pr((2n−1)!!Hn−z≤ε)≤2πnε2 for every z∈C and ε>0. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.
Exact Moments of Gaussian Gram Hafnians Reveal an n2/logn Threshold for Weak Anticoncentration
Anticoncentration is central to hardness arguments for approximate sampling. In the independent Gaussian surrogate for collision free Gaussian boson sampling, the moment ratio studied here also determines the averaged ideal linear cross entropy reference value. Let Hk,n=haf(XTX), where X∈Ck×2n has independent standard circular complex Gaussian entries. We evaluate E∣Hk,n∣2 and E∣Hk,n∣4 exactly by reducing four hafnian copies to a rank two Gaussian integral. For Rk,n=(E∣Hk,n∣2)2/E∣Hk,n∣4, we obtain Rk,n=4−n(n2n)/Fk,n, where Fk,n=3F2(−n,−n,1/2;1,k/2;1) is a terminating generalized hypergeometric polynomial. If k/n2→c>0, then Fk,n→e1/cI0(1/c), where I0 is the modified Bessel function of the first kind of order zero, and consequently Rk,nπn→[e1/cI0(1/c)]−1. Thus k≍n2 is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is k≍n2/logn. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.