Parity is not in QAC⁰

The explanation

Take the bit string 1011. Its parity is 1, because it holds an odd number of ones. Flip any single bit and the parity flips too. So a parity circuit must combine information from every input bit.

A circuit's depth is its number of layers of gates. Shallow classical circuits of AND, OR and NOT gates cannot compute parity. Furst, Saxe and Sipser, and separately Ajtai, proved this in the early 1980sSource 1. Moore introduced the matching quantum circuit classes and linked parity to fanoutSource 2. Fanout copies one bit onto many others at once.

The quantum class is called QAC0. Its circuits have constant depth and polynomially many qubits. For 100 input bits, a polynomial bound might allow 100² = 10,000 qubits in total. The gates are any one-qubit gates plus Toffoli gates. A Toffoli gate flips a target qubit when all of its control qubits are 1. It may have any number of controls. Gates in one layer must not share qubits. So one qubit cannot control many gates at once.

The new theorem covers every fixed depth and every polynomial bound on qubits. For large enough n, no such circuit computes parity with any fixed positive worst-case advantageSource 3. Worst-case advantage ε means the answer is right with chance at least 1/2 + ε on every input. A coin toss already gets 1/2. Taking ε = 1/6 gives the usual threshold of 2/3Source 4. Extra qubits start at zero, only one qubit is measured, and the rest may end in any stateSource 3. The result resolves Moore's parity conjecture in this measured-output modelSource 5. It also rules out coherent fanout in constant depthSource 6.

Earlier work needed limits. Some bounds required exact answers, at most a few layers, or few extra qubits. Anshu, Dong, Ou and Yao allowed a little more than n extra qubits at each fixed depthSource 7. The new theorem drops all of these restrictions.

The main obstacle is the unbounded Toffoli gate. One such gate can touch every input, so counting wires gives no boundSource 8. The first paper uses product projections, which fix one chosen state on each of some qubits. It shows a shallow circuit almost never moves a state from zero mismatches to many mismatches with such a fixed pattern. The second paper reaches the same theorem another way, through pruning along regular trajectoriesSource 9. Neither structural theorem is used to prove the otherSource 9. The theorem holds only eventually: it allows exceptions at small input sizesSource 10.

How sure is this? Lean, a computer proof checker, has a formal proof of the parity bound. It covers every fixed depth, polynomial qubit bound and advantage. It also covers the 2/3 specialization and the product-projection estimate. The regular-trajectory and pruning steps of the second paper are not separate Lean statements. No specialist review has been published.

What it doesn't show. This does not cover circuits with fanout gates, intermediate measurements or postselection, and it gives no bound for small input sizes.