Using contour-integral representations of the permanent and of the Hafnian, we turn the computation of their moments for random matrices into a replica calculation, analogous to that of the moments of the partition function of a mean-field spin glass. For the $2k$-th moment of $N\times N$ matrices with independent entries, the dominant saddle point is replica symmetric for $k>2$, and we obtain in closed form the exponential growth rate, the prefactor and the first $1/N$ correction, in agreement with exact enumerations. The growth rate depends only on whether the entries are real or complex; higher cumulants affect only the prefactor and the $1/N$ term. At $k=2$ the replica-symmetric solution becomes unstable, separating a power-law bulk of the distribution from a large-deviation tail, which we compute. The results apply to boson sampling with single photons and with squeezed light.
AI Summary
The paper studies high moments and right tails of random permanents and Hafnians, motivated by ideal single-photon and Gaussian boson sampling. Contour-integral representations and Hubbard–Stratonovich decoupling convert moment calculations into finite-dimensional replica integrals, evaluated by saddle-point expansion at fixed integer $k\ge3$ and large matrix size $N$.
For $Y=|\operatorname{per}M|^2/N!$, it obtains $\langle Y^k\rangle\sim C_kN^\alpha e^{N\Lambda(k)}$, including explicit prefactors and $1/N$ corrections. For real unit-variance Gaussian entries, $\Lambda(k)=2\log[(2k-1)!!]-k\log(2k-1)$ and $\alpha=k/2$; for circular complex Gaussians, $\Lambda(k)=2\log(k!)-k\log k$ and $\alpha=(k-1)/2$. Higher entry cumulants change subleading terms rather than the exponential rate. Exact moment–size dualities connect complex permanents to themselves and real permanents to complex symmetric Hafnians. Normalized Hafnian moments have the complex-permanent rate per photon pair, without a polynomial prefactor. Exact moment computations test the expansions, and the complex prefactor gives an explicit limit previously conjectured to exist.
The paper infers a $Y^{-3}$ crossover and large-deviation tails from moment continuation. Boson-sampling applications predict exponentially growing variance-based sample requirements for linear cross-entropy estimation. The replica-symmetric expansion becomes singular at $k=2$ and does not determine the bulk or anti-concentration. Optical applications require dilute Gaussian-submatrix approximations; fixed-device self-averaging is assumed, and noise is excluded. Some symbolic calculations were LLM-assisted and not independently checked by hand, although numerical consistency checks are reported.
Little sign of AI-generated textAI use disclosedOverclaimsPossible error
some calculations in this section have been done using Claude and were not checked by hand (although they were checked by an adversarial LLM, ChatGPT, and found correct).
Central claim may not hold: Section V uses integer-replica moment formulas at noninteger and complex orders without establishing the continuation or asymptotic control required for Mellin inversion.
The claimed linear distributional rate I(η)=2η and resulting y^{-3} regime are not established because the Mellin saddle calculation excludes that interval and the Legendre transform supplies no matching probability lower bound there.
The experimental section omits the sample-count factor when computing the empirical mean's squared skewness, giving exponential rate approximately 0.76 instead of approximately 0.47.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Using contour-integral representations of the permanent and of the Hafnian, we turn the computation of their moments for random matrices into a replica calculation, analogous to that of the moments of the partition function of a mean-field spin glass. For the 2k-th moment of N×N matrices with independent entries, the dominant saddle point is replica symmetric for k>2, and we obtain in closed form the exponential growth rate, the prefactor and the first 1/N correction, in agreement with exact enumerations. The growth rate depends only on whether the entries are real or complex; higher cumulants affect only the prefactor and the 1/N term. At k=2 the replica-symmetric solution becomes unstable, separating a power-law bulk of the distribution from a large-deviation tail, which we compute. The results apply to boson sampling with single photons and with squeezed light.
The paper studies high moments and right tails of random permanents and Hafnians, motivated by ideal single-photon and Gaussian boson sampling. Contour-integral representations and Hubbard–Stratonovich decoupling convert moment calculations into finite-dimensional replica integrals, evaluated by saddle-point expansion at fixed integer k≥3 and large matrix size N.
For Y=∣perM∣2/N!, it obtains ⟨Yk⟩∼CkNαeNΛ(k), including explicit prefactors and 1/N corrections. For real unit-variance Gaussian entries, Λ(k)=2log[(2k−1)!!]−klog(2k−1) and α=k/2; for circular complex Gaussians, Λ(k)=2log(k!)−klogk and α=(k−1)/2. Higher entry cumulants change subleading terms rather than the exponential rate. Exact moment–size dualities connect complex permanents to themselves and real permanents to complex symmetric Hafnians. Normalized Hafnian moments have the complex-permanent rate per photon pair, without a polynomial prefactor. Exact moment computations test the expansions, and the complex prefactor gives an explicit limit previously conjectured to exist.
The paper infers a Y−3 crossover and large-deviation tails from moment continuation. Boson-sampling applications predict exponentially growing variance-based sample requirements for linear cross-entropy estimation. The replica-symmetric expansion becomes singular at k=2 and does not determine the bulk or anti-concentration. Optical applications require dilute Gaussian-submatrix approximations; fixed-device self-averaging is assumed, and noise is excluded. Some symbolic calculations were LLM-assisted and not independently checked by hand, although numerical consistency checks are reported.
Computing the distribution of permanents of random matrices has been an outstanding open problem for several decades. In quantum computing, "anti-concentration" of this distribution is an unproven input for the proof of hardness of the task of boson-sampling. We study permanents of random i.i.d. complex Gaussian matrices, and more broadly, submatrices of random unitary matrices. Using a hybrid representation-theoretic and combinatorial approach, we prove strong lower bounds for all moments of the permanent distribution. We provide substantial evidence that our bounds are close to being tight and constitute accurate estimates for the moments. Let U(d)k×k be the distribution of k×k submatrices of d×d random unitary matrices, and Gk×k be the distribution of k×k complex Gaussian matrices. (1) Using the Schur-Weyl duality (or the Howe duality), we prove an expansion formula for the 2t-th moment of ∣Perm(M)∣ when M is drawn from U(d)k×k or Gk×k. (2) We prove a surprising size-moment duality: the 2t-th moment of the permanent of random k×k matrices is equal to the 2k-th moment of the permanent of t×t matrices. (3) We design an algorithm to exactly compute high moments of the permanent of small matrices. (4) We prove lower bounds for arbitrary moments of permanents of matrices drawn from Gk×k or U(k), and conjecture that our lower bounds are close to saturation up to a small multiplicative error. (5) Assuming our conjectures, we use the large deviation theory to compute the tail of the distribution of log-permanent of Gaussian matrices for the first time. (6) We argue that it is unlikely that the permanent distribution can be uniquely determined from the integer moments and one may need to supplement the moment calculations with extra assumptions to prove the anti-concentration conjecture.
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 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.
In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.
We develop closed-form expressions for the moments and cumulants of Gaussian states when measured in the photon-number basis. We express the photon-number moments of a Gaussian state in terms of the loop Hafnian, a function that when applied to a ( 0 , 1 ) -matrix representing the adjacency of a graph, counts the number of its perfect matchings. Similarly, we express the photon-number cumulants in terms of the Montrealer, a newly introduced matrix function that when applied to a ( 0 , 1 ) -matrix counts the number of Hamiltonian cycles of that graph. Based on these graph-theoretic connections, we show that the calculation of photon-number moments and cumulants are #P-hard. Moreover, we provide an exponential time algorithm to calculate Montrealers (and thus cumulants), matching well-known results for Hafnians. We then demonstrate that when a uniformly lossy interferometer is fed in every input with identical single-mode Gaussian states with zero displacement, all the odd-order cumulants but the first one are zero. Finally, we employ the expressions we derive to study the distribution of cumulants up to the fourth order for different input states in a Gaussian boson sampling setup where K identical states are fed into an ℓ -mode interferometer. We analyze the dependence of the cumulants as a function of the type of input state, squeezed, lossy squeezed, squashed, or thermal, and as a function of the number of non-vacuum inputs. We find that thermal states perform much worse than other classical states, such as squashed states, at mimicking the photon-number cumulants of lossy or lossless squeezed states.
Gaussian boson samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For non-negative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that, in general, both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian boson sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.