Product-projection localization and the QAC0 parity lower bound

1 Introduction

Parity is a basic test of whether a shallow circuit can combine information from all of its inputs. For a computational-basis string x=(x_1,\ldots,x_n)\in\{0,1\}^n, its value is \parity(x)=x_1\oplus\cdots\oplus x_n. We study circuits generated by arbitrary one-qubit unitaries and Toffoli gates with any number of controls and one target. Gates in each parallel layer have pairwise disjoint supports. The depth is the number of such layers.

The circuit starts in \ket{x}\otimes\ket0^{\otimes(N-n)} on N total qubits. Its answer is the result of measuring one designated output qubit in the computational basis; the remaining registers may be discarded in arbitrary final states, and the input need not be preserved. For 0<\varepsilon\le1/2, computing parity with worst-case advantage \varepsilon means giving the correct answer with probability at least 1/2+\varepsilon for every x. The class \QAC uses constant depth and polynomially many total qubits. This also bounds the gate count: a disjoint layer on N qubits has at most N nonempty gates. The gates may depend on n, but not on the input string. We use unitary circuits, with no intermediate measurements, postselection, or primitive unbounded-fanout gate.

Taking \varepsilon=1/6 gives the usual success threshold 2/3. Thus Theorem 1 resolves positively the conjecture \parity\notin\QAC, with bounded error, polynomially many ancillas, and only a measured output required.

1.1 History and significance

In the classical class \mathrm{AC}^0, circuits use unbounded-fan-in AND and OR gates and NOT gates, with unrestricted reuse of wires. The superpolynomial constant-depth lower bounds for parity of Furst, Saxe, and Sipser [FSS84] and, independently, Ajtai [Ajt83], were fundamental explicit circuit lower bounds. Yao obtained exponential bounds [Yao85], and Håstad obtained almost optimal exponential bounds through the switching lemma [Hås86]. Quantum circuits introduce a different constraint: the supports of gates in a parallel layer are disjoint, so a wire cannot control arbitrarily many simultaneous gates.

Moore introduced the corresponding quantum circuit classes and related coherent parity to unbounded fanout [Moo99]. The latter is the unitary sending \ket{b,y_1,\ldots,y_k} to \ket{b,y_1\oplus b,\ldots,y_k\oplus b}. The coherent parity transformation sends the same input to \ket{b\oplus\parity(y),y_1,\ldots,y_k}, where y=(y_1,\ldots,y_k). Hadamard conjugation interchanges these two transformations. Moore’s original formulation required ancillary qubits to return to zero; our result also treats the more permissive measured-output model. Green, Homer, Moore, and Pollett developed the associated quantum counting classes and modular-gate equivalences [GHMP02]. The constant-depth constructions of Høyer and Špalek demonstrate how much computational power a primitive fanout operation provides [HŠ05].

Early lower bounds revealed the importance of the ancillary register. Fang, Fenner, Green, Homer, and Zhang obtained a depth lower bound of order \log(n/(a+1)) for exact, clean parity computation with a ancillary qubits [FFGHZ06, Corollary 4.6]; Bera developed a different lower-bound method in the ancilla-free setting [Ber11]. Padé, Fenner, Grier, and Thierauf ruled out exact clean simulation at entangling depth two [PFGT20]. Fenner, Grier, Padé, and Thierauf subsequently removed the final-state cleanliness requirement for exact single-output parity at that depth [FGPT25, Theorem 6.1]. Here the quoted depth-two results count multiqubit layers, allowing arbitrary one-qubit layers between them; we call this entangling depth. Rosenthal proved lower bounds for approximate parity unitaries and related cat-like states, and gave constant-depth approximation constructions with superpolynomial resources [Ros21]. Approximate unitary implementation and computation of a single measured classical bit have different output requirements, so the distinction matters in comparing lower bounds.

More recent work developed spectral and Fourier methods for \QAC. Nadimpalli, Parham, Vasconcelos, and Yuen used the Pauli spectrum to prove ancilla-restricted lower bounds [NPVY24]. Anshu, Dong, Ou, and Yao ruled out a fixed positive parity advantage with \widetilde O(n^{1+3^{-d}}) ancillas at every fixed entangling depth d\ge1 [ADOY25, Corollary 4.4 and Theorem 4.6]. Dong, Ou, and Yao increased this ancilla range to \widetilde O(n^{1+2^{-d}}) [DOY25, Corollary 3.3]. Here \widetilde O suppresses logarithmic factors. Both results use spectral-norm approximation of conjugated observables.

Joshi, Tal, Vasconcelos, and Wright proved exact parity lower bounds at entangling depth three and bounded parity correlation at entangling depth two by \exp(-\Omega(\sqrt n)), without a size restriction [JTVW26, Theorem 1.2 and Corollary 5.9]. Kintali’s September 2026 preprint reports correlation at most \exp(-\Omega(n)) at entangling depth three and an exponential multiqubit gate lower bound for exact parity at entangling depth four [Kin26, Theorems 1–2]. These results retain a resource restriction or a fixed upper bound on entangling depth. Gretta, Gupta, and Joshi established an equivalence between the general parity lower-bound question and Fourier concentration [GGJ26a], and Xu and Li extended related fanout reductions to symmetric Boolean functions [XL26]. Our theorem permits every fixed depth and every fixed polynomial bound on the total number of qubits, with arbitrary discarded garbage and any fixed positive worst-case advantage.

1.2 The localization argument

Unbounded gate arity is the first obstacle to a lower bound. A single Toffoli gate can involve every input, so the number of wires in an output’s backward light cone gives no useful restriction. Our argument instead bounds transitions from a fixed product condition to states with many mismatches from that condition. We keep the amplitude lost when imposing a projection, without normalizing the resulting state.

A product projection fixes a chosen one-qubit vector on each qubit of a subset and acts as the identity elsewhere. Fix reference unit vectors v_i on a subset S\subseteq\{1,\ldots,N\}. Their mismatch count is

its eigenvalue counts the factors orthogonal to their reference vectors. Write [M=0] and [M\ge r] for its zero and high-count spectral projections. Given a shallow circuit U and a product projection A, our structural theorem bounds

for every fixed depth and all sufficiently large N. The norm is the operator norm, and the estimate is uniform in U,A,M. In particular, the uncounted register can carry an arbitrary, internally entangled state. Theorem 2 gives the precise statement in a reflection-gate model containing the original circuits.

There are two inductions. The outer induction removes one circuit layer. Every allowed Toffoli is a reflection I-2P about a product projection. If A fixes only k qubits, at most k gates in a disjoint layer meet its support. Expanding those reflections on the two sides of A expresses the conjugate as a sum of products of three projections, each conjugated by a circuit of one smaller depth. Intermediate mismatch cutoffs bound these ordered products. This proves localization for projections supported on few qubits (Section 4).

The reflection expansion has a cost exponential in the support size, so it does not directly control arbitrary product projections. To handle such a projection, write it as [D=0] for a second mismatch count D. A polynomial p(D) of low degree expands into projections on few qubits. The construction in Section 3 controls both its approximation error on a low-count interval and the sum of its coefficients weighted by the cost of this expansion. It need not be a good approximation at large counts. The second induction controls precisely that remaining error.

Here the order of the operators is decisive. Put P=[M=0], Q=U[D=0]U^\dagger, and H=[M\ge N^t]. Squaring the transition norm gives \norm{HQP}^2=\norm{HQPQH}. Replacing only the first Q by p(UDU^\dagger) leaves an error acting on PQ. After conjugation by U^\dagger, the high-count part of that error is another localization problem, with the two counts exchanged and a larger mismatch threshold. We prove the universal statement at that larger threshold first. A finite chain of thresholds ends above the maximum possible count N, where localization is automatic; working backward proves the original statement (Section 5). The same-depth inverse-circuit invocation is therefore part of a finite induction.

Finally, the output-zero probability is the diagonal of the conjugated output projection. Its parity coefficient is the average of matrix entries between complementary Hadamard product states. Those states differ on all n input qubits. The localization theorem makes every such entry small when N is polynomial in n, whereas a fixed worst-case advantage forces their average to stay positive (Section 6). This final step places no restriction on the unmeasured registers.

The polynomial ingredients have a substantial history. The combination of Chebyshev approximation with exact roots at exceptional integer points follows an established approximation-and-interpolation pattern for symmetric predicates [She09, Section 3.1]. Polynomial localization and concentration for quantum states appear in work of Kuwahara, Arad, Amico, and Vedral [KAAV17] and Anshu and Metger [AM23]. The latter also track the total norm of local terms. For \QAC, the spectral-norm approximation approach of Anshu, Dong, Ou, and Yao [ADOY25] is a particularly relevant predecessor. We prove the required polynomial and coefficient estimates here. The finite inverse-circuit induction supplies the additional scale improvement: localization holds for every fixed exponent pair 0\le s<t, uniformly in both counts and the entire uncounted register.

The companion article Regular trajectories, pruning and quantum parity [Ope26, Sections 4–7] gives an independent proof through state-dependent propagation, projection insertion, and pruning. Its structural estimates concern regular trajectories; the present operator-norm theorem is proved without a trajectory hypothesis. Both articles prove their own polynomial estimates and their own parity conversion, so neither parity proof invokes the other.

1.3 Consequences

Localization and parity also constrain symmetric computation and state preparation. We combine them with reductions of Xu and Li [XL26] and state constructions of Gretta, Gupta, and Joshi [GGJ26a]. In particular, strict majority, \operatorname{MAJ}_n(x)=\mathbf 1\{|x|>n/2\}, where |x| is the Hamming weight, cannot be computed in this circuit model with worst-case advantage 1/(\log n)^\gamma for any fixed \gamma>0 (Corollary 3). This separates the model from the corresponding one with unbounded threshold gates.

The state-preparation consequences rule out inverse-polynomial measurement probabilities for both a string and its bitwise complement, and sufficiently accurate preparation of uniform superpositions of strings of a fixed Hamming weight k with n^\delta\le k\le n/2 for fixed \delta>0 (Corollary 1). For a single measured output, define its expected sign as the probability of zero minus the probability of one. Localization implies that its Fourier coefficients have total squared weight that decays faster than every inverse power of n on input subsets of size at least n^\delta, for every fixed 0<\delta\le1 (Corollary 2). Finally, majority cannot be computed with average success at least 1-\tfrac12 n^{-\delta} on uniformly random inputs, for any fixed \delta>0 (Corollary 4). The precise quantifiers and proofs appear after the parity proof in Section 7.

Organization. Section 2 states the localization theorem and fixes the circuit model. Section 3 proves the polynomial approximation. Section 4 reduces small-support projections to the preceding depth, and Section 5 completes the finite scale induction. Section 6 derives Theorem 1, and Section 7 proves the consequences just described.

2 Product projections and localization

The parity proof will use localization for a single output projection. We prove the stronger uniform statement for every product projection, because its induction exchanges the projected and counted registers.

All operators act on \mathcal H_N=(\mathbb C^2)^{\otimes N}, and \norm{\cdot} denotes the operator norm. Identities on unmentioned qubits are implicit. Spectral projections are written in brackets; for example, [M\ge r] is the projection onto the sum of eigenspaces of a self-adjoint operator M with eigenvalues at least r. All logarithms are natural.

A count is an operator

The subscript indicates the qubit on which the summand acts. The reference vector v_i\in\mathbb C^2 can be chosen separately at each qubit. The summands commute, and the spectrum of M is contained in \{0,\ldots,|S|\}. A product projection is a tensor product of rank-one one-qubit projections on a subset, with identity on the complement. Its support is the selected subset. The empty product is I. These are precisely the projections [M=0]. In particular, a product projection need not have rank one on \mathcal H_N.

We use a slightly enlarged gate set of product-state reflections, as in [Ros21, Section 2 and Proposition 2.1]. Let \cU_d(N) be the set of unitaries

where each L_j is a product of one-qubit unitaries and each R_j is a layer of gates I-2A with disjoint supports, with A a product projection on the gate’s qubits. Identity layers are allowed. The class \cU_0(N) consists of products of one-qubit unitaries.

This model contains the circuits of Theorem 1. Indeed, if C projects onto all controls being 1, a Toffoli gate equals

Grouping the local gates in each parallel step gives (2.2) with a number of reflection layers bounded by the original depth. Discarded qubits can be retained as idle wires without changing any later measurement probability. Here d counts reflection layers in the enlarged model; it is at most the number of physical layers in the original circuit. The arbitrary local layers in (2.2) are included in this definition, rather than charged separately to d.

We will also use closure under inversion at the same depth. Each R_j is self-adjoint, since it is a product of commuting self-adjoint reflections. Thus

This is the same normal form with the layer indices reversed: the new local layers are L_d^\dagger,\ldots,L_0^\dagger, in temporal order, and the new reflection layers are R_d,\ldots,R_1. No factors on overlapping supports have been commuted.

Write \cB_d(s,t) for the assertion of Theorem 2 at the specified d,s,t, including its uniformity. If t>1, it is immediate for N>1, since [M\ge N^t]=0. We prove the theorem by induction on d, assuming all fixed exponent pairs at the preceding depth. The counts M,D are allowed to be different because the proof will exchange their roles when applying (2.3).

The next two sections supply the approximation and depth-reduction estimates. The proof of Theorem 2 is completed in Section 5.

3 A polynomial approximation with controlled coefficients

We will approximate the zero spectral projection of a count by a polynomial. Small approximation error alone is not enough: expanding the kth power of a count produces up to N^k product projections. For a polynomial f(x)=\sum_k c_kx^k, define its weighted coefficient norm by

This bounds the sum of absolute coefficients in the later operator expansion. The construction uses Chebyshev approximation together with exact roots at the first integer points, a classical approximation-and-interpolation pattern; see Sherstov [She09, Section 3.1 and Lemma 3.9]. Controlling this sum is in the same general spirit as tracking the total local norm of Anshu and Metger [AM23, Definition 2.3 and Lemma 4.5]. We supply the exact bounds needed here, including intervals whose endpoint exceeds the maximum count N.

4 Depth reduction for small-support projections

We begin the proof of Theorem 2 at depth zero. We then show that the full localization statement at depth d-1 controls projections of small support at depth d. All large-N thresholds in this section depend only on the displayed exponents and the depth, not on the circuits, counts, or product projections.

The depth-zero estimate incorporates both the chance of producing a mismatch and the amplitude lost under projection. We next extend the preceding-depth hypothesis from one mismatch pattern to all patterns below a small threshold. This is the input needed to control successive factors in the layer expansion.

We can now remove one reflection layer when the tested projection has small support. The expansion produces three ordered factors; the low-count estimate just proved bounds the transitions between them.

5 The finite scale induction

The preceding depth gives localization for projections with small support. We now extend that estimate to arbitrary product projections. The extension uses the inverse circuit at a larger mismatch scale. The main constraint is how far that scale can move: to prove \cB_d(s,t) from \cB_d(t,b), we need t<b<2t-s. This interval leaves room for a polynomial whose approximation error decays faster than e^{-N^s} while its degree and the logarithm of its weighted coefficient norm remain below the mismatch threshold N^t.

We now choose a finite chain of scales within this interval. Each step will advance the mismatch exponent by almost the current gap t-s. Keeping at least half of the initial gap for O(1/(t-s)) steps will carry that exponent above one, where the tail projection vanishes. A slack of order (t-s)^2 per step is small enough to preserve the gap.

6 From localization to parity

We finish by relating the output probability to transitions between product states. All localization estimates have already been proved; no assumption about coherent or clean computation is needed here. For the broader Fourier-concentration setting, see [GGJ26a]; the character-orthogonality identity needed here is proved directly.

The role of a polynomial qubit bound is solely the choice of 0<s<t<1/c. The localization theorem itself is uniform on N qubits and does not assume any relation between N and an input length. The proof gives no claim of the same lower bound when the ancillary register is allowed to be superpolynomial.

7 Consequences of localization and parity

The direct parity proof is complete. Localization next bounds complementary-output probabilities, and a construction of Gretta, Gupta, and Joshi [GGJ26a] gives a Dicke-state obstruction. We also derive scalar-output Fourier concentration directly from localization. This concentration rules out high average accuracy for majority, while Xu and Li’s reductions [XL26] give worst-case obstructions for symmetric functions. Throughout, discarded registers remain unrestricted.

7.1 State preparation

Gretta, Gupta, and Joshi [GGJ26a] connect complementary-output probabilities and Dicke-state preparation to parity. Here localization bounds the complementary probabilities directly; their block construction then gives the Dicke-state consequence. For an n-qubit density operator \rho, write

where \bar y is the bitwise complement of y. This is the felinity of \rho [GGJ26a, Definition 2.1]. Also write

for the weight-k Dicke state and trace distance, respectively.

In particular, no such family can assign inverse-polynomial probabilities to both a string and its complement: their two terms contribute 4p_y p_{\bar y} to \mathcal F_n(\rho).

The polynomial bound in Corollary 1 is measured in the number n of target qubits. Gretta, Gupta, and Joshi [GGJ26b, Theorem 1.1] show that every n-qubit pure state can be prepared exactly at constant depth with 2^{O(n)} ancillas, all returned to zero.

7.2 Scalar-output Fourier concentration

Gretta, Gupta, and Joshi [GGJ26a, Conjecture 1 and Corollary 1.2] formulate a qualitative Quantum-LMN statement and establish its equivalence with the parity lower-bound question. Our localization theorem gives this Fourier-concentration statement directly. For an n-input circuit C on N total qubits with output qubit t, define its expected measured sign and uniform-input Fourier coefficients by

Write W_{\ge k}[f_C]=\sum_{|S|\ge k}|\widehat f_C(S)|^2. This is the absolute squared Fourier tail, not a fraction of the total weight \mathbb E_x f_C(x)^2\le1.

7.3 Majority and symmetric functions

The reductions of Xu and Li turn the parity lower bound into a worst-case lower bound for majority and broader symmetric families. For a symmetric f_n:\{0,1\}^n\to\{0,1\}, let f_{n,i} be its value on inputs of Hamming weight i, and define its transition radius by

with \rho(f_n)=0 for a constant function. Write \widetilde{\deg}_{1/3}(f_n) for the least total degree of a real polynomial approximating f_n pointwise within 1/3. For nonconstant symmetric functions, Paturi’s characterization [Pat92, Theorem 1] gives

Thus the approximate-degree hypothesis below also forces a polynomially large transition radius.

There is consequently a strict separation between the Boolean families computed with worst-case success at least 2/3 in our model and in the matched model obtained by adjoining unit-cost reversible unbounded-arity threshold gates

while retaining the same depth, disjoint-support, qubit, ancilla, and output conventions. The enlarged model contains the original one and computes strict majority exactly with one such gate at t=\lfloor n/2\rfloor+1, whereas Corollary 3 excludes even worst-case success 2/3 for majority in the original model.

7.4 High average accuracy for majority

The preceding obstruction assumes an advantage on every input. The high-average-accuracy consequence of Gretta, Gupta, and Joshi [GGJ26a, Corollary 4.6] also follows directly from our Fourier-concentration bound: majority retains a polynomial Fourier tail at a polynomially growing cutoff.

This conclusion does not assert a constant average-case gap or exclude 1-1/\operatorname{polylog}n correlation.