OctoInformBeta

Parity is not in QAC0

For an input string x=(x1,…,xn)∈{0,1}nx=(x_1,\ldots,x_n)\in\{0,1\}^n, parity is parity⁡(x)=x1⊕⋯⊕xn\operatorname{parity}(x)=x_1\oplus\cdots\oplus x_n. A physical layer consists of arbitrary one-qubit unitaries and unbounded-arity Toffoli gates with pairwise disjoint supports. A physical circuit on N≥nN\ge n total qubits starts in |x⟩⊗|0⟩⊗(N−n)|x\rangle\otimes|0\rangle^{\otimes(N-n)} and measures one designated output qubit in the computational basis, with arbitrary final states allowed on all discarded qubits. Its depth is the number of physical layers. Computing parity with worst-case advantage ε∈(0,1/2]\varepsilon\in(0,1/2] means returning parity⁡(x)\operatorname{parity}(x) with probability at least 1/2+ε1/2+\varepsilon for every xx. The question is whether fixed depth and polynomially many total qubits permit a fixed positive worst-case advantage. Strict majority is the Boolean function MAJ⁡n(x)=𝟏{x1+⋯+xn>n/2}\operatorname{MAJ}_n(x)=\mathbf 1\{x_1+\cdots+x_n>n/2\}.

For exact parity computation with aa ancillary qubits all returned to zero, Fang, Fenner, Green, Homer, and Zhang proved a depth lower bound of order log⁡(n/(a+1))\log(n/(a+1)).

The preprint proves that, for every fixed nonnegative integer depth dd, real c≥1c\ge1, and advantage 0<ε≤1/20<\varepsilon\le1/2, all sufficiently large nn exclude a physical circuit with N≤ncN\le n^c that computes parity with worst-case advantage ε\varepsilon. Beyond the results of the Lean library, the preprint also rules out fixed-depth circuits with polynomially many total qubits that compute strict majority with uniform-input average success at least 1−12n−δ1-\tfrac12 n^{-\delta} for all sufficiently large nn, for any fixed δ>0\delta>0.

A mismatch count is the operator M=∑i∈S(I−|vi⟩⟨vi|)iM=\sum_{i\in S}(I-|v_i\rangle\langle v_i|)_i, for a subset S⊆{1,…,N}S\subseteq\{1,\ldots,N\} and separately chosen unit vectors vi∈ℂ2v_i\in\mathbb C^2. A product projection fixes a unit vector on each qubit of a selected subset and acts as the identity elsewhere. The enlarged depth-dd circuit model consists of dd disjoint layers of reflections I−2AI-2A about product projections AA, interleaved with products of one-qubit unitaries. The Lean library proves uniform localization: for every fixed depth dd and real 0≤s<t0\le s<t, the operator norm of the transition from zero mismatches to at least NtN^t mismatches under a product projection conjugated by an enlarged depth-dd circuit is at most exp⁡(−Ns)\exp(-N^s) for all sufficiently large NN, uniformly over the circuits and mismatch counts. The Lean library’s polynomial-size parity theorem states that, for all positive integers d,k,Cd,k,C and sufficiently large nn, every physical circuit of depth at most dd with n≤N≤C(n+1)kn\le N\le C(n+1)^k has an input on which its success probability is strictly less than 2/32/3. Lean has checked every result of the Lean library, including its general parity lower bound, so the Lean library is the reference. Each result on these pages has the Lean library’s statement, with any differing preprint statement given beside it. The preprint is a guide only to the order and names of the results.