Parity is not in \mathrm{QAC}^{0}

Resolves Moore's parity conjecture in the measured-output model: constant-depth quantum circuits with arbitrary one-qubit gates, unbounded-arity Toffoli gates and polynomially many total qubits cannot compute parity with any fixed positive worst-case advantage. Ancillas start in zero, one output qubit is measured, and all other registers may be discarded. Xu–Li's reductions give the same bounded-error obstruction for strict majority. (Lean)

Manuscripts (2)

Product-projection localization and the QAC0 parity lower bound

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026}

We prove that constant-depth quantum circuits with arbitrary one-qubit and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many qubits. Ancillas start in zero, only one output qubit is measured, and all final garbage is unrestricted. This resolves Moore's parity conjecture in the measured-output model.

Regular trajectories, pruning and quantum parity

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Regular-trajectories-pruning-and-quantum-parity-September-24-2026}

We prove that constant-depth quantum circuits with arbitrary one-qubit gates and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many total qubits. Ancillary qubits are initialized to |0\rangle, one output qubit is measured, and all other final registers may be discarded without restriction. This resolves Moore's parity conjecture in the measured-output model.

Result 274 · Mathematical physics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.