Why shallow quantum circuits cannot compute parity

← All digests

Family 274 · Mathematical physics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

Given a string of bits, parity asks whether the number of ones is odd or even. Its definition is elementary:

$$\operatorname{PARITY}_n(x)=x_1\oplus\cdots\oplus x_n,$$

where $\oplus$ means addition modulo two. Flipping any one input flips the answer. This makes parity a useful test of whether a computation can combine information from every input.

Quantum circuits can use superpositions and interference, so classical circuit lower bounds do not automatically apply. Moreover, the shallow quantum model considered here includes gates acting on arbitrarily many qubits at once. A simple argument that information can reach only a small number of wires therefore fails.

Family 274 contains two manuscripts claiming that these resources still cannot compute parity at constant depth with polynomially many qubits and any fixed positive worst-case advantage over guessing. They allow the inputs to be destroyed and arbitrary unwanted final states to be discarded. Only one measured output bit needs to be correct.

2. Background and essential definitions

The circuit model

A qubit has state space $\mathbb C^2$, with basis $|0\rangle,|1\rangle$. An $N$-qubit system has tensor-product space $(\mathbb C^2)^{\otimes N}$. Gates are unitary linear transformations, preserving inner products and total probability.

The allowed gates are arbitrary one-qubit unitaries and generalized Toffoli gates. A Toffoli gate with controls $z_1,\ldots,z_t$ and target $b$ acts as

$$|z_1,\ldots,z_t,b\rangle\longmapsto |z_1,\ldots,z_t,b\oplus z_1z_2\cdots z_t\rangle.$$

It flips the target exactly when every control is one. The number of controls is unbounded, and a gate has unit cost regardless of that number.

A parallel layer contains gates with disjoint supports: no qubit belongs to two gates in the same layer. Circuit depth counts sequential layers. There is no geometric restriction on which qubits interact. Ancillary qubits, the extra workspace beyond the input, begin in zero. The circuit starts on $|x\rangle|0\rangle^{\otimes(N-n)}$, applies its unitary gates, and measures one designated qubit at the end.

There are no intermediate measurements, postselection or primitive unbounded-fanout gates. The gates may depend arbitrarily on the input length, including their complex matrix entries, but not on the particular input string. Thus this is a nonuniform model with no gate-description computability restriction.

The class $\mathrm{QAC}^0$ uses fixed depth and polynomially many total qubits as $n$ grows. Since each disjoint layer has at most $N$ nonempty gates, this also bounds the gate count polynomially.

Three output requirements

An exact coherent parity operation maps $|x,b\rangle$ to $|x,b\oplus\operatorname{PARITY}(x)\rangle$ on superpositions as well as basis inputs. A clean implementation also restores workspace to zero. A measured-output computation asks only for a correct final classical bit; all other registers may be arbitrary.

The last requirement is weaker. A lower bound for it consequently rules out the stronger tasks too. Worst-case advantage $\varepsilon>0$ means success probability at least $1/2+\varepsilon$ on every input. The familiar bounded-error threshold $2/3$ corresponds to $\varepsilon=1/6$.

3. Development history and previous partial results

Classical $\mathrm{AC}^0$ allows constant-depth circuits of unbounded-fan-in AND and OR gates, with NOT gates and unrestricted wire reuse. Furst, Saxe and Sipser, and independently Ajtai, proved that parity requires superpolynomial size. Yao and Håstad strengthened these bounds, with Håstad’s switching lemma becoming a central tool.

Moore’s 1999 paper formulated quantum analogues and connected parity to fanout. Fanout sends a control bit coherently to many targets by exclusive-or. It is not cloning an arbitrary unknown quantum state; its action is a specified unitary on the computational basis. Conjugating fanout by Hadamard gates exchanges its control-target pattern with coherent parity. Høyer and Špalek subsequently showed how powerful constant-depth circuits become when fanout is supplied as a primitive.

Early lower bounds exposed the importance of workspace. Fang, Fenner, Green, Homer and Zhang obtained logarithmic depth bounds for exact clean parity when the number of ancillas is restricted. Later work ruled out exact clean simulation at entangling depth two, then removed the final-cleanliness requirement there. Entangling depth counts only multiqubit layers, permitting arbitrary one-qubit layers between them; it should not be confused with the total layer convention used in the headline theorem.

Rosenthal studied approximate parity unitaries and related cat-like states, with constant-depth constructions using superpolynomial resources. Pauli-spectrum and low-degree methods of Nadimpalli and collaborators, Anshu–Dong–Ou–Yao, and Dong–Ou–Yao expanded the permitted ancilla counts but retained depth-dependent resource restrictions.

Joshi, Tal, Vasconcelos and Wright established stronger depth-specific results, including exact parity obstructions at entangling depth three and approximate single-output bounds at depth two. The source manuscripts also cite Kintali’s September 2026 preprint for further depth-three correlation and depth-four exact-computation bounds. These precedents do not cover every fixed depth together with every polynomial workspace bound.

Gretta, Gupta and Joshi related the general parity question to Fourier concentration and state preparation. Their work also shows that shallow quantum circuits can approximate majority well on average, an important reason not to infer a sweeping classical-style average-case limitation from a parity lower bound.

4. What the new manuscripts claim

The common parity theorem

Both M1 and M2 state that for every fixed depth, fixed polynomial bound on total qubits and fixed $0<\varepsilon\leq1/2$, sufficiently large input lengths admit no allowed circuit with success at least $1/2+\varepsilon$ on every input.

For example, fix $d$, $c\geq1$ and $\varepsilon$. Eventually no depth-at-most-$d$ circuit on at most $n^c$ total qubits meets that guarantee. M2 also states the bound with an arbitrary fixed prefactor $C(n+1)^k$. The threshold may depend on all these fixed parameters; finitely many small input lengths are not excluded.

Ancillas start in zero, only one output is measured, the input need not be preserved, and every other final register can be discarded. The manuscripts therefore report a resolution of Moore’s parity conjecture in this more permissive measured-output model. Hadamard conjugation also excludes a constant-depth polynomial-resource coherent fanout implementation.

A structural localization theorem

M1 proves a stronger operator statement in an enlarged model of product-state reflections. Choose reference vectors $v_i$ on some qubits and count mismatches with

$$M=\sum_{i\in S}(I-|v_i\rangle\langle v_i|)_i.$$

Its integer eigenvalue counts how many selected factors differ from their references. Brackets such as $[M=0]$ and $[M\geq r]$ denote projections onto the indicated eigenspaces.

For a product projection $A$, a fixed-depth circuit $U$ and fixed exponents $0\leq s<t$, M1 claims, for sufficiently large total size $N$,

$$\bigl\|[M\geq N^t]UAU^\dagger[M=0]\bigr\| \leq e^{-N^s}.$$

The norm is the operator norm. The estimate is uniform in the product tests and circuit; the uncounted register can have arbitrary internal entanglement. For nontrivial thresholds below $N$, it says that a conjugated product condition barely connects a completely matching state to a state with very many mismatches.

Further consequences

M1 reports strong concentration of the output’s Fourier spectrum below every fixed power $n^\delta$. Here the output function is its expected sign, probability of zero minus probability of one; Fourier characters are products $\prod_{i\in S}(-1)^{x_i}$. The total squared Fourier weight on subsets of size at least $n^\delta$ decays faster than any inverse power of $n$.

The stated reductions also exclude strict-majority computation with worst-case advantage $1/(\log n)^\gamma$ for fixed $\gamma>0$. They give state-preparation obstructions, including sufficiently accurate Dicke states: uniform superpositions of strings with exactly $k$ ones. For fixed $0<\delta<1$ and $n^\delta\leq k\leq n/2$, the claimed trace-distance lower bound is $1/(80k)$ for sufficiently large $n$. The two papers establish their own parity proofs; neither uses the other’s structural theorem as an input.

5. Why the advance matters

Importance: 5/5, provisional. The claim addresses a foundational lower-bound problem for shallow quantum computation. It permits arbitrary fixed polynomial workspace, all fixed depths and the weak measured-output task, removing restrictions that shaped earlier progress.

The distinction between large gates and fanout is central. A single Toffoli can inspect many controls, but disjoint layer supports prevent one qubit from controlling arbitrarily many simultaneous operations. The result would show that quantum interference and wide controlled gates do not eliminate this limitation within the stated model.

The structural consequences also explain why parity is a useful benchmark rather than an isolated puzzle. High-order Fourier dependence and certain macroscopic state-preparation tasks would provide routes to parity. A general obstruction constrains all these routes. This rating measures significance if the claims hold, not proof verification.

6. The main idea

Reflections instead of light cones

A generalized Toffoli can be written $I-2P$, where $P$ is a product projection: all controls are fixed to one and the target to $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$. This representation tracks failed local product conditions even when the gate touches many qubits.

M1 uses two inductions. For projections supported on few qubits, only a few gates in a disjoint layer can meet the support. Expanding their reflections reduces the comparison to smaller depth. For a large product projection, a low-degree polynomial in a mismatch count approximates the zero-count test over a suitable interval.

That polynomial may behave badly outside the interval. M1 controls this remaining error through a same-depth inverse-circuit argument at a larger mismatch threshold. A finite sequence of increasing thresholds ends beyond the maximum possible count, where the estimate is automatic. Working backward closes the localization statement. Keeping projections unnormalized preserves the small amplitudes that the argument needs.

The final parity coefficient can be expressed using matrix elements between complementary Hadamard product states. These differ on all $n$ input qubits. Localization makes those elements small when $N$ is polynomial in $n$, whereas a fixed worst-case parity advantage forces their average to remain nonzero.

A second route through regular trajectories

M2 studies how low-degree operators propagate along particular state trajectories. A trajectory is regular when product-test mismatch counts have rapidly decaying tails for suitable collections of gates. Polynomial filters transport these tails forward and backward and show that regularity survives insertion of a product projection.

A state-dependent pruning rule then supplies regularity: reflections with very small projection probability on the current state are deleted. Each deletion changes the state only slightly, and the accumulated error stays controlled across a fixed number of layers.

For the parity contradiction, the argument copies basis inputs into untouched reference qubits and considers a uniform coherent input. The copied reference retains a parity sign corresponding to exactly $n$ excitations in an initial product basis. The pruned computation’s conjugated output projection has a negligible tail at that scale. Their pairing cannot support the required acceptance advantage.

Projection insertion and pruning are analytical devices. They do not add physical postselection or intermediate measurements to the allowed circuit model.

7. Scope, limitations, and open questions

The theorem concerns constant depth and polynomially many total qubits, with the specified gates and zero-initialized ancillas. It does not rule out growing depth, superpolynomial resources, a primitive fanout operation or different measurement-enabled models.

The headline statement excludes a fixed positive worst-case advantage. M1 gives additional quantitative correlation and Fourier consequences, but it should not be replaced by an unproved optimal size-depth tradeoff. Its majority bounds also do not imply a constant average-case error barrier: the manuscript explicitly distinguishes its inverse-polynomial near-perfect-success obstruction from weaker approximation guarantees.

The two proofs offer different structural tools—uniform operator localization and state-dependent trajectory control. Their usefulness for other circuit classes, sharper resource bounds and broader state-preparation questions remains a separate direction from the common parity conclusion.

8. Sources and further reading

Moore’s formulation, the recent depth-specific lower bounds and the Fourier-concentration equivalence are linked above. For the role of an added fanout gate, see Høyer and Špalek, Quantum Fan-out is Powerful. M1 and M2 below provide the new claims, their precise depth conventions and independent proof strategies.

Source manuscripts

• M1. OpenAI, Product-projection localization and the QAC0 parity lower bound (September 24, 2026).
• M2. OpenAI, Regular trajectories, pruning and quantum parity (September 24, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.