oai-math-revised beta

Browse › Mathematical physics › 274 Parity is not in QAC0

Product-projection localization and the QAC0 parity lower bound

OpenAI · September 24, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

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.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Follow-up works

  • Minbo Gao, Zhengfeng Ji, Chenghua Liu, A simplified proof of PARITY ∉ QAC⁰ (ECCC TR26-258, 18 October 2026). Presents itself as a self-contained simplification of this paper's localization proof: it replaces the low-count enumeration and three-factor propagation of Lemmas 5–6 here with a direct layer-removal argument (citing the companion paper's Proposition 4.1), and keeps the zero-count polynomial, the inverse-circuit argument and the parity reduction. [family-level]
  • Shiva Kintali, PARITY ∉ QAC⁰ (via Polarization and Direct Induction) (preprint, dated 17 October 2026). Gives a self-contained simplification of this paper's proof: polarization writes the reflection expansion as a linear combination of product projections with coefficient cost 18^k, which replaces the intermediate low-count propagation while keeping the localization framework and the inverse-circuit bootstrap; the companion paper is cited as a different proof. [family-level]

Formalization

  • OpenAI math release, Lean scope notes for family 274 (lean/docs/274.md, October 2026). Describes the release's Lean formalization of the measured-output parity lower bound for every fixed positive worst-case advantage and polynomial total-qubit bound (plus a specialization to success below 2/3) and the product-projection localization estimate, with comparator statements in QACParity.lean and RegularParity.lean. [family-level]

Possibly relevant literature (found by the agent, not checked)

Digests and expositions

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026,
  author = {{OpenAI}},
  title = {{Product-projection localization and the $\mathrm{QAC}^0$ parity lower bound}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026/paper.pdf}{OAI:Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/274.md. The Lean statements have not been checked by people against the paper's claims.

Family 274: Parity is not in QAC0

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.

Other papers in this family: