REVIEW
Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
Quantum Physics · Submitted 30 Sep 2026 · 51 references
Pith's verdict: The anticoncentration half is a clean, self-contained result; the hardness half is standard and plausible but genuinely conditional on exact-real arithmetic, and the authors say so clearly.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Random matching layers on a paired magic fermionic input reach Haar-scale output spread at the sharp threshold $\log n/\log(9/4) \approx 0.855\log_2 n$ layers, and at larger logarithmic depth estimating output probabilities is…
The reading
What carries the argument
The engine is the collision chain. Two copies of the state, Howe duality between the $GL_n$ and $GL_2$ actions, and permutation symmetry reduce the collision probability, which lives in an exponentially large many-particle space, to a reversible Markov chain on the $k+1$ sectors $r = |S\cap T|$ counting common occupied modes between the two copies; Hahn polynomials diagonalize the transition matrix. The chain splits the causes cleanly: the eigenvalues $\lambda_j$ depend only on the gate ensemble ($\lambda_1 \approx 2/3$, $\lambda_2 \approx 4/9$), while the spectral coefficients $c_j(\Psi)$ depend only on the input. For an occupation-basis input $c_1\sim n$, so the slowest mode dominates; for the paired magic input $c_1$ is bounded by a constant and $c_2 \sim 3n/2$, so at the scale $n(4/9)^t = \Theta(1)$ the slowest contribution has vanished and the second mode sets the transition, with the sum of even modes producing $e^{3z/2}$. A separate three-state chain on two-particle correlations yields the matching lower bound that excludes earlier crossings without assuming monotonicity. The hardness side runs on different machinery: postselected type-I fusion in four native layers turns the magic blocks into a universal graph-state computation, swap-network routing lemmas embed that circuit into typical matching schedules, and gatewise Cayley paths with a rational linear-program decoder interpolate from Haar gates to the hard endpoint.
Extended reading notes
Core claim
The central claim is that one and the same shallow ensemble — independent uniform perfect matchings with independent Haar $U(2)$ gates on the paired magic input $(|0011\rangle+|1100\rangle)^{\otimes B}$ — carries both guarantees. The normalized collision ratio $R_{n,t}$ drops to any fixed multiple $q>1$ of the passive-Haar benchmark at depth $\log n/\log(9/4) + O_q(1)$, with the uniform-limit profile $R_{n,t}/R_{\mathrm{Haar}}(n) \to e^{3z/2}$ in the window $z=n(4/9)^t = \Theta(1)$; a two-particle-correlation lower bound shows no substantially earlier depth has bounded collision. At depth at least $6.5\log_2 n + 9$, estimating the probability of a fixed half-filled output to additive error $2^{-O(n\log^2 n)}$ on at least a $3/4+\gamma$ fraction of instances suffices to solve $\#\mathrm{P}$ in randomized polynomial time in the real-RAM model. Everything about the collision survives verbatim when the Haar gates are replaced by a uniform draw from a finite 192-gate alphabet, and classical output relabeling upgrades the collision bound to anticoncentration at each fixed output. The paper is explicit that the accuracy proved is finer than the $1/N$ scale sampling-to-counting needs, so hardness of sampling within constant total-variation distance remains open.
Load-bearing premise
The load-bearing premise is the hardness half's exact-arithmetic model: the reduction assumes Haar samples, circuit queries, and real arithmetic are exact, and the paper explicitly leaves transferring this to a finite-precision physical ensemble as future work — if that idealisation cannot be met, the $\#\mathrm{P}$-hardness conclusion does not reach a real device.
Editorial extensions
If this is right
- A constant collision ratio — the standard sufficient criterion for anticoncentration — holds from depth $\approx 0.855\log_2 n$ onward using only $O(n\log n)$ two-mode gates.
- The input decides the relaxation scale: an occupation-basis input keeps a large collision even under full Haar randomness, so the paired magic input is doing essential work, not the gate randomness alone.
- The collision law is preserved exactly by a finite 192-gate alphabet of single-particle Clifford gates with eighth-root phases, so the anticoncentration guarantee holds for a discrete, physically implementable gate set.
- At logarithmic depth above $6.5\log_2 n$, estimating a fixed output probability to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction above $3/4$ is average-case $\#\mathrm{P}$-hard, under the exact-arithmetic real-RAM premise the paper does not claim to instantiate physically.
- Hardness of sampling to constant total-variation distance does not follow from these results, and the authors state that this gap remains open.
Reading between the lines
- Editorial inference: the input-versus-ensemble separation suggests a general screening test for shallow anticoncentration — inspect which spectral coefficients of a candidate input grow with $n$ rather than demand convergence of the whole state ensemble to Haar; other non-Gaussian inputs could be tested this way.
- Editorial inference: if the real-RAM premise is dropped, the hardness half may weaken or fail, whereas the collision half is exact and quantitative, so the two halves of the paper have very different robustness profiles — a useful distinction for anyone planning to rely on one guarantee or the other.
- Editorial inference: the constant $0.855$ is inherited from the second eigenvalue $(4/9)^t$ of the matching chain; a different pairing architecture with a faster-relaxing matching distribution would push the threshold lower, turning the search for better shallow architectures into a concrete optimization problem.
- Editorial inference: the padding and embedding failure bounds make the hardness statement purely asymptotic ($n$ above about $2^{32.4}$ modes); an experiment-minded reader should prefer the deterministic Bene\u0161-prefix variant, which the paper shows removes embedding failure entirely, or await a tighter embedding analysis.
Original abstract
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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Sampling problems give some of the clearest conditional separations between quantum and classical computation. | background 1.00 | 0.05 | 0.02 | asserted 0.94 |
| s1 | In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. | background 0.97 | 0.07 | 0.02 | asserted 0.98 |
| s2 | Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. | background 0.98 | 0.11 | 0.04 | asserted 1.00 |
| s3 | A natural open question is whether linear depth is necessary? | gap 1.00 | 0.04 | 0.02 | unclear 0.80 |
| s4 | We show that logarithmic depth suffices for both guarantees in the same ensemble. | result 0.68 | 0.96 | 0.88 | asserted 1.00 |
| s5 | 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. | result 0.99 | 0.92 | 0.24 | asserted 1.00 |
| s6 | The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. | interpretation 0.94 | 0.81 | 0.04 | asserted 1.00 |
| s7 | An occupation-basis input retains large collision even under full Haar randomness. | result 0.83 | 0.60 | 0.02 | asserted 1.00 |
| s8 | 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$. | result 0.88 | 0.94 | 0.19 | asserted 1.00 |
| s9 | We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. | method 0.96 | 0.94 | 0.04 | asserted 1.00 |
| s10 | A finite $192$-gate alphabet preserves the collision law exactly. | result 0.82 | 0.85 | 0.04 | asserted 1.00 |
| s11 | 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. | result 0.50 | 0.93 | 0.53 | asserted 1.00 |
| s12 | 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. | limitation 0.96 | 0.81 | 0.05 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2609.40100 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.