For Haar-random quantum states, measurement probabilities follow the universal Porter--Thomas distribution. This implies anticoncentration, i.e.\ the spreading of probability over exponentially many outcomes, a key property underlying random-circuit-sampling experiments. We derive the exact analogue of the Porter--Thomas law for random fermionic Gaussian states, both with and without particle-number conservation. We also consider Clifford Gaussian states, for which the problem maps onto a simple model of arcs and loops. For large systems the probabilities become log-normally distributed, with moments growing polynomially in system size. Free-fermion states thus anticoncentrate only up to polynomial factors. We then show how this fermionic Porter--Thomas law emerges in random one-dimensional brickwork matchgate circuits. A simple single-arc approximation accurately describes the full distribution of probabilities, revealing an early diffusive regime followed by a slow relaxation on times scaling as the square of the system size. We rigorously prove that depths growing almost quadratically with system size are required for the collision probability to converge. Finally, we show that ideal free-fermion sampling yields large linear cross-entropy scores, and propose a log-based benchmark with an exact fermionic normalization.
For Haar-random quantum states, measurement probabilities follow the universal Porter--Thomas distribution. This implies anticoncentration, i.e.\ the spreading of probability over exponentially many outcomes, a key property underlying random-circuit-sampling experiments. We derive the exact analogue of the Porter--Thomas law for random fermionic Gaussian states, both with and without particle-number conservation. We also consider Clifford Gaussian states, for which the problem maps onto a simple model of arcs and loops. For large systems the probabilities become log-normally distributed, with moments growing polynomially in system size. Free-fermion states thus anticoncentrate only up to polynomial factors. We then show how this fermionic Porter--Thomas law emerges in random one-dimensional brickwork matchgate circuits. A simple single-arc approximation accurately describes the full distribution of probabilities, revealing an early diffusive regime followed by a slow relaxation on times scaling as the square of the system size. We rigorously prove that depths growing almost quadratically with system size are required for the collision probability to converge. Finally, we show that ideal free-fermion sampling yields large linear cross-entropy scores, and propose a log-based benchmark with an exact fermionic normalization.
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0, the distribution corresponding to circuits of depth O(n2m+1log(n)) is at most O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.
Anticoncentration describes how an ensemble of quantum states spreads over the allowed Hilbert space, leading to statistically uniform output probability distributions. In this work, we investigate the anticoncentration of random Clifford circuits toward the overlap distribution of random stabilizer states. Using exact analytical techniques and extensive numerical simulations based on Clifford replica tensor networks, we demonstrate that random Clifford circuits fully anticoncentrate in logarithmic circuit depth; namely, higher-order moments of the overlap distribution converge to those of random stabilizer states. Moreover, we investigate the effect of introducing a controlled number of non-Clifford (magic) resources into Clifford circuits. We show that inserting a polylogarithmic in qudit number of T states is sufficient to drive the overlap distribution toward the Porter-Thomas statistics, effectively recovering full quantum randomness. In short, this fact presents doped tensor networks and shallow Clifford circuits as pseudomagic quantum states. Our results clarify the interplay between Clifford dynamics, magic-state injection, and quantum complexity, with implications for quantum circuit sampling, many-body quantum physics, and the benchmarking of quantum computational advantage.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong ε-approximate unitary k-design on n qubits, the distribution of each output probability is within O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters 1 and 2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance O(k−1/2+ε). Every strong ε-approximate unitary k-design invariant on logk+O(1) qubits achieves error 2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong ε-approximate k-design is concentrated around its Haar value n−Θ(1): its mean differs from the Haar mean by O(k−1/4+ε1/2) and its standard deviation is O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates n−O(1) bits of entropy per sample, which makes them useful for random number generation.
Sampling-based quantum advantage raises a basic resource question: how much non-Gaussianity is needed to reproduce the random-matrix statistics often associated with quantum chaos? Passive fermionic linear optics preserves Gaussian structure, and even Haar-random mode mixing fails to anticoncentrate for Slater inputs. We show that overcoming this obstruction requires an extensive input resource. For any pure half-filled input state, the one-body defect ν, defined as the summed occupation variance of the natural orbitals, must scale linearly with system size. For products of bounded-size blocks on 4N modes, this condition is also sufficient, with normalized collision moment asymptotic to 2N/ν, compared with the Porter-Thomas value 2. For four-mode products, the full Porter-Thomas moment hierarchy is recovered precisely when the defect density tends to its maximum. Assuming average-case hardness, approximate classical sampling remains hard near maximal density, with an error tolerance that increases with the density. Two-copy number fluctuations measure ν directly, and the same quantity lower-bounds the combined cost of non-Gaussian resource modes and parity-preserving local gates in deterministic exact preparation. Fermionic randomness therefore carries an extensive magic cost, with a quantitative link between sampling statistics, preparation resources, and an experimentally accessible witness.
While many statistical properties of deep random quantum circuits can be deduced, often rigorously and other times heuristically, by an approximation to global Haar-random unitaries, the statistics of constant-depth random quantum circuits are generally less well-understood due to a lack of amenable tools and techniques. We circumvent this barrier by considering a related constant-time Brownian circuit model which shares many similarities with constant-depth random quantum circuits but crucially allows for direct calculations of higher order moments of its output distribution. Using mean-field (large-n) techniques, we fully characterize the output distributions of Brownian circuits at shallow depths and show that they follow a Porter-Thomas distribution, just like in the case of deep circuits, but with a truncated Hilbert space. The access to higher order moments allows for studying the expected and typical Linear Cross-entropy (XEB) benchmark scores achieved by an ideal quantum computer versus the state-of-the-art classical spoofers for shallow Brownian circuits. We discover that for these circuits, while the quantum computer typically scores within a constant factor of the expected value, the classical spoofer suffers from an exponentially larger variance. Numerical evidence suggests that the same phenomenon also occurs in constant-depth discrete random quantum circuits, like those defined over the all-to-all architecture. We conjecture that the same phenomenon is also true for random brickwork circuits in high enough spatial dimension.
Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary?
We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of logn/log(9/4)≈0.855log2n layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness.
At a larger logarithmic depth, we prove, in the real-RAM model, average-case #P-hardness of estimating output probabilities to additive error 2−O(nlog2n) on any fixed fraction of instances above 3/4. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite 192-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and O(nlogn) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N scale, where N=(n/2n), required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.