{"id":"arxiv/2609.40100","url":"https://arxiv.org/abs/2609.40100","tags":["quant-ph"],"score":0,"title":"Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness","domain":"quant-ph","source":"arxiv","authors":["Natansh Mathur","Iordanis Kerenidis"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}