Parity is not in QAC0 (Moore's parity conjecture)

$\mathrm{QAC}^0$ is the class of constant-depth quantum circuits on polynomially many qubits built from arbitrary one-qubit unitaries and Toffoli gates with unboundedly many controls, gates in a layer acting on disjoint qubits. Classically parity is not in $\mathrm{AC}^0$ (Furst-Saxe-Sipser, Ajtai, Hastad). Moore introduced these quantum classes in 1999 and related coherent parity to unbounded fanout; he conjectured that parity cannot be computed in $\mathrm{QAC}^0$ . Prior lower bounds needed restrictions on the number of ancillas or on the entangling depth. Can a constant-depth quantum circuit of this kind, with polynomially many zero-initialized ancillas, compute the parity of $n$ input bits with bounded error?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Quantum circuit complexity; constant-depth lower bounds
Posed by: Cristopher Moore (Quantum circuits: fanout, parity, and counting, arXiv quant-ph/9903046, 1999)
Year posed: 1999
Years open: 27y
Solved: 2026-09-24
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 40 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Claims: for every fixed depth $d$ , every $c\ge1$ and every $0<\varepsilon\le1/2$ , for all large $n$ no depth- $d$ circuit of one-qubit unitaries and unbounded-arity Toffoli gates on at most $n^c$ qubits, ancillas starting in $|0\rangle$ and one output qubit measured, computes parity with probability at least $1/2+\varepsilon$ on every input. Taking $\varepsilon=1/6$ gives bounded error $2/3$ . The companion paper gives a second proof via regular trajectories and pruning; via Xu-Li reductions the same obstruction holds for strict majority. It does not cover circuits with intermediate measurements, postselection or primitive fanout gates, and gives no explicit size-depth tradeoff beyond polynomial size.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. Two manuscripts dated the same day give two different proofs of the same bound.

Verification

No independent mathematician has checked this yet. Checked here: abstracts, introduction and Theorem 1.1 of the principal manuscript, read against Moore's conjecture as cited. The proofs were not refereed. Scope stated by the paper: unitary circuits with no intermediate measurement, postselection or primitive fanout gate; one measured output qubit, garbage unrestricted; Moore's original clean-ancilla model is covered as a special case. Lean-checked: the release's formalization catalogue lists comparator config ComparatorChallenges/QACParity.json with declaration OAI.QAC.parity_lower_bound (plus RegularParity.json, OAI.QAC.parity_lower_bound_polynomial_size). The statement was read here: for every depth d, exponent c >= 1 and 0 < eps <= 1/2, for all large n, no circuit of at most d disjoint layers of one-qubit unitaries and multi-control Toffolis on at most n^c qubits succeeds with probability >= 1/2 + eps on every input, success being the Born probability of the parity value on the measured qubit summed over all garbage. That is the headline claim. Not rebuilt here.

Parity is not in QAC0 (Moore's parity conjecture)

What was actually shown

What the AI did

Verification

Sources

Discussion