🔬 condensed matter

Moments of Random Permanents and Hafnians: A Replica Approach

This paper employs a replica approach with contour-integral representations to derive closed-form expressions for the moments of random permanents and Hafnians, revealing a replica-symmetric dominant saddle point for $k>2$ and a phase transition at $k=2$ that separates the distribution's bulk from its large-deviation tail, with direct applications to boson sampling.

Original authors: Paolo Facchi, Angelo Mariano, Giorgio Parisi, Saverio Pascazio, Antonello Scardicchio

Published 2026-10-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paolo Facchi, Angelo Mariano, Giorgio Parisi, Saverio Pascazio, Antonello Scardicchio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern physics, there is a quiet but profound divide between two ways nature organizes itself. On one side stand fermions, the particles that make up matter, like electrons in an atom. They are solitary and strict; no two can ever occupy the same space or state at the same time. This rule creates a kind of mathematical cancellation, where certain possibilities wipe each other out, leaving behind a structure that is surprisingly easy to calculate and predict. On the other side are bosons, the particles that carry forces, like photons of light. They are social and generous; they love to crowd together into the same state. When they do, the mathematical cancellations that help us with fermions disappear entirely. Instead of simplifying, the math explodes into a massive, tangled sum of possibilities that grows so fast it becomes nearly impossible to solve with a standard computer. This difference is not just a curiosity of particle physics; it is the engine behind a new kind of computing that uses light to solve problems that would take classical machines thousands of years to finish.

The heart of this difficulty lies in a specific mathematical object called a permanent. While the more famous determinant is a tool used to solve systems of equations and describes the behavior of fermions, the permanent is its signless, chaotic cousin. It describes the behavior of bosons. For a long time, scientists have known that calculating a permanent for a large system is an incredibly hard task, one that belongs to a class of problems so difficult that even the most powerful supercomputers struggle with them. However, knowing that a problem is hard is different from understanding the statistical behavior of the answers it produces. When researchers build machines to generate random patterns of light, they are not trying to calculate a single, specific permanent. Instead, they are sampling from a vast distribution of possible outcomes, hoping to see if the light behaves in a way that a classical computer could not mimic. To do this, they need to know what the typical behavior of these random permanents looks like, and how often extreme, rare values might appear.

A team of physicists has now mapped out this statistical landscape with remarkable precision. They focused on the moments of these random permanents, which are essentially measurements of how the values spread out and how heavy their tails are. By treating the problem as if it were a system of interacting spins in a magnetic material, they were able to use a powerful technique called the replica method. This approach allowed them to turn a difficult counting problem into a calculation of the most likely state, or saddle point, of a complex system. They discovered that for most scenarios, the system settles into a predictable, symmetric state where the behavior is governed by a simple exponential growth rate. This rate depends only on whether the underlying numbers are real or complex, acting as a universal law for the growth of these values.

However, the story changes when looking at the very center of the distribution. The researchers found that the simple, symmetric solution they used for most cases breaks down when examining the lower moments, specifically the second moment. At this point, the system becomes unstable, revealing a sharp transition between the bulk of the data and a heavy tail of rare, extreme events. In this tail region, the probability of finding a very large permanent follows a specific power law, meaning that while these extreme values are rare, they are far more common than one would expect in a standard bell curve. This heavy tail is crucial because it suggests that the output of these light-based experiments is dominated by a few very bright outcomes, making the task of verifying the experiment statistically challenging but also physically distinct from other types of random processes.

The team applied these findings to two specific types of photonic experiments: one using single photons and another using squeezed light, a special state where the light waves are compressed. They found that while both setups produce heavy-tailed distributions, the single-photon setup has a much heavier tail, meaning its extreme outcomes are even more likely to occur. This difference has direct consequences for how many samples an experiment needs to run to prove it is working correctly. For the single-photon case, the number of required samples grows exponentially with the size of the system, making verification incredibly expensive. For the squeezed-light case, the growth is much slower, suggesting that these experiments might be easier to validate in practice. The researchers also showed that their mathematical predictions match perfectly with exact computer enumerations of small systems, giving them high confidence that their formulas describe the true behavior of these complex light patterns.

Ultimately, this work provides a clear map of the statistical terrain for random permanents and their related mathematical twins, the Hafnians. It confirms that the difficulty of these problems is not just a computational hurdle but a fundamental feature of the physics of light. By understanding the shape of the distribution, from the common bulk to the rare, extreme tails, scientists can better design and test the next generation of quantum computers. The study does not solve the problem of calculating a permanent for a specific large matrix, but it does solve the problem of understanding what happens when you throw a million random matrices at a computer and ask what the results look like. The answer is that nature, in its bosonic form, is surprisingly generous with its extremes, creating a landscape where the rare and the extraordinary are not just possible, but an integral part of the whole.

Technical Summary: Moments of Random Permanents and Hafnians: A Replica Approach

Problem Statement
The paper addresses the statistical mechanics of random matrix permanents and Hafnians, specifically the computation of their moments $\langle | \text{per } M |^{2k} \rangle$ and $\langle | \text{hf } M |^{2k} \rangle$ for $N \times N$ (or $2N \times 2N$ ) random matrices with independent and identically distributed (i.i.d.) entries. While the moments of determinants are well-understood due to their connection to matrix spectra, permanents lack a spectral representation and are computationally #P-complete. This difficulty has left the high-order moments of random permanents largely unexplored, despite their critical role in quantifying the output distributions of photonic quantum computing experiments, specifically Boson Sampling (single photons) and Gaussian Boson Sampling (squeezed states). The authors aim to derive closed-form expressions for the exponential growth rates, prefactors, and finite-size ( $1/N$ ) corrections of these moments for both real and complex Gaussian ensembles, as well as general symmetric distributions.

Methodology
The authors employ a "replica approach" analogous to the calculation of partition function moments in mean-field spin glasses. The core methodology involves three steps:

Contour-Integral Representation: The permanent and Hafnian are expressed as multiple contour integrals in the complex plane. For a matrix $M$ , the permanent is represented as:
$\text{per}(M) = \prod_{i=1}^N \oint \frac{du_i}{2\pi i u_i^2} \prod_{j=1}^N \oint \frac{dv_j}{2\pi i v_j^2} \exp\left( \sum_{i,j} u_i M_{ij} v_j \right)$
This transforms the problem of averaging powers of the permanent into an integral over auxiliary variables.
Hubbard-Stratonovich (HS) Decoupling: To average over the random matrix entries $M_{ij}$ , the authors introduce complex (or real) HS fields. This decouples the rows and columns of the matrix, converting the problem into an integral over these auxiliary fields. For Gaussian entries, this results in an effective action involving the Hafnian (for real matrices) or the permanent (for complex matrices) of the HS field matrix.
Saddle-Point Analysis: In the limit of large $N$ , the integrals are evaluated using the saddle-point method. The authors analyze the stability of the saddle points, distinguishing between the Replica Symmetric (RS) solution and potential Replica Symmetry Breaking (RSB). They derive the rate function $\Lambda(k) = \lim_{N \to \infty} \frac{1}{N} \ln \langle Y^k \rangle$ , where $Y$ is the normalized moment, and calculate the Gaussian fluctuations around the saddle point to obtain the prefactor and the first $1/N$ correction.

Key Contributions and Results

Replica Symmetry for $k > 2$ : For the $2k$ -th moment, the dominant saddle point is replica symmetric for all $k > 2$ . The authors derive the exact exponential growth rate $\Lambda(k)$ , the prefactor $C_k$ , and the first $1/N$ correction term $a_1/N$ in closed form.
- Real Gaussian Matrices: The rate function is $\Lambda_R(k) = 2k \ln 2 + 2 \ln \Gamma(k + 1/2) - \ln \pi - k \ln(2k - 1)$ . The prefactor and correction terms depend on the cumulants of the entry distribution; specifically, the fourth cumulant $\kappa_4$ modifies the prefactor, while higher cumulants affect only the $1/N$ term.
- Complex Gaussian Matrices: The rate function is $\Lambda_C(k) = 2 \ln \Gamma(k+1) - k \ln k$ . The authors establish an exact moment-size duality: $\langle |\text{per } M|^{2k} \rangle_N = \langle |\text{per } M|^{2N} \rangle_k$ . This duality, previously derived via representation theory, is recovered here via HS decoupling.
Instability at $k=2$ and Large Deviations: At $k=2$ , the replica-symmetric solution becomes unstable (the Hessian develops a zero or negative eigenvalue). This signals a transition between the "bulk" of the distribution and the "large-deviation tail." The authors compute the tail behavior, finding a universal power-law decay $P(y) \sim y^{-3}$ (for the normalized variable) in the transition region, followed by a stretched exponential tail. The bulk distribution ( $k \le 2$ ) requires RSB techniques, which are noted as a subject for future work.
Hafnians and Gaussian Boson Sampling: The paper derives a duality between the moments of real Gaussian permanents and the moments of Hafnians of symmetric complex Gaussian matrices. Specifically, $\langle (\text{per } M)_{real}^{2k} \rangle_N = \langle |\text{hf } M|^{2N} \rangle_{2k}$ . This result is directly applicable to Gaussian Boson Sampling, where output probabilities are proportional to squared Hafnians.
Universality: The exponential growth rate $\Lambda(k)$ is shown to be universal for any entry distribution possessing all moments (e.g., Rademacher $\pm 1$ entries), depending only on whether the entries are real or complex. Non-Gaussian features (higher cumulants) only influence the subleading prefactors and finite-size corrections.

Significance and Claims
The paper claims to provide the first systematic analytical treatment of high-order moments of random permanents and Hafnians using techniques from disordered systems. The authors emphasize that:

Analytical Access: They successfully turn a combinatorial counting problem into a solvable statistical mechanics problem, obtaining results that agree remarkably well with exact numerical enumerations for small $N$ (e.g., $N=8, 9$ ).
Experimental Relevance: The results quantify the "heavy tails" of the output probability distributions in photonic experiments. The authors note that the high variance (determined by moments $k \ge 3$ ) implies that statistical benchmarks like cross-entropy scores require a number of samples that grows exponentially with $N$ , and that standard Gaussian confidence intervals are insufficient due to the heavy-tailed nature of the distribution.
Distinction between Sampling and Evaluation: The paper clarifies that while evaluating a single permanent is hard, the statistical properties of random permanents (which determine the difficulty of sampling) can be characterized by these moments.
Limitations: The authors modestly state that their replica-symmetric approach is valid for $k > 2$ . The behavior of the distribution in the bulk ( $k \le 2$ ), which determines properties like anti-concentration (crucial for hardness proofs), remains inaccessible via this specific method and requires a future RSB calculation.

The work connects the theory of random matrices with the physics of spin glasses, suggesting that the "less-explored counterpart" to determinants (permanents) can be understood through the lens of replica symmetry and its breaking.

More like this