Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
Diese Arbeit zeigt, dass Schaltungen mit logarithmischer Tiefe mit passiver linearer Optik und nicht-gaußschen Magic-Inputs ausreichen, um sowohl Antikonzentration als auch durchschnittliche -Härte für das Fermionen-Sampling zu erreichen, wodurch die zuvor erforderlichen Konstruktionen mit linearer Tiefe und quadratischer Größe mittels einer Haar-zufälligen globalen Konstruktion durch eine Gate-Komplexität von ersetzt werden.