Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
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)≈0.855log2 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 #P-hardness of estimating output probabilities to additive error 2−O(nlog2 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(nlog n) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N scale, where N=binomnn/2, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
Related
- Anticoncentration and entanglement in Gaussian boson sampling
- Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
- Average-case hardness of Betti number estimation
- On Certifying Source Sampling Hardness in Quantum Generative Modeling
- Polynomial-time classical simulation of boson and fermion sampling under thermal loss
BibTeX
@misc{mathur2026logarithmicdepth,
title = {{Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness}},
author = {Natansh Mathur and Iordanis Kerenidis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40100},
eprint = {2609.40100},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40100},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
AU - Natansh Mathur
AU - Iordanis Kerenidis
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40100
UR - https://arxiv.org/abs/2609.40100
AB - 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)≈0.855log_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 #P-hardness of estimating output probabilities to additive error 2^−O(nlog^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(nlog n) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N scale, where N=binomnn/2, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
ER -