Shallow circuits, no parity, proved at last?
Two AI preprints claim that parity is not in QAC⁰, Moore’s 1999 conjecture
Covers result 274 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.
3:32. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
Parity asks whether a string of bits has an odd number of ones, so every bit matters. In the 1980s, Ajtai, Furst, Saxe and Sipser, and then Håstad, proved that classical circuits of constant depth and polynomial size, with NOT gates and unlimited AND and OR gates, cannot compute it.
Quantum circuits of constant depth and polynomial size, with one-qubit gates and giant Toffoli gates, form the class called QAC⁰. In 1999 Cristopher Moore conjectured that they cannot copy a bit onto many wires, which is equivalent to computing parity: Hadamard gates turn one into the other. With a fan-out gate, parity takes depth 3 for any number of bits; without it, a tree of CNOT gates needs a new layer every time the number of bits doubles. Partial results piled up, with lower bounds for few extra qubits and for depths 2, 3 and 4. In 2024 a claimed proof was withdrawn within a week, and four days after the new papers’ date a human preprint still called the general case open.
Result 274 is two OpenAI preprints, 48 pages, both dated September 24, 2026, with independent proofs. They claim that for any fixed depth and polynomially many qubits, with extra qubits starting at zero, one qubit measured and everything else discarded, no circuit gets parity right on every input with any fixed advantage over guessing, once the number of bits is large enough. Using reductions by Xu and Li, majority is ruled out too.
What it doesn’t claim
Circuits with fan-out gates or intermediate measurements, or with more than polynomially many qubits, where depth 7 circuits are known to approximate parity. The threshold on the number of bits is not explicit.
Where it stands
- Posted as preprints
- OpenAI, two papers, 48 pages, dated September 24, 2026
- Peer reviewed
- Not yet
- Formalized in Lean
- In part: the main theorem, not the majority result (docs)
Last checked October 19, 2026. The preprints have not been revised. The first paper’s main theorem is formalized in Lean at full strength, about 3,600 lines with no unproved steps, which we did not build; the majority result is not. OSVerify has not reviewed them. Scott Aaronson called the problem “one of the great questions of quantum complexity theory since 1999”, but we found no technical comment from specialists.
How the proofs go
- Mirrors and mismatches. The first proof treats every Toffoli as a reflection about a product state. Its key structural theorem bounds how far a shallow stack of such reflections can push a product pattern: many mismatches are astronomically unlikely. Parity needs exactly the opposite, a transition from every input qubit agreeing to every input qubit disagreeing. Where polynomial approximations fail, the proof runs the circuit backwards at a larger scale, through a finite chain of scales.
- A second, independent proof. The second paper prunes gates that almost never fire and follows regular trajectories.
The numbers in the video
- Ours: with a fan-out gate, parity in depth 3 for any number of bits; a CNOT tree needs depth ⌈log₂ n⌉.
- Ours: one Toffoli touching every input has correlation with parity of only 21−n, like a classical AND gate.
- Ours: the identity behind the first proof (parity as an average transition between opposite product states), checked for 3 to 5 bits.
Read the source
- Product-Projection Localization and the QAC⁰ Parity Lower Bound (PDF), 21 pages.
- Regular Trajectories, Pruning and Quantum Parity (PDF), 27 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 274.
The 2 papers in this result
OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.
Transcript
Read the full script
0:00The question
Parity asks whether a string of bits has an odd number of ones, so every bit matters. In the 1980s, Ajtai, Furst, Saxe and Sipser, and then Håstad, proved that classical circuits of constant depth and polynomial size, with NOT gates and unlimited AND and OR gates, cannot compute it. Quantum circuits of constant depth and polynomial size, with one-qubit gates and giant Toffoli gates, form the class called QAC⁰. In 1999 Cristopher Moore conjectured that they cannot copy a bit onto many wires, which is equivalent to computing parity: Hadamard gates turn one into the other. Our computer shows the difference: with a fan-out gate, parity takes depth 3 for any number of bits; without it, a tree of CNOT gates needs a new layer every time the number of bits doubles. Partial results piled up: lower bounds with few extra qubits, and for depths 2, 3 and 4. In 2024 a claimed proof was withdrawn within a week. Four days after the new papers’ date, a human preprint still called the general case open.
1:08The claims
Result 274 is two OpenAI preprints, 48 pages, both dated September 24, 2026, with independent proofs. They claim that for any fixed depth and polynomially many qubits, with extra qubits starting at zero, one qubit measured and everything else discarded, no circuit gets parity right on every input with any fixed advantage over guessing, once the number of bits is large enough. Using reductions by Xu and Li, majority is ruled out too. Giant gates alone do not help much. Our computer finds that one Toffoli touching every input has correlation with parity of only 2^(1−n), halving with every extra bit, exactly like a classical AND gate. Not claimed: circuits with fan-out gates or intermediate measurements, or with more than polynomially many qubits, where depth 7 circuits are known to approximate parity. The threshold on the number of bits is not explicit.
2:11How the proofs go
The first proof treats every Toffoli as a reflection about a product state. Its key structural theorem bounds how far a shallow stack of such reflections can push a product pattern: many mismatches are astronomically unlikely. Parity needs exactly the opposite, a transition from every input qubit agreeing to every input qubit disagreeing, and our computer checks the identity behind this. Where polynomial approximations fail, the proof runs the circuit backwards at a larger scale, through a finite chain of scales. The second proof takes a different route: it prunes gates that almost never fire and follows regular trajectories.
2:51Where it stands
The preprints are unrefereed and unchanged since release. The first paper’s main theorem is formalized in Lean at full strength, about 3,600 lines with no unproved steps, which we did not build; the majority result is not. OSVerify has not reviewed them. Scott Aaronson called the problem one of the great questions of quantum complexity theory since 1999, but we found no technical comment from specialists. If they hold, Moore was right: quantum circuits of constant depth and polynomial size cannot compute parity on large inputs, or copy one bit onto every wire.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.