Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > QAC0:
Reports tagged with QAC0:
TR26-258 | 18th October 2026
Minbo Gao, Zhengfeng Ji, Chenghua Liu

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

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, ... more >>>




ISSN 1433-8092 | Imprint