Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.35019

Anticoncentration of Complex Gaussian Hafnians

Priyanshu Pant

Published Sep 28, 2026• 0 citations
arXivHTMLPDF

Abstract

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π}\,\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.

DOI
10.48550/arxiv.2609.35019

Related papers

Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry

Hongru Zhao

Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for $2n$ selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order $n^2/\log n$. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.

math.PRCross-listedarXiv:2610.00112•Sep 10, 2026•0 citations

Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration

Hongru Zhao

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 $H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)$, where $X\in\mathbb{C}^{k\times 2n}$ has independent standard circular complex Gaussian entries. We evaluate $\mathbb{E}|H_{k,n}|^2$ and $\mathbb{E}|H_{k,n}|^4$ exactly by reducing four hafnian copies to a rank two Gaussian integral. For $R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4$, we obtain $R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}$, where $F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)$ is a terminating generalized hypergeometric polynomial. If $k/n^2\to c>0$, then $F{k,n}\to e^{1/c}I_0(1/c)$, where $I_0$ is the modified Bessel function of the first kind of order zero, and consequently $R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}$. Thus $k\asymp n^2$ is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is $k\asymp n^2/\log n$. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.

quant-pharXiv:2608.17065•Aug 19, 2026•4 citations

Shifted Anticoncentration for Real Gram Hafnians and Symmetric Gaussian Hafnians

Hongru Zhao

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.

math.PRCross-listedarXiv:2609.06526•Sep 8, 2026

Anticoncentration and entanglement in Gaussian boson sampling

Laura Shou, Adam Ehrenberg, Yu-Xin Wang +2 more

Anticoncentration and entanglement are two properties used to study classical hardness or easiness of Gaussian boson sampling in varying regimes. In this paper, we consider three directions concerning anticoncentration and entanglement in Gaussian boson sampling: (1) We derive closed-form expressions for the second moment of hafnians of symmetric Gaussian products, and use this to precisely locate the anticoncentration transition as a function of the number of squeezed input modes. (2) We derive closed-form expressions for the Rényi-$α$ Page curves for Gaussian boson sampling. (3) We study unequal input squeezing parameters $(s_i)_i$, and prove estimates as well as monotonicity of the average-case Rényi-2 entropy Page curve in terms of the magnitudes $|s_i|$, which allow for extending equal squeezing results to unequal squeezing.

quant-pharXiv:2609.01241•Aug 28, 2026•4 citations

Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality

Frederic Koehler, Pui Kuen Leung

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 $\mathrm{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 $\mathrm{per}(zJ + W)$ lie within a disk of radius $\tilde{O}(n^{-1/3})$, which yields an approximation algorithm when the bias of the entries is $\tildeΩ(n^{-1/3})$. Previously, there were no efficient algorithms at biases smaller than $1/\mathrm{polylog}(n)$, and it was unknown whether there typically exist zeros $z$ with $|z| \ge 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.

cs.DSCross-listedarXiv:2604.01367•Apr 3, 2026•3 citations

Anticoncentration of the Permanent in Ginibre Ensembles

Frederic Koehler, Pui Kuen Leung

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.

math.PRCross-listedarXiv:2607.20329•Jul 23, 2026
Let G2nG_{2n}G2n​ be a complex symmetric random matrix whose entries above the diagonal are independent standard circular complex Gaussians, and let Hn=haf⁡(G2n)H_n=\operatorname{haf}(G_{2n})Hn​=haf(G2n​). We prove the uniform shifted anticoncentration bound Pr⁡ ⁣(∣Hn(2n−1)!!−z∣≤ε)≤2nπ ε2\Pr\!\left( \left| \frac{H_n}{\sqrt{(2n-1)!!}}-z \right| \le \varepsilon \right) \le 2\sqrt{\frac nπ}\,\varepsilon^2Pr(​(2n−1)!!​Hn​​−z​≤ε)≤2πn​​ε2 for every z∈Cz\in\mathbb Cz∈C and ε>0\varepsilon>0ε>0. This establishes a local anticoncentration property that supports hardness arguments for quantum advantage in Gaussian boson sampling.
Local anticoncentration controls the conversion of additive output probability estimates to relative estimates in Gaussian boson sampling. We prove a center-uniform quadratic small-ball bound for hafnians of complex Gaussian transpose Gram matrices for 2n2n2n selected modes, with an explicit finite coefficient that is polynomial when the number of Gaussian rows is at least of order n2/log⁡nn^2/\log nn2/logn. Letting the Gaussian row count tend to infinity yields anticoncentration for the independent complex symmetric Gaussian ensemble. For the transpose Gram hafnian bound, the proof compresses dependent hafnian cofactors by Fourier interpolation and controls their self-coupled variance through a conditional Wishart identity that preserves the transpose Gram coordinate. Independent perturbations satisfy related bounds, and a positive mixture density shows that the local quadratic power is exact. Together with the uniform hiding theorem in the companion paper, the result gives local anticoncentration for finite Haar interferometers.
Exact Moments of Gaussian Gram Hafnians Reveal an n2/log⁡nn^2/\log nn2/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)H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)Hk,n​=haf(XTX), where X∈Ck×2nX\in\mathbb{C}^{k\times 2n}X∈Ck×2n has independent standard circular complex Gaussian entries. We evaluate E∣Hk,n∣2\mathbb{E}|H_{k,n}|^2E∣Hk,n​∣2 and E∣Hk,n∣4\mathbb{E}|H_{k,n}|^4E∣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∣4R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4Rk,n​=(E∣Hk,n​∣2)2/E∣Hk,n​∣4, we obtain Rk,n=4−n(2nn)/Fk,nR_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}Rk,n​=4−n(n2n​)/Fk,n​, where Fk,n=3F2(−n,−n,1/2;1,k/2;1)F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)Fk,n​=3F2​(−n,−n,1/2;1,k/2;1) is a terminating generalized hypergeometric polynomial. If k/n2→c>0k/n^2\to c>0k/n2→c>0, then Fk,n→e1/cI0(1/c)F{k,n}\to e^{1/c}I_0(1/c)Fk,n→e1/cI0​(1/c), where I0I_0I0​ is the modified Bessel function of the first kind of order zero, and consequently Rk,nπn→[e1/cI0(1/c)]−1R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}Rk,n​πn​→[e1/cI0​(1/c)]−1. Thus k≍n2k\asymp n^2k≍n2 is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is k≍n2/log⁡nk\asymp n^2/\log nk≍n2/logn. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.
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.
Anticoncentration and entanglement are two properties used to study classical hardness or easiness of Gaussian boson sampling in varying regimes. In this paper, we consider three directions concerning anticoncentration and entanglement in Gaussian boson sampling: (1) We derive closed-form expressions for the second moment of hafnians of symmetric Gaussian products, and use this to precisely locate the anticoncentration transition as a function of the number of squeezed input modes. (2) We derive closed-form expressions for the Rényi-ααα Page curves for Gaussian boson sampling. (3) We study unequal input squeezing parameters (si)i(s_i)_i(si​)i​, and prove estimates as well as monotonicity of the average-case Rényi-2 entropy Page curve in terms of the magnitudes ∣si∣|s_i|∣si​∣, which allow for extending equal squeezing results to unequal squeezing.
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)\mathrm{per}(zJ + W)per(zJ+W), where JJJ is the all-ones matrix and WWW is a random matrix with independent mean-zero entries. We show that when the entries of WWW are standard complex Gaussians, all zeros of the random polynomial per(zJ+W)\mathrm{per}(zJ + W)per(zJ+W) lie within a disk of radius O~(n−1/3)\tilde{O}(n^{-1/3})O~(n−1/3), which yields an approximation algorithm when the bias of the entries is Ω~(n−1/3)\tildeΩ(n^{-1/3})Ω~(n−1/3). Previously, there were no efficient algorithms at biases smaller than 1/polylog(n)1/\mathrm{polylog}(n)1/polylog(n), and it was unknown whether there typically exist zeros zzz with ∣z∣≥1|z| \ge 1∣z∣≥1. As a complementary result, we show that the bulk of the zeros, namely (1−ε)n(1 - ε)n(1−ε)n of them, have magnitude Θ(n−1/2)Θ(n^{-1/2})Θ(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 WWW with i.i.d. subexponential entries.
Let K∈{R,C,H}\mathbb{K}\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}K∈{R,C,H}, put β=dim⁡RKβ=\dim_{\mathbb{R}}\mathbb{K}β=dimR​K, and let GnKG_n^{\mathbb{K}}GnK​ be an n×nn\times nn×n matrix with i.i.d. standard K\mathbb{K}K-Gaussian entries, namely a standard K\mathbb{K}K-Ginibre matrix. We prove that the normalized row-ordered permanent WnK=per⁡KGnK/n!W_n^{\mathbb{K}}=\operatorname{per}_{\mathbb{K}}G_n^{\mathbb{K}}/\sqrt{n!}WnK​=perK​GnK​/n!​ has a radial density pnKp_n^{\mathbb{K}}pnK​ satisfying ∥pnK∥∞=pnK(0)≲βn(β+2)/4\|p_n^{\mathbb{K}}\|_\infty=p_n^{\mathbb{K}}(0)\lesssim_βn^{(β+2)/4}∥pnK​∥∞​=pnK​(0)≲β​n(β+2)/4 and sup⁡z∈KP(∣WnK−z∣≤ε)≲βn(β+2)/4εβ\sup_{z\in\mathbb{K}}\mathbb{P}(|W_n^{\mathbb{K}}-z|\leq\varepsilon)\lesssim_βn^{(β+2)/4}\varepsilon^βsupz∈K​P(∣WnK​−z∣≤ε)≲β​n(β+2)/4εβ. In particular, for K=C\mathbb{K}=\mathbb{C}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.