pipette
ENEnglish

Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness

Natansh Mathur, Iordanis Kerenidis

Preprint

En palabras de los autores

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 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 -hardness of estimating output probabilities to additive error on any fixed fraction of instances above . 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 -gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the scale, where , required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.