Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-258 | 18th October 2026 16:19

A simplified proof of PARITY $\notin$ QAC$^0$

RSS-Feed




TR26-258
Authors: Minbo Gao, Zhengfeng Ji, Chenghua Liu
Publication: 18th October 2026 16:25
Downloads: 52
Keywords: 


Abstract:

We give a simplified, self-contained proof of OpenAI's parity lower bound for constant-depth quantum circuits with arbitrary one-qubit gates, unbounded-arity Toffoli gates, and polynomially many ancillas. The proof establishes product-projection localization and uses it to bound the parity Fourier coefficient of the acceptance probability. We remove one circuit layer directly, avoiding intermediate low-count propagation. This yields a leakage recurrence that closes by induction over depth and threshold scales.



ISSN 1433-8092 | Imprint