Product-projection localization and the QAC0 parity lower bound

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 $\operatorname{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 $\lvert x\rangle\otimes\lvert0\rangle^{\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 $\mathrm{QAC}^{0}$ 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.

Theorem 1 (Parity lower bound). Fix a nonnegative integer $d$, a real number $c\ge1$, and $0<\varepsilon\le1/2$. For all sufficiently large $n$, no circuit of depth at most $d$ on $n$ input qubits and at most $n^c$ total qubits, using arbitrary one-qubit unitaries and unbounded-arity Toffoli gates, computes $\operatorname{PARITY}(x)$ with probability at least $1/2+\varepsilon$ for every $x\in\{0,1\}^n$. Gates in each layer have disjoint supports, ancillas start in $\lvert0\rangle$, and one output qubit is measured; the other qubits may be discarded.

Taking $\varepsilon=1/6$ gives the usual success threshold $2/3$. Thus Theorem 1 resolves positively the conjecture $\operatorname{PARITY}\notin\mathrm{QAC}^{0}$, with bounded error, polynomially many ancillas, and only a measured output required.

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 [8] and, independently, Ajtai [1], were fundamental explicit circuit lower bounds. Yao obtained exponential bounds [26], and Håstad obtained almost optimal exponential bounds through the switching lemma [12]. 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 [17]. The latter is the unitary sending $\lvert b,y_1,\ldots,y_k\rangle$ to $\lvert b,y_1\oplus b,\ldots,y_k\oplus b\rangle$. The coherent parity transformation sends the same input to $\lvert b\oplus\operatorname{PARITY}(y),y_1,\ldots,y_k\rangle$, 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 [9]. The constant-depth constructions of Høyer and Špalek demonstrate how much computational power a primitive fanout operation provides [13].

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 [6], Corollary 4.6; Bera developed a different lower-bound method in the ancilla-free setting [4]. Padé, Fenner, Grier, and Thierauf ruled out exact clean simulation at entangling depth two [21]. Fenner, Grier, Padé, and Thierauf subsequently removed the final-state cleanliness requirement for exact single-output parity at that depth [7], 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 [23]. 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 $\mathrm{QAC}^{0}$. Nadimpalli, Parham, Vasconcelos, and Yuen used the Pauli spectrum to prove ancilla-restricted lower bounds [18]. 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$ [2], Corollary 4.4 and Theorem 4.6. Dong, Ou, and Yao increased this ancilla range to $\widetilde{O}(n^{1+2^{-d}})$ [5], 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 [14], 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 [15], 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 [10], and Xu and Li extended related fanout reductions to symmetric Boolean functions [25]. 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.

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 $\lVert HQP\rVert^2 = \lVert HQP QH\rVert$. 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 [24], Section 3.1. Polynomial localization and concentration for quantum states appear in work of Kuwahara, Arad, Amico, and Vedral [16] and Anshu and Metger [3]. The latter also track the total norm of local terms. For QAC$^{0}$, the spectral-norm approximation approach of Anshu, Dong, Ou, and Yao [2] 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 [20], 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.

Consequences

Localization and parity also constrain symmetric computation and state preparation. We combine them with reductions of Xu and Li [25] and state constructions of Gretta, Gupta, and Joshi [11]. In particular, strict majority, $\operatorname{MAJ}_n(x) = 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 10). 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 8). 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 9). Finally, majority cannot be computed with average success at least $1 - \frac{1}{2}n^{-\delta}$ on uniformly random inputs, for any fixed $\delta> 0$ (Corollary 11). 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.

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 $\lVert\cdot\rVert$ 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,\lvert S\rvert\}$. 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 [23], Section 2 and Proposition 2.1. Let $\mathcal{U}_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 $\mathcal{U}_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.

Theorem 2 (Localization of conjugated product projections). Fix a nonnegative integer $d$ and real numbers $0\le s<t$. For all sufficiently large $N$, every $U\in\mathcal{U}_d(N)$ and every pair of counts $M,D$ on $\mathcal{H}_N$ satisfy

The sufficient lower bound on $N$ depends only on $d,s,t$, not on the circuit, the counted subsets, or their reference vectors.

Write $\mathcal{B}_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).

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

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 $k$th power of a count produces up to $N^k$ product projections. For a polynomial $f(x) = \sum_k c_k x^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 [24], Section 3.1 and Lemma 3.9. Controlling this sum is in the same general spirit as tracking the total local norm of [3], Definition 2.3 and Lemma 4.5. We supply the exact bounds needed here, including intervals whose endpoint exceeds the maximum count $N$.

Lemma 3. Fix real numbers $0 < a < b$ and $u > (a + b)/2$. For every sufficiently large integer $N$, there is a real polynomial $p$ such that

and

The threshold for $N$ depends only on $a$, $b$, $u$. No restriction $b \le1$ is imposed.

Proof. Put

Since $a < b$, we have $m \ge2r$ once $N$ is sufficiently large. Define the root polynomial

It is one at zero and vanishes at the first $r$ positive integers. On $[r,m]$ we only use the crude bound $|F(x)| \le m^r$. To overcome this growth, we multiply it by a polynomial that is one at zero and small throughout $[r,m]$. To construct that factor, define the Chebyshev polynomials by

Induction in this recurrence, using the corresponding addition identities, gives

In particular, $|T_j(x)| \le1$ on $[-1,1]$. Set

The denominator is positive, and $p(0) = 1$.

To bound the denominator, write $q = \sqrt{r/m}$ and $h = (1+q)/(1-q)$. Then $0 < q < 1$ and

Consequently

This denominator is also at least $1$, by $(h^\ell+h^{-\ell})/2\ge1$.

The polynomial vanishes at the integers $1,\ldots,r$. For $r\le x\le m$, the affine Chebyshev argument in (3.3) lies in $[-1,1]$, and each factor $|1-x/j|$ is at most $m$. Thus

Since $r\ge N^a$ and $\log m\longrightarrow\infty$, this is at most $\exp(-N^a)$ for all sufficiently large $N$. Together with the exact roots, this proves (3.2). No estimate is needed at noninteger points between $0$ and $r$.

It remains to bound the degree and the coefficient cost. The coefficient convolution formula gives $W_N(fg)\le W_N(f)W_N(g)$. Hence the root product has weighted norm at most

For $z(x)=(m+r-2x)/(m-r)$, we have

Here $m\ge2r$ controls the constant coefficient, while the positive integer $m-r\ge1$ controls the linear coefficient. This bound remains valid when $m>N$.

Let $A=2\beta+1$. The Chebyshev recurrence and induction give $W_N(T_j(z))\le A^j$: the inductive step uses

The initial cases follow from $W_N(T_0(z))=1$ and $W_N(T_1(z))=\beta\le A$. Since $A\le7+4N\le11(1+N)$ and the denominator in (3.3) is at least $1$, we obtain

Finally, with $\gamma=(a+b)/2>a$, the rounded definitions imply

Both $r+\ell$ and $\log W_N(p)$ are $o(N^u)$ because $u>\gamma$. All constants depend only on the fixed exponents, proving (3.1) with the asserted uniform threshold.

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.

Lemma 4 (Depth zero). For every fixed $0 \le s < t$, the statement $\mathcal{B}_0(s,t)$ holds.

Proof. If $U \in\mathcal{U}_0(N)$, then $Q = U[D = 0]U^{\dagger}$ is a product projection. Let $S$ be the counted subset of $M$, let $P = [M = 0]$, and put $I_* = S \cap\operatorname{supp} Q$. Write $|v_i\rangle$ for the reference vectors of $M$ and $|w_i\rangle$ for the projected vectors of $Q$ on $I_*$. Set

Every vector in the range of $P$ has the fixed tensor factor $\bigotimes_{i \in S}|v_i\rangle$ on $S$. Its factor on the complement of $S$ is arbitrary and need not be a product state. Applying $Q$ contributes the squared-amplitude factor $\prod_{i \in I_*}(1-p_i)$ on $S$, and a contraction on its complement. If this amplitude is nonzero, the resulting normalized factor on $S$ is

with factors placed in their original qubit order. In this product vector, the mismatch count has the law of a sum $K$ of independent Bernoulli variables with parameters $p_i$; coordinates in $S \setminus I_*$ never contribute. Keeping the squared-amplitude factor, we obtain, for every $r > 0$,

The middle inequality is Markov’s inequality applied to $2^K$. The same bound is immediate if the amplitude vanishes. Taking $r = N^t$ gives $\left\|[M \ge N^t]QP\right\| \le\exp\left(-\frac{1}{2}(\log2)N^t\right)$, which is at most $\exp(-N^s)$ for all sufficiently large $N$. ∎

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.

Lemma 5 (Propagation from low counts). Fix $d \ge1$ and assume $\mathcal{B}_{d-1}(s,t)$ for every fixed pair $0 \le s < t$. For fixed $\alpha,\sigma\ge0$ and $\beta> \max\{\alpha,\sigma\}$, all sufficiently large $N$ satisfy

uniformly for every count $M$ and every $B = VP_*V^\dagger$, where $V \in\mathcal{U}_{d-1}(N)$ and $P_*$ is a product projection.

Proof. Let $S$ be the counted subset of $M$. For $F \subseteq S$, define $M^F$ by replacing the reference vector on each coordinate of $F$ with an orthogonal unit vector, leaving the other references unchanged. The projection $[M^F = 0]$ specifies precisely the mismatch pattern $F$ for $M$, with identity on the complement of $S$. Hence

These counts are diagonal in the same product basis, and pointwise in that basis $M^F \ge M - |F|I$. Choose fixed exponents

For all sufficiently large $N$, uniformly over the indicated $F$, $N^\beta- |F| \ge N^{\beta'}$. Thus

where the last inequality is $B_{d-1}(\sigma',\beta')$. There are at most $(1+N)^{\lceil N^\alpha\rceil+1}$ patterns. The triangle inequality therefore bounds the left side of (4) by

for all sufficiently large $N$, since $\sigma' > \alpha,\sigma$. □

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.

Lemma 6 (Small-support depth reduction). Fix $d \ge1$ and assume $B_{d-1}(s,t)$ for every fixed pair $0 \le s < t$. For fixed $u,w \ge0$ and $t > \max\{u,w\}$, all sufficiently large $N$ satisfy

uniformly for every $U \in\mathcal{U}_d(N)$, every count $M$, and every product projection $A$ supported on at most $N^u$ qubits.

Proof. The claim is immediate when $t > 1$, so suppose $t \le1$. Write

where $V = L_1$ if $d = 1$, and put $A' = L_0AL_0^\dagger$. This is a product projection with the same support as $A$, of size $k \le N^u$. Gates of $R_1$ whose supports avoid $\operatorname{supp} A'$ commute with $A'$ and cancel in $R_1A'R_1$. Because the gates in $R_1$ have disjoint supports, at most $k$ gates remain.

Expand each remaining reflection $I - 2P_*$ on both sides of $A'$. Each term is a scalar multiple of $P_{\mathrm{left}}A'P_{\mathrm{right}}$, where the two side factors are product projections: within either side, the selected gate projections have disjoint supports. The sum of the absolute scalar coefficients is at most

Conjugation by $V$ turns each such term into a product $B_1B_2B_3$, with

Each $B_j$ is therefore a contraction to which Lemma 5 applies. No commutation between these three factors is asserted or needed.

Choose fixed exponents

and set

Insert these cutoffs between the three factors, read from right to left. The resulting terms isolate a jump to the first cutoff, a jump from below the first to the second, and a jump from below the second to the final high-count sector:

The first term has norm at most $\exp(-N^{w'})$ by $\mathcal{B}_{d-1}(w',\tau_1)$, applied to $(I-E_1)B_3P$. For the second term, Lemma 5 with $(\alpha,\sigma,\beta)=(\tau_1,w',\tau_2)$ bounds $(I-E_2)B_2E_1$ by the same quantity. For the third, that lemma with $(\alpha,\sigma,\beta)=(\tau_2,w',t)$ bounds $HB_1E_2$. All other factors are contractions. Therefore

Summing with (4.3) gives

for all sufficiently large $N$. The strict gaps $w'>u,w$ absorb the entire expansion cost uniformly for $k\le N^u$.

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 $\mathcal{B}_d(s,t)$ from $\mathcal{B}_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$.

Lemma 7 (One backward step). Fix $d\ge1$, and assume $\mathcal{B}_{d-1}(s,t)$ for every fixed $0\le s<t$. Let $s,t,b$ be fixed real numbers with

If $\mathcal{B}_d(t,b)$ holds, then $\mathcal{B}_d(s,t)$ holds.

Proof. Choose fixed auxiliary exponents

These choices are possible because $b<2t-s$. Since $b>t>a$, they give exactly the inequalities required by the polynomial and small-support estimates:

Fix $U \in\mathcal{U}_d(N)$ and counts $M$, $D$, and put

Let $p(x) = \sum_k c_k x^k$ be the polynomial in Lemma 3 for $a,b,u$. We will first control $Hp(C)P$ by small-support localization. Squaring the desired norm will then place the remaining high-$C$ error on $PQ$, where the larger-scale hypothesis applies after inversion.

Each count summand is a rank-one projection on one qubit. Expanding $D^k$ gives at most $N^k$ ordered monomials, each a product projection on at most $k$ qubits: repeated indices collapse by idempotence, while different indices commute. For $k \le\deg p \le N^u$, Lemma 6 applies to every such monomial with the same fixed exponents $u$, $w$, $t$. Since $p(C) = Up(D)U^\dagger$, its coefficient bound gives

The constant term causes no difficulty: it is a multiple of $I$, and $HP = 0$. Also, $\lVert C\rVert\le N$ gives

The polynomial need not approximate $Q$ on all of $\mathcal{H}_N$. Squaring the desired norm makes the approximation error occur as $(Q-p(C))PQ$, rather than $(Q-p(C))P$:

Only the leftmost $Q$ was replaced in this decomposition. No commutation of $P$ with $C$ or $Q$ is involved.

Split the last error at the spectral threshold $N^b$ of $C$. The spectral projections of $C$ commute with $Q$ and $p(C)$. On $[C < N^b]$, the error is zero at eigenvalue $0$, since $p(0) = 1$, and at most $e^{-N^a}$ at every positive eigenvalue, since these eigenvalues are integers. Hence

The remaining factor is exactly the transition controlled by the inverse circuit. Unitary conjugation gives

Here $\mathcal{B}_d(t,b)$ applies with circuit $U^\dagger$, mismatch count $D$, and projected count $M$. Inverse closure (2) and the universal quantifiers in $\mathcal{B}_d(t,b)$ are both used.

Combining (6), (8), (9), and (10) yields

By (5.1), each term is eventually at most $\frac{1}{3}e^{-2N^s}$. Indeed $w>u$, $t>u$, and $a,w,t>s$. This remains true for $s=0$, when the comparison quantity is a fixed positive constant. Taking the square root proves $\mathcal{B}_d(s,t)$. All sufficient lower bounds on $N$ depend only on the fixed parameters and $d$, so the conclusion is uniform. ∎

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.

Proof of Theorem 2. The case $d=0$ is Lemma 4. Fix $d \ge1$, and assume the theorem at depth $d-1$ for every fixed exponent pair. It remains to prove $\mathcal{B}_d(s,t)$ for fixed $0 \le s < t \le1$; the case $t>1$ is immediate. Put

and define

Writing $g_i=t_i-s_i$, we have

Let $K=\lceil2/g\rceil$. Since $0<g\le1$,

Thus $g_i>g/2$ for $i\le K$, and

Let $J\le K$ be the first index for which $t_J>1$. This index and every exponent in the chain are independent of $N$. The assertion $\mathcal{B}_d(s_J,t_J)$ is trivial.

Suppose now that $\mathcal{B}_d(s_{i+1},t_{i+1})$ has been proved, where $i<J$. The recurrence and the positive next gap give

Thus Lemma 7 applies with $b=t_{i+1}$. Its assumed assertion is precisely $\mathcal{B}_d(t_i,t_{i+1})=\mathcal{B}_d(s_{i+1},t_{i+1})$, so it proves $\mathcal{B}_d(s_i,t_i)$. Working backward reaches the target pair, as in Figure 1.

There are only finitely many steps for each fixed $d,s,t$. Taking the maximum of their sufficient lower bounds on $N$ preserves uniformity over every circuit and pair of counts. Each step uses only finitely many fixed exponent tuples from depth $d-1$; the number of monomials and their varying supports are paid for by the explicit coefficient estimates, not by further asymptotic thresholds. Thus the induction does not require a threshold uniform over all real exponent pairs. This completes the depth induction.

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 [10]; the character-orthogonality identity needed here is proved directly.

Proof of Theorem 1. Suppose that a circuit as in the theorem exists on $n$ input qubits and $N-n$ initially zero ancillas, with $n \le N \le n^c$. Retain any discarded qubits as idle wires and write $W$ for the resulting unitary. By Section 2, $W \in\mathcal{U}_d(N)$ after padding with identity layers. Let $O$ project the output qubit onto $|0\rangle$, and put

The Born rule identifies $p_0(x)$ with the probability of output zero, irrespective of the final states of the other qubits. Here and below the last zero denotes all initially zero ancillas.

For $h \in\{0,1\}^n$, define

Let $M_h$ be the count on the input qubits whose reference vectors are the factors of $\xi_h$. The vectors $|\xi_h,0\rangle$ and $|\xi_{\bar{h}},0\rangle$ have exact counts zero and $n$, respectively. Choose fixed $0 < s < t < 1/c$. For all sufficiently large $n$, $N^t \le n^{ct} < n$. Since $O$ is a product projection and $W^\dagger\in\mathcal{U}_d(N)$, (13) gives

Its uniformity in the count makes the same lower bound on $N$ valid for all $h$.

Averaging these complementary matrix entries gives the parity Fourier coefficient of $p_0$, namely $2^{-n}\sum_x(-1)^{|x|}p_0(x)$, where $|x|=\sum_j x_j$. To see this, note that $\langle x|\xi_h\rangle=2^{-n/2}(-1)^{h\cdot x}$, where the dot product is taken modulo two. Also, $(-1)^{\bar{h}\cdot x}=(-1)^{|x|+h\cdot x}$. Character orthogonality therefore gives

The addition in $x+y$ in the character is modulo two. For even $x$, the success guarantee gives $p_0(x)\ge1/2+\varepsilon$; for odd $x$, it gives $p_0(x)\le1/2-\varepsilon$. The even and odd classes have equal size, so the final expression in (13) is at least $\varepsilon$. But (12) bounds its absolute value by $e^{-N^s}$, which tends to zero because $N\ge n$. This contradiction proves the theorem.

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.

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 [11] 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 [25] give worst-case obstructions for symmetric functions. Throughout, discarded registers remain unrestricted.

State preparation

Gretta, Gupta, and Joshi [11] 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$ [11], Definition 2.1]. Also write

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

Corollary 8 (State-preparation obstructions). Fix a nonnegative integer $d$, $c \ge1$, $a > 0$, and $0 < \delta< 1$. For all sufficiently large $n$, every $n$-qubit reduced state $\rho$ prepared from zero inputs by an allowed depth-at-most-$d$ circuit on at most $n^c$ total qubits satisfies

Moreover, for every integer $k$ with $n^\delta\le k \le n/2$,

The remaining qubits may be discarded in arbitrary final states.

Proof. Retain all $N$ preparation qubits, including those eventually discarded, and write $\lvert\psi\rangle= U\lvert0^N\rangle$ and $Q = \lvert\psi\rangle\langle\psi\rvert$. Thus $Q$ is the conjugate by $U \in\mathcal{U}_d(N)$ of a product projection. For an output string $y$, let $P_y$ fix the $n$ output qubits to $y$ and act identically on the remaining register, and let $M_y$ count mismatches from $y$ on the outputs. Then $P_y = [M_y = 0]$ and $\lVert P_y\psi\rVert^2 = p_y$. Fix $0 < s < t < 1/c$. For sufficiently large $n$, $N^t < n$, so the complementary-string projection satisfies $\overline{P_y} \le[M_y \ge N^t]$. Localization gives

The threshold is uniform in $y$. Cauchy–Schwarz gives $\sum_y \sqrt{p_y p_{\bar{y}}} \le1$, and hence

eventually. This argument uses the pure state on the complete register, so it applies to every reduced output state $\rho$.

For the second assertion, we give the block construction underlying [10], including the estimates needed at the stated trace distance. Put

Partition the $n$ sites into $\ell$ blocks $B_j$ whose sizes $b_j$ differ by at most one. Append one zero qubit $t_j$ per block, and on $B_jt_j$ apply

Each gate equals $I-2A_j\otimes|-\rangle\langle-|$, so all these gates form one disjoint product-reflection layer, implemented by parallel one-qubit basis changes, one Toffoli layer, and the inverse basis changes. Let $\sigma_*$ be the resulting state of the $\ell$ new qubits when the input is $|D_k^n\rangle$. Its all-one probability is

For a binomial random variable $B$ with parameters $n,p$, the integer $k$ is a mode and $\operatorname{Var}(B)\le k$. Chebyshev’s inequality gives

since the displayed interval contains at most $4\sqrt{k}+1$ integers. This estimate is uniform in $n\ge2k$. The all-zero probability is $r_0=\|\Pi|D_k^n\rangle\|^2$, where $\Pi=\prod_j(I-A_j)$. To bound it, use the unit vector

Since $b_j\ge n/\ell-1$, $p\le1/2$, and $k/\ell\ge\log k$,

The commuting projections satisfy $I-\Pi\le\sum_j A_j$, so $\|(I-\Pi)\nu\|\le ek^{-3/2}$. Moreover, $|\langle\nu|D_k^n\rangle|=\sqrt{r_1}$, because every term of the Dicke state has weight $k$. Therefore

All errors here are uniform for $k\le n/2$ as $k\to\infty$. The factor four counts both complementary strings in the definition of felinity.

Apply the same block circuit to $\rho$, and call its new-qubit state $\sigma$. Trace distance contracts under a unitary and partial trace. Also, for any two states $\tau,\tau'$ with computational-basis probabilities $q,q'$, the definition gives

Thus $\operatorname{TD}(\rho,|D_k^n\rangle\langle D_k^n|)\le1/(80k)$ would imply

For large $k$, $\ell\ge\sqrt{k}$, while $k\ge n^\delta$ gives $n\le\ell^{2/\delta}$. The preparation of $\sigma$ therefore has fixed depth and polynomially many total qubits as a function of $\ell$. But $\ell^2/k\to\infty$, so its felinity exceeds $\ell^{-2}$ eventually, contrary to the first assertion applied with target size $\ell$ and exponent $a=2$. Since $k\ge n^\delta\to\infty$, all thresholds can be chosen uniformly over the allowed $k$. ∎

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 8 is measured in the number $n$ of target qubits. Gretta, Gupta, and Joshi [11], 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.

Scalar-output Fourier concentration

Gretta, Gupta, and Joshi [10], 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_{\geq k}[f_C] = \sum_{|S|\geq 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 \leq1$.

Corollary 9 (Qualitative scalar-output Quantum-LMN). For every fixed nonnegative integer $d$, there is a positive function $\gamma_d$ on the positive integers, depending only on $d$, such that $\gamma_d(k)/k^A \to\infty$ for every fixed $A>0$, and every allowed depth-at-most-$d$ circuit $C$ on $n$ inputs and $N$ total qubits, every designated output $t$, and every integer $1 \leq k \leq n$ satisfy

In particular, fix $c \geq1$, $0 < \delta\leq1$, and $B > 0$. For all sufficiently large $n$, uniformly over these circuits with $N \leq n^c$,

The sufficient threshold depends only on $d$, $c$, $\delta$, $B$.

Proof. Fix a circuit $C$ and let $Q = C^\dagger O_0 C$, where $O_0$ projects its output qubit onto $|0\rangle$. For $h \in\{0,1\}^n$, let $\xi_h$ be the Hadamard product vector from the proof of Theorem 1, and let $M_h$ count mismatches from its factors on the $n$ input qubits. For $S \subseteq[n]$, write $\mathbf{1}_S$ for its indicator string. The character calculation in (6.2), with $\bar{h}$ replaced by $h \oplus\mathbf{1}_S$, gives

since $f_C(x) = 2\langle x,0|Q|x,0\rangle- 1$. For fixed $h$, the vectors $|\xi_{h\oplus\mathbf{1}_S},0\rangle$ are orthonormal as $S$ varies, and their $M_h$ counts are exactly $|S|$. Jensen’s and Bessel’s inequalities therefore yield

For any fixed $0 < \sigma< \tau$, Theorem 2 bounds this by $4e^{-2N^\sigma}$ whenever $N$ is sufficiently large and $k \ge N^\tau$. The threshold depends only on $d,\sigma,\tau$.

It remains to obtain one function of $k$ valid for every circuit size. For each positive integer $k$, define

where the supremum ranges over all allowed depth-at-most-$d$ circuits, all designated outputs, and all input and total sizes $k \leq n \leq N$. Parseval’s identity gives $W_{\geq k}[f_C] \leq\mathbb{E}_x f_C(x)^2 \leq1$, so $0 \leq b_d(k) \leq1/k$. Fix $A \geq1$. If $N \geq k^A$, then $W_{\geq k}[f_C]/N \leq k^{-A}$. For the remaining sizes $k \leq N < k^A$, choose fixed $0 < \sigma< \tau< 1/A$. For sufficiently large $k$, we have $N^\tau< k$, so (14) gives

These two bounds are uniform over the supremum. Since $A$ is arbitrary, $b_d(k) = o(k^{-B})$ for every fixed $B > 0$. Thus the positive function

satisfies $\gamma_d(k)/k^B \to\infty$ for every $B > 0$, and the definition of $b_d$ gives $W_{\geq k}[f_C] \leq N/\gamma_d(k)$. Finally, choose $B' > (c+B)/\delta$ in this superpolynomial growth property to obtain the asserted cutoff consequence.

Majority and symmetric functions

The reductions of [25] 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 [22] gives

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

Corollary 10 (Majority and symmetric functions). Let $(f_n)$ be a symmetric Boolean family satisfying either $\rho(f_n) \geq n^\delta$ for some fixed $\delta> 0$, or $\widetilde{\deg}_{1/3}(f_n) = \Omega(n^{1/2+\eta})$ for some fixed $\eta> 0$, for all sufficiently large $n$. For every fixed $\gamma> 0$, no nonuniform family in the circuit model of Theorem 1, with fixed depth and polynomially many total qubits, computes $f_n$ with probability at least $1/2 + 1/(\log n)^\gamma$ on every input for all sufficiently large $n$. In particular, this excludes strict majority $\mathrm{MAJ}_n(x) = 1\{|x| > n/2\}$, whose transition radius is $\lceil n/2\rceil$.

Proof. Xu and Li’s Theorem 16 and Corollaries 2–3 [25] turn a family satisfying either hypothesis and the stated success bound into an exact, clean implementation of fanout on $n$ targets, with constant entangling depth and polynomially many ancillas. Their circuit convention [25] requires the measured output to be an initially zero ancilla; appending one fresh zero qubit and a CNOT from our designated output preserves its measurement distribution, even with arbitrary garbage. Their entangling depth $D$ uses at most $2D+1$ of our layers. Thus the reduction stays within fixed depth and polynomial total qubits. Hadamard conjugation on the fanout data wires gives the exact parity unitary; a zero target and its final measurement contradict Theorem 1. Finite exceptional input lengths do not affect this circuit-family contradiction.

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 10 excludes even worst-case success 2/3 for majority in the original model.

High average accuracy for majority

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

Corollary 11 (High-average-accuracy majority obstruction). For every fixed $\delta>0$, no nonuniform family $(C_n)$ in the circuit model of Theorem 1, with fixed depth and polynomially many total qubits, satisfies

for all sufficiently large $n$. Here $f_{C_n}(x)\in[-1,1]$ is the expected measured sign: the probability of output zero minus the probability of output one. Equivalently, no such family computes strict majority with average success at least $1-\frac{1}{2}n^{-\delta}$, where the average is over uniform inputs and the output measurement.

Proof. Suppose such a family exists, restrict to odd $n$, and put $g_n(x)=(-1)^{\operatorname{MAJ}_n(x)}$ and $\delta_0=\min\{\delta,1/4\}$. Since $|f_{C_n}|\le1$ and $g_n^2=1$, the asserted correlation gives

where the norm uses the uniform probability measure.

We use the following finite-size majority tail estimate: for $\varepsilon\ge n^{-1/3}$ and sufficiently large odd $n$,

This is [19], Theorem 3.5.6, p. 50. Set $\varepsilon=4n^{-\delta_0}$ and let $k_n$ be the largest odd integer at most $n^{2\delta_0}/112$. These parameters satisfy the estimate’s hypotheses for all sufficiently large odd $n.

Parseval’s identity and the triangle inequality for the Fourier coefficients at degrees at least $k_n$ now give

On the other hand, $k_n \geq\lceil n^{\delta_0}\rceil$ eventually. Applying Corollary 9 at the latter cutoff, with $B=\delta_0+1$, yields $W_{\geq k_n}[f_{C_n}] \leq n^{-(\delta_0+1)}$, a contradiction. $\square$

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