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 $\log n/\log(9/4)\approx0.855\log_2 n$ 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 $\#\mathsf{P}$-hardness of estimating output probabilities to additive error $2^{-O(n\log^2 n)}$ 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(n\log n)$ gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the $1/N$ scale, where $N=\binom{n}{n/2}$, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
AI Summary
The paper asks whether Fermion Sampling needs linear-depth passive dynamics to obtain anticoncentration and average-case hardness of output-probability estimation. It studies a product of four-mode non-Gaussian states $(|0011\rangle+|1100\rangle)/\sqrt2$, followed by independent uniform perfect matchings with independent Haar $U(2)$ gates.
For $N=\binom{n}{n/2}$, the normalized expected collision $N\mathbb E\sum_y p_y^2$ reaches any fixed factor above its passive-Haar benchmark at depth $\log n/\log(9/4)+O(1)\approx0.855\log_2 n$. The benchmark tends to $2$, and the Haar-relative collision converges to $e^{3z/2}$ for bounded $z=n(4/9)^t$, while collision diverges when $z\to\infty$. Two-copy representation theory reduces the calculation to an $n/2+1$-state reversible chain diagonalized by Hahn polynomials. Input-dependent spectral weights suppress the slowest mode; two-particle correlations provide the matching lower bound. A 192-gate alphabet preserves the collision law exactly, and uniform classical output relabeling yields fixed-output anticoncentration.
At a larger $O(\log n)$ depth, bounded by $6.5\log_2 n+9$, probability estimation to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction above $3/4$ is average-case $\#\mathsf P$-hard in the real-RAM model. The reduction embeds four-layer postselected hard circuits into typical schedules and uses Cayley-path interpolation with a rational linear-program decoder.
Depth assumes native arbitrary-pair fermionic gates; preparation, physical routing, and noise are separate. The hardness reduction has substantial padding, does not establish hardness for the finite alphabet, and requires accuracy finer than the $1/N$ scale. Constant-total-variation sampling hardness remains open.
Little sign of AI-generated textAI use disclosedStrong assumptions
Claude Opus 5.5 and ChatGPT 6 Astra were extensively used during the research process to explore and refine proof ideas, formalize the proofs, and to perform numerical verifications.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks whether Fermion Sampling needs linear-depth passive dynamics to obtain anticoncentration and average-case hardness of output-probability estimation. It studies a product of four-mode non-Gaussian states (∣0011⟩+∣1100⟩)/2, followed by independent uniform perfect matchings with independent Haar U(2) gates.
For N=(n/2n), the normalized expected collision NE∑ypy2 reaches any fixed factor above its passive-Haar benchmark at depth logn/log(9/4)+O(1)≈0.855log2n. The benchmark tends to 2, and the Haar-relative collision converges to e3z/2 for bounded z=n(4/9)t, while collision diverges when z→∞. Two-copy representation theory reduces the calculation to an n/2+1-state reversible chain diagonalized by Hahn polynomials. Input-dependent spectral weights suppress the slowest mode; two-particle correlations provide the matching lower bound. A 192-gate alphabet preserves the collision law exactly, and uniform classical output relabeling yields fixed-output anticoncentration.
At a larger O(logn) depth, bounded by 6.5log2n+9, probability estimation to additive error 2−O(nlog2n) on any fixed fraction above 3/4 is average-case #P-hard in the real-RAM model. The reduction embeds four-layer postselected hard circuits into typical schedules and uses Cayley-path interpolation with a rational linear-program decoder.
Depth assumes native arbitrary-pair fermionic gates; preparation, physical routing, and noise are separate. The hardness reduction has substantial padding, does not establish hardness for the finite alphabet, and requires accuracy finer than the 1/N scale. Constant-total-variation sampling hardness remains open.
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.
We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anticoncentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes.An understanding of the conditions for anticoncentration is important for determining which quantum circuits are difficult to simulate classically, as anticoncentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation.Our definition of anticoncentration is that the expected collision probability of the distribution-that is, the probability that two independently drawn outcomes will agree-is only a constant factor larger than the collision probability for the uniform distribution.We show that when the two-local gates are each drawn from the Haar measure (or any 2-design), at least (n log(n)) gates (and thus (log(n)) circuit depth) are needed for this condition to be met on an n-qudit circuit.In both the case where the gates are nearest neighbor on a one-dimensional ring and the case where gates are long range, we show that O(n log(n)) gates are also sufficient and we precisely compute the optimal constant prefactor for the n log(n).The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical-mechanical model, which we manage to bound using stochastic and combinatorial techniques.
We consider the hardness of computing additive approximations to output probabilities of random quantum circuits. We consider three random circuit families, namely, Haar random, p=1 QAOA, and random IQP circuits. Our results are as follows. For Haar random circuits with m gates, we improve on prior results by showing coC=P hardness of average-case additive approximations to an imprecision of 2−O(m). Efficient classical simulation of such problems would imply the collapse of the polynomial hierarchy. For constant depth circuits i.e., when m=O(n), this linear scaling in the exponent is within a constant of the scaling required to show hardness of sampling. Prior to our work, such a result was shown only for Boson Sampling in Bouland et al (2021). We also use recent results in polynomial interpolation to show coC=P hardness under BPP reductions rather than BPPNP reductions. This improves the results of prior work for Haar random circuits both in terms of the error scaling and the power of reductions. Next, we consider random p=1 QAOA and IQP circuits and show that in the average-case, it is coC=P hard to approximate the output probability to within an additive error of 2−O(n). For p=1 QAOA circuits, this work constitutes the first average-case hardness result for the problem of approximating output probabilities for random QAOA circuits, which include Sherrington-Kirkpatrick and Erdös-Renyi graphs. For IQP circuits, a consequence of our results is that approximating the Ising partition function with imaginary couplings to an additive error of 2−O(n) is hard even in the average-case, which extends prior work on worst-case hardness of multiplicative approximation to Ising partition functions.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood. We develop a common framework for classical simulation of boson and fermion sampling under thermal loss, including pure loss. For Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing, and fermion sampling with magic inputs, we obtain polynomial-time sampling at inverse-polynomial total variation error, for any fixed nonzero overall loss rate, and with high probability over Haar-random interferometers. A milder flatness assumption on the ideal output distribution suffices for quasipolynomial-time simulation without Haar randomness. With constant thermal loss per layer, the same flatness assumption gives polynomial-time simulation at logarithmic depth. Our bounds for Fock-state boson sampling cover both dilute and saturated regimes and become stronger near full input filling: when only a bounded number of input modes are empty, the noisy output for Haar-random interferometers converges, as the number of modes grows, to a distribution independent of the interferometer.
Anticoncentrated n-bit distribution from log(n) qubits
Random circuit sampling (RCS) is a leading approach to demonstrate quantum advantage, with its believed classical hardness rooted in anticoncentration of output distributions and average-case hardness of probability estimation. Here we show that this association is not fundamental. We introduce holographic random circuit sampling (HRCS), a spatiotemporal protocol that interleaves random unitary evolution with mid-circuit measurements. We prove that n classical bits exhibiting ε-approximate anticoncentration of Haar random states can be generated using only O(logn) physical qubits and linear depth, establishing a precise space-time trade-off and indicating efficient classical simulation. Our analyses is built upon exact formulas for collision probability and higher-order power sums. Our experimental validation on IBM Quantum devices demonstrates sampling up to 200 classical bits using only 20 qubits.