Browse › Mathematical physics › 274 Parity is not in QAC0
Regular trajectories, pruning and quantum parity
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 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.
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). Simplifies the companion localization proof, and for its direct layer-removal step uses the outside-support factorization from this paper's Proposition 4.1. [family-level]
- Shiva Kintali, PARITY ∉ QAC⁰ (via Polarization and Direct Induction) (preprint, dated 17 October 2026). Simplifies the companion localization paper's proof by polarization and direct induction, and cites this paper as a different proof of the parity bound via regular trajectories and pruning. [family-level]
Formalization
- OpenAI math release, Lean scope notes for family 274 (lean/docs/274.md, October 2026). Formalizes the general positive-advantage parity lower bound (RegularParity.lean comparator), its success-below-2/3 specialization and product-projection localization; the notes state that regular-trajectory propagation and pruning are not separate formalized statements. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Ashley Montanaro, Changpeng Shao, Dominic Verdon, Low-degree approximation of QAC⁰ circuits (arXiv:2411.00976, v1 1 November 2024, withdrawn in v2 on 7 November 2024). An earlier claimed proof of the statement of Theorem 1 here via low-degree approximation; it was withdrawn with the comment "Lemma 2.1 is incorrect, and we need some time to fix it".
- Yangjing Dong, Fengning Ou and Penghui Yao, On the Computational Power of Geometrically Local QAC circuits (arXiv:2604.07178v2, 2026-09-30). Studies geometrically local versions of the circuit model and relates a stronger polynomial-size parity width lower bound to the parity exclusion claimed by this family. [family-level]
Digests and expositions
- AI Proved What?, Shallow circuits, no parity, proved at last? (episode 274, October 2026). Provides a short video and transcript outlining the measured-output claim, product-projection localization and the companion pruning argument. [AI-generated per source] [family-level]
Elsewhere
- Emergent Mind: family 274
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Regular-trajectories-pruning-and-quantum-parity-September-24-2026,
author = {{OpenAI}},
title = {{Regular trajectories, pruning and quantum parity}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Regular-trajectories-pruning-and-quantum-parity-September-24-2026/paper.pdf}{OAI:Regular-trajectories-pruning-and-quantum-parity-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:
- Product-projection localization and the QAC0 parity lower bound · September 24, 2026