1 · The essentials
Parity asks whether a list of zeros and ones contains an odd number of ones. The result concerns quantum circuits that use a fixed number of processing layers, even as the input grows. These circuits may perform arbitrary operations on individual quantum bits and use a specified kind of operation involving arbitrarily many quantum bits at once. Even with a total number of quantum bits bounded by a polynomial in the input length, they cannot answer the parity question with a fixed positive advantage over guessing on every input. The extra quantum bits must start at zero, and the answer is obtained by measuring just one quantum bit; everything else may be discarded. The manuscripts have Lean formalizations and describe this result as resolving Moore's parity conjecture in this measured-output setting.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a workshop that must report whether an odd number of switches are on, but has only a fixed number of rounds to process them. Adding more workspace and allowing certain very large operations still does not make every task possible within those rounds. The image is only a guide: the result depends on the exact quantum operations and output rules allowed.
Why it matters
The result identifies a limit on constant-depth quantum computation even when some gates can involve arbitrarily many qubits. It also allows all non-output registers to be discarded, so the obstruction does not require a tidy final workspace. The repository summary further states that Xu–Li's reductions give the same bounded-error obstruction for strict majority.
2 · Going further
The precise problem is to compute parity using constant-depth circuits with arbitrary one-qubit gates and unbounded-arity Toffoli gates, while using polynomially many total qubits. Ancillary qubits are initialized to , a single output qubit is measured, and all other final registers are unrestricted and may be discarded. The lower bound rules out any fixed for which such circuits would return the correct parity with probability at least on every input.
Both abstracts describe this as resolving Moore's parity conjecture in the measured-output model. The output condition is part of the statement: the circuits need not restore their workspace or satisfy any restriction on the discarded registers. The repository summary also attributes an extension of the bounded-error obstruction to strict majority to Xu–Li's reductions.
The main manuscript is titled “Product-projection localization and the QAC0 parity lower bound,” while the companion is titled “Regular trajectories, pruning and quantum parity.” These titles point to product-projection localization and to regular trajectories and pruning, respectively, but the supplied abstracts do not explain those methods or their logical relationship. Both manuscripts state the same parity lower bound and are marked Lean-formalized; the supplied text does not give a finer account of what each formalization covers.
Useful notions
- Parity of a binary input
- Quantum bits and measurement
- Circuit gates and depth
- Polynomial resource bounds
- Worst-case success probability
What was known before / what is new
Before
The source identifies Moore's parity conjecture as the problem being resolved in the measured-output model. It supplies no account of earlier partial results or the conjecture's history. It also names Xu–Li's reductions as the route from the parity obstruction to the strict-majority obstruction.
New
The main result rules out a fixed positive worst-case advantage for parity in the stated constant-depth quantum circuit model with polynomially many total qubits. It permits unrestricted final garbage, rather than imposing conditions on the registers that are not measured. Both supplied manuscripts state this result and are marked Lean-formalized.
Limits and assumptions
The hypotheses are constant depth, arbitrary one-qubit gates and unbounded-arity Toffoli gates, polynomially many total qubits, zero-initialized ancillas, and measurement of one output qubit. The conclusion concerns a fixed positive advantage on every input; it does not state an obstruction for advantages that shrink with input length or for success averaged over inputs. The main result has a Lean formalization, and both manuscripts are labeled Lean-formalized, but the supplied material does not specify the detailed verification scope or separately establish formalization of the strict-majority consequence. No remaining open problems are listed, and the source gives no conclusion for models outside the stated hypotheses.
Mini glossary
- Parity —
- Whether the number of ones in a binary input is odd or even.
- Constant depth —
- A bound on the number of circuit layers that stays fixed as the input length grows.
- Ancilla —
- An extra quantum bit used by the circuit, required here to start in the zero state.
- Worst-case advantage —
- The amount by which the success probability exceeds one half on every input.
- Measured-output model —
- The setting here in which one output qubit is measured and all other final registers may be discarded without restriction.
- Polynomially many total qubits —
- A total qubit count bounded by a polynomial in the input length, including the ancillary qubits.
Keywords : Quantum circuit lower bounds · Parity · QAC0
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Product-projection localization and the QAC0 parity lower bound
24/09/2026We 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
24/09/2026We 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 , 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.