1 Introduction
The class \QAC consists of constant-depth quantum circuits with arbitrary one-qubit gates and generalized Toffoli gates of unbounded arity, using polynomially many total qubits. Ancillary qubits are initialized to zero. The supports of gates in a layer are pairwise disjoint. This last condition makes the availability of fanout a substantive question: one cannot simultaneously use a qubit as the control of arbitrarily many two-qubit gates. Moore asked whether the coherent fanout operation can be implemented in this model, and conjectured a negative answer. Its unitary parity counterpart is equivalent by Hadamard conjugation [8, 16].
We prove Moore’s parity conjecture in the measured-output model and therefore also exclude coherent fanout. The lower bound holds for bounded-error computation with a single measured output, even when the computation changes the input and leaves arbitrary garbage in the other registers.
1.1 The circuit model and the result
For x\in\{0,1\}^{n}, let
An allowed circuit acts on \lvert x\rangle\lvert0\rangle^{\otimes a}. Its gates are arbitrary one-qubit unitaries and generalized Toffoli gates
on distinct control and target qubits. Each gate has unit cost, regardless of its arity. A depth-d circuit is a product of d layers of gates with pairwise disjoint supports. There is no geometric restriction. At the end, one designated qubit is measured in the computational basis. The other registers may be discarded. Intermediate measurements, postselection, and additional fanout gates are not allowed. All gates and their complex entries may depend arbitrarily on n, but not on x.
Theorem 1.1. Fix positive integers d,k,C and a real 0<\varepsilon\le1/2. There is an integer n_0=n_0(d,k,C,\varepsilon) such that, for every n\ge n_0, every allowed circuit of depth at most d on at most C(n+1)^k total qubits has an input x\in\{0,1\}^{n} on which its answer equals \Parity_n(x) with probability strictly less than 1/2+\varepsilon.
Here total qubits means the n inputs together with all ancillary qubits. Disjoint nonempty gate supports imply that a depth-d circuit on N qubits contains at most dN gates. Thus the theorem covers the usual fixed-depth model with polynomially many gates and polynomially many ancillas: the ancillary bound gives a polynomial bound on N, and a polynomial bound on N already bounds the number of gates.
In particular, no nonuniform constant-depth family with polynomial resources computes parity with any fixed positive worst-case advantage. The theorem is eventual for each fixed depth, polynomial bound, and advantage; it permits arbitrary finite exceptions at small input lengths.
To make the connection with fanout explicit, let
For the Hadamard gate H, conjugating a controlled-NOT by H\otimes H interchanges its control and target; this follows directly from its action on the two-qubit basis. Writing F_n as the product of its commuting controlled-NOT operations gives
Thus a constant-depth polynomial-resource implementation of F_n, together with two layers of one-qubit gates and a zero target, would contradict Theorem 1.1. This also excludes Moore’s original formulation, in which the ancillary qubits must be restored to zero [16].
Theorem 1.1 also has state-preparation consequences corresponding to those of Gretta, Gupta, and Joshi [9, Corollary 4.10 and Theorem 4.14]. Let \rho be the retained n-qubit state of an allowed unitary preparation from all-zero inputs, with arbitrary final ancillas discarded. Its felinity is 2\sum_y p_y p_{\bar y}, where p_y=\langle y|\rho|y\rangle and \bar y is the bitwise complement of y. At each fixed depth and fixed polynomial total-qubit bound, for every fixed A>0, eventually every such preparation has felinity less than n^{-A}. For every fixed 0<\delta<1, eventually every such preparation and every integer k with n^\delta\le k\le n/2 also satisfy
Here trace distance is one half of the trace norm. The companion states the same bounds [18, Corollary 8 (State-preparation obstructions), Section 7.1]. The argument after the parity proof in Section 7 justifies the pointwise reductions, including exact promotion with arbitrary final garbage and polynomial total-qubit overhead.
1.2 Previous work
The classical class \mathsf{AC}^{0} allows unbounded-fan-in AND and OR gates, NOT gates, and unrestricted reuse of wires. Parity was among the first explicit functions shown to require superpolynomial size at constant depth, by Furst, Saxe, and Sipser and independently Ajtai [1, 7]; Håstad obtained almost optimal exponential bounds through the switching lemma [11]. The quantum question combines the additional expressive power of one-qubit unitaries with the disjoint-support restriction on each layer. Moore’s formulation and the counting classes studied by Green, Homer, Moore, and Pollett made the role of coherent fanout explicit [8, 16]. Constant-depth constructions with fanout further demonstrated the computational importance of that operation [12].
Early quantum lower bounds exposed the importance of the ancillary register. Fang, Fenner, Green, Homer, and Zhang proved a depth bound of order \log(n/(a+1)) for exact parity computation with a ancillas that must be restored to zero [5, Corollary 4.6]. Padé, Fenner, Grier, and Thierauf ruled out exact clean simulation at entangling depth two [19]; Fenner, Grier, Padé, and Thierauf subsequently removed the final-state cleanliness requirement for exact single-output parity at that depth [6, Theorem 6.1]. Here and in the depth-specific comparisons below, entangling depth counts only layers of multiqubit gates; arbitrary one-qubit layers may occur between them. This convention differs from our total layer count by at most a constant factor for fixed depth.
Rosenthal obtained lower bounds for approximate parity and fanout unitaries and related cat-like states, together with constant-depth approximation constructions using superpolynomial resources [20]. Approximation of a parity unitary is a stronger task than computing one measured classical bit: the latter may destroy the input and leave arbitrary garbage. Nadimpalli, Parham, Vasconcelos, and Yuen developed Pauli-spectrum methods with depth-dependent restrictions on the ancillary count [17]. Anshu, Dong, Ou, and Yao obtained lower bounds allowing barely superlinear ancillary counts [2]; Dong, Ou, and Yao developed further low-degree estimates and applications to quantum channels [4]. These resource restrictions do not cover an arbitrary fixed polynomial ancillary bound.
Joshi, Tal, Vasconcelos, and Wright ruled out exact parity at entangling depth three for sufficiently large input lengths, with no bound on the number of gates or ancillas. They also proved approximate parity lower bounds at entangling depth two for one measured output, without requiring input preservation [13]. Kintali’s September 2026 preprint reports exponentially small average parity correlation at entangling depth at most three, independently of the number of gates and ancillas, and an exponential gate lower bound for exact parity at entangling depth at most four [14, Theorems 1–2].1 These depth-specific statements do not cover every fixed depth. Gretta, Gupta, and Joshi characterize the general parity question through Fourier concentration [9], while Xu and Li extend related fanout reductions to symmetric functions [22]. Our theorem permits every fixed depth and every polynomial total-qubit bound simultaneously. All structural statements needed for its proof are established below.
The companion article Product-projection localization and the QAC0 parity lower bound proves a uniform operator-norm localization theorem and an independent parity lower bound [18, Sections 2 and 6]. The present article instead proves state-dependent propagation, projection insertion, and pruning for regular trajectories. Both arguments use product-projection counts and elementary Chebyshev filters; neither structural theorem is used to prove the other.
1.3 The proof and its main tools
A generalized Toffoli gate is a reflection I-2P, where P is a product of one-qubit rank-one projections. This representation suggests counting how many local factors of a product test fail. A single such gate can couple arbitrarily many qubits, so its conjugation need not preserve small operator support. Moreover, product-projection filters can have large norms away from the count range where they approximate well. Controlling the state on which each approximation is used is therefore essential. Informally, a trajectory sequence is regular when, for every sufficiently small collection of reflections in a layer, the combined count of failures of their local factors has a rapidly decaying tail on the state entering that layer. The precise definition is asymptotic and allows arbitrary gates and states at each circuit size.
Polynomial locality and concentration have been related in work of Kuwahara, Arad, Amico, and Vedral and of Anshu and Metger [3, 15]. In the circuit setting, Pauli concentration and low-degree approximation are central to the works just discussed. An operator has degree at most \ell when it is a sum of operators supported on at most \ell sites each. We retain the elementary link between this degree and the number of product-basis coordinates an operator can change. The additional steps here are two-sided tail transport and stability under a product projection, which permit a trajectory to be made regular by a state-dependent pruning rule.
The first tool, Proposition 4.1, transports operators of low degree along a regular trajectory, with an arbitrarily small fixed loss in the degree exponent. Its conclusion is an approximation on the trajectory vector. The second tool, Proposition 6.1, shows that regularity survives insertion of an arbitrary product projection followed by reverse evolution. The key step is Lemma 5.1, which compares two regular trajectories. One polynomial detects a tail at the starting end; another approximates the product projection at the finishing end. They are applied on different sides of an inner product, so their large global norms are paid for by the appropriate tail estimates.
Projection stability then makes regularity available without an initial assumption on the circuit. Starting from a product state, we retain a reflection when its projection has probability at least m^{-6} on the current state, where m is the number of qubits. The retained layer is regular, and the deleted gates change the state by at most 2m^{-2} per layer. Iterating this rule yields a regular trajectory close to the original evolution (Proposition 6.5). The stability and propagation statements concern arbitrary product tests and regular trajectories, rather than parity alone.
Finally, we copy each basis input into a reference register that the subsequent computation leaves untouched. On the uniform coherent input, worst-case parity success becomes a signed acceptance expectation bounded away from zero. The pruned circuit has almost the same expectation. Write W for that circuit, \psi_0 for the initial product state, and P_B for the accepting output projection. The copying gates survive pruning, so conjugating the reference sign back through W sends \psi_0 to a vector with exactly n excitations relative to the initial product state \psi_0. The signed expectation pairs this vector with W^\dagger P_BW\psi_0, whose tail for that same count is bounded by Corollary 6.2. Because the total number m of qubits is polynomially bounded in n, a sufficiently small fixed h>0 can be chosen with m^h=o(n), separating these two scales and giving the contradiction.
Sections 2 and 3 introduce the formalism and the polynomial filters. Section 4 proves low-degree propagation, and Section 5 establishes tail transport. Projection stability and pruning are proved in Section 6; Section 7 completes the parity argument.
2 Product tests and regular trajectories
We work on the Hilbert space (\C^2)^{\otimes m}. Vector norms are Euclidean norms, and operator norms are the induced norms. Unless explicitly stated otherwise, every starting vector has norm at most one. Products of orthogonal projections used in the analysis are applied without renormalizing the resulting vectors. All projection insertions below are analytic devices; the permitted circuit operations remain unitary until the final output measurement.
2.1 The gate model and product tests
The physical circuit has n input qubits, a ancillary qubits initialized to \lvert0\rangle^{\otimes a}, and a designated output qubit measured in the computational basis. Its gates are arbitrary one-qubit unitaries and the generalized Toffoli gates of Section 1. Gates in each layer have pairwise disjoint supports, and each gate counts once regardless of its arity. The gates may depend arbitrarily on the input length, including through their complex entries, but are independent of the input string. No input or ancillary register is required to be restored, and the output qubit may be an original input qubit. All other qubits may be discarded after the output is measured. There are no intermediate measurements, postselection operations, geometric restrictions, or extra fanout gates.
For the analysis, we allow a reflection
where J_g is a nonempty set of sites and each v_{g,j} is a unit vector. The tensor factors are understood to occupy their indicated sites. Each P_g is an orthogonal projection, so R_g=R_g^\dagger=R_g^{-1}. A generalized Toffoli with c\ge1 distinct controls z_1,\ldots,z_c and a distinct target b has this form with
and identities elsewhere. Indeed, it acts trivially unless all controls are one, and on that control subspace its target action is I-2\lvert-\rangle\langle-\rvert=X. This product-reflection viewpoint also appears in Rosenthal [20].
An analytic layer will be either a product of such reflections on pairwise disjoint supports, or a tensor product of one-qubit unitaries. Splitting a physical layer into its two gate types preserves its operation, because its gates have disjoint supports. Thus a physical circuit of depth d gives at most 2d analytic layers. We use t for their number and m for the total number of qubits, including any reference qubits subsequently introduced. Empty layers are permitted. Every reflection layer has at most m gates, since their supports are nonempty and disjoint.
Definition 2.1 (Product test). A test A consists of a subset J_A\subseteq\{1,\ldots,m\} and a specified unit vector v_{A,j} at each j\in J_A. Its excitation count and zero projection are
Here a subscript j extends a one-site operator by identity at all other sites, and \one_{H_A\in E} denotes the spectral projection of H_A onto the set E\subseteq\mathbb R. The empty test has H_A=0 and P_A=I.
The summands of H_A are commuting orthogonal projections. Choosing the basis (v_{A,j},v_{A,j}^{\perp}) at each tested site diagonalizes them simultaneously. Consequently its spectrum is contained in \{0,1,\ldots,|J_A|\}, and 0\le H_A\le mI. We use spectral inequalities such as H_A\ge x also when x is not an integer.
For a set S of gates in one reflection layer, disjointness makes their specified local factors a single test. We write H_S for its count and P_S=\prod_{g\in S}P_g for its zero projection. If F is the whole reflection layer, then
Indeed, a gate in S commutes with each of its own local factors, while other gates have disjoint supports. Every spectral projection of H_S therefore commutes with F as well. If H_A retains only some sites of this test, then H_A and H_S are diagonal in the same product basis, H_A\le H_S, and
2.2 Asymptotic sequences and uniformity
All asymptotic statements concern an arbitrary sequence indexed by \nu\in\mathbb N, with total qubit counts m_\nu\to\infty and a bounded number of analytic layers. The states, tests, gates, and circuits can all vary with \nu. We suppress \nu and write m for m_\nu; thus “eventually” means at all sufficiently large sequence indices. Every exponent appearing in an estimate is a fixed real number independent of \nu. Padding with empty layers gives a common bound on length. When a fixed layer pattern is convenient, one may restrict to a subsequence with fixed length and layer types: there are only finitely many such patterns. An eventual assertion on every such subsequence yields the assertion on the original sequence, since any infinite set of violations has an infinite subsequence with one fixed pattern.
The following elementary observation will also supply uniformity over tests chosen from the current state.
Lemma 2.2 (Uniformity from arbitrary choices). Fix a sequence of base data, and let \mathcal D_\nu be the nonempty set of permitted auxiliary choices at index \nu. Suppose that for every sequence D_\nu\in\mathcal D_\nu and every fixed admissible parameter tuple \theta, an assertion \mathcal E(\nu,D_\nu,\theta) holds eventually. Then, for every fixed \theta, there is an index \nu_0 such that
The same conclusion holds if the premise is proved on every subsequence on which the base hypotheses remain valid.
Proof. Fix \theta. If the conclusion fails, there are increasing indices \nu_i and choices D_{\nu_i}\in\mathcal D_{\nu_i} violating the assertion. Choose arbitrary permitted values at the other indices. The resulting sequence of choices contradicts the premise. In the subsequence version, apply the premise directly to the violating subsequence.
The lemma imposes no cardinality or finiteness requirement on \mathcal D_\nu. In particular, a permitted test may depend on the exact state at its index. The eventual threshold may depend on the fixed tuple \theta; no threshold uniform over all real exponent tuples is asserted.
Definition 2.3 (Regular trajectory). Write V=U_t\cdots U_1 for analytic layers and set \xi_j=U_j\cdots U_1\xi_0, where \norm{\xi_0}\le1. The sequence of these trajectories is regular if the following holds at every reflection layer U_j: for every fixed triple
eventually, simultaneously for every set S of at most m^b gates of that layer,
There is no regularity condition at one-qubit layers. Regularity is a property of an asymptotic sequence, not of a single finite circuit.
Commutation with H_S gives
at a reflection layer, so either endpoint can be used in (2.1). It follows that reversing a regular trajectory is regular for the inverse circuit: inverse reflection layers are the same layers, and inverse one-qubit layers impose no condition. Restricting a regular trajectory to any segment or subsequence preserves regularity. Multiplying each trajectory by a scalar of modulus at most one also preserves it. For any fixed use of regularity, finitely many auxiliary exponents and layers may be handled simultaneously by taking the maximum of their eventual thresholds. This does not require a common threshold for all admissible exponents.
2.3 Operator degree and excitation shifts
Definition 2.4 (Operator degree). An operator is supported on J\subseteq\{1,\ldots,m\} if it has the form E_J\otimes I_{J^c}. It has degree at most the nonnegative integer \ell if it is a finite sum of operators each supported on at most \ell sites. An assertion \deg E\le x for real x\ge0 means \deg E\le\lfloor x\rfloor.
Degree bounds survive sums, while products have degree at most the sum of the factors’ degrees: expand into supported terms and take the union of each pair of supports. Taking adjoints preserves degree, as does conjugating by a tensor product of one-qubit unitaries. No bound on the number or norms of terms in a support decomposition is part of the definition.
The following support constraint is the elementary locality principle behind the connection between polynomial approximation and Hamming concentration; compare Anshu and Metger [3, Lemmas 2.10–2.11]. We record its exact form for arbitrary product tests.
Lemma 2.5 (Degree controls excitation shifts). Let \ell be a nonnegative integer. If \deg E\le\ell and A is any test, then
In particular, for every real x,
If Q is a polynomial of degree at most \ell, then \deg Q(H_A)\le\ell.
Proof. First let E be supported on a set J of size at most \ell. Decompose H_A into the counts on J_A\cap J and on J_A\setminus J. In the product basis for the test, a matrix element of E can be nonzero only when the states outside J agree, so their excitation count is unchanged. Each count inside J is between zero and |J_A\cap J|. The total counts can therefore differ by at most |J|\le\ell. This proves the block assertion for a supported term, hence for their sum. Summing the forbidden blocks gives the two displayed consequences.
Finally, expanding H_A^j produces sums of products of j one-site operators. Each product is supported on at most j sites, even when a site occurs more than once. Expanding Q into powers of H_A proves the last assertion, including its constant term.
3 Two polynomial filters
We need two different polynomials in excitation counts. The first approximates the zero projection on an initial part of the integer spectrum. The second detects a tail while remaining nonnegative on the whole real line. Both may grow outside their effective ranges; explicit bounds on that growth will be essential. The zero filter combines normalized Chebyshev approximation with exact roots at the first positive integers, a classical approximation-and-interpolation construction for symmetric predicates; see Sherstov [21, Section 3.1 and Lemma 3.9]. We give the construction and its estimates explicitly because transport requires control of the polynomial over the entire count interval, as well as accuracy on the initial integer range.
3.1 An elementary Chebyshev construction
Define real polynomials C_\ell by
The cosine and hyperbolic cosine addition formulas satisfy this same recurrence and initial values, so
Thus |C_\ell(y)|\le1 for -1\le y\le1, and C_\ell is positive and nondecreasing on [1,\infty). We also have the elementary global bound
Indeed, writing M=2|y|+1\ge1, the initial cases hold, and the recurrence gives 2|y|M^\ell+M^{\ell-1}\le M^{\ell+1} because 2|y|M+1\le M^2.
For 1\le a<R\le m, define
The denominator is a positive real constant. As x increases from zero to a, y(x) decreases from y(0)>1 to one; as x increases from a to R, y(x) decreases from one to minus one. The preceding formulas therefore imply
Whenever a\le R/2, we have R-a\ge1. For every x\in[0,m] it follows that |y(x)|\le1+2m\le3m. Since C_\ell(y(0))\ge1, (3.1) yields the uniform bound
For a useful exact expression for the denominator, put z=\sqrt{a/R}. Defining
direct substitution into the exponential formula for \cosh gives
Moreover, integration of (1-w^2)^{-1} between zero and z gives
Consequently, if \tau_0=2\operatorname{artanh}\sqrt{a/R}, then
as a/R\to0. These facts prove all the approximation estimates below.
3.2 Approximating the zero projection
Lemma 3.1 (Integer zero filter). Fix 0<q<L<1 and r>(q+L)/2. For all sufficiently large integers m there is a real polynomial Q such that
and, for every integer j with 0\le j\le m^L,
In fact the construction has Q(0)=1 exactly.
Proof. Set
Eventually a\le R/2, since q<L. The denominator estimate above and \cosh x\ge e^x/2 for x\ge0 give
Define
Then Q(0)=1, and Q vanishes at each integer from one through a. For 0\le x\le m, the product has absolute value at most (m+1)^a. For a\le x\le R, (3.2) therefore gives
This proves the required accuracy at all the integer arguments. Accuracy between the integers in (0,a) is neither claimed nor needed.
For the degree and global size, put \beta=(q+L)/2. Since q<\beta,
The estimate (3.3) holds on the entire real interval [0,m], including between the small integer roots, and gives
In particular,
For any fixed r>\beta, both the degree and this logarithmic bound are at most m^r eventually. Indeed, every fixed power of \log(2m) is o(m^{r-\beta}), as is seen by setting w=\log m and comparing a polynomial in w with e^{(r-\beta)w}.
Since every H_A has integer spectrum, this is a projection approximation in the required sense. More explicitly, with \Pi=\one_{H_A\le m^L}, the spectral theorem gives
For every vector \xi, splitting into the two spectral ranges yields
Its operator degree is at most m^r by Lemma 2.5.
3.3 A nonnegative tail detector
Lemma 3.2 (Tail filter). Fix 0<v<h<u\le1 and s>0. Let k be a degree exponent satisfying k>s+(u-h)/2. For all sufficiently large integers m, there is a real polynomial T with
and
Proof. Set
Eventually a\le R/2, and (3.2) gives 0\le B\le1 on [0,R]. The denominator satisfies C_\ell(y(0))\ge\cosh6 by (3.4). Hence, on [a,R],
For example, \cosh6\ge1+6^2/2=19 proves the last strict inequality.
We next verify uniformly that B(x)\to0 on [0,m^v]. Put z=\sqrt{a/R}, which tends to zero, and for this low range put
These are positive eventually because m^v/a\to0. The same hyperbolic identity gives
Now
Also 0<z_x\le z in this range. The inequalities (3.4) show uniformly that \operatorname{artanh}z_x/z_x\to1 and \operatorname{artanh}z/z\to1. Both hyperbolic cosine arguments therefore tend uniformly to six. Their ratio tends uniformly to one, which proves 0\le B(x)\le1/8 on [0,m^v] eventually.
Choose an odd integer J with 10m^s\le J<10m^s+2 and define the majority polynomial
For z\in[0,1] its summands are nonnegative and their full binomial sum is one, so 0\le M_J(z)\le1. On 0\le z\le1/8,
Changing the summation index in the complementary binomial sum gives M_J(1-z)=1-M_J(z), since J is odd. Therefore M_J(z)\ge1-2^{-J/2} for 7/8\le z\le1.
Take
This square of a real polynomial is nonnegative at every real argument. It lies in [0,1] on [0,R]. On [0,m^v] it is at most 2^{-J}\le\exp(-m^s), since J\ge10m^s and 10\log2>1. On [a,R] it is at least (1-2^{-J/2})^2\ge1/4 eventually.
It remains to control its degree and its growth on [0,m], where B need not lie in [0,1]. Write A=(7m)^{2\ell}\ge1. By (3.3), throughout this whole interval,
Taking absolute values in the binomial formula, and then including all indices in its sum, gives
Thus the required global estimates, including the final square, are
With \beta=s+(u-h)/2, we have \ell J=O(m^\beta), and hence
The fixed strict inequality k>\beta makes each bound at most m^k eventually. This proves the lemma, including the endpoint case u=1.
Evaluating T at a count operator gives a positive semidefinite operator of degree at most m^k and norm at most e^{m^k}. In particular, its global nonnegativity prevents contributions from outside [m^h,m^u] from cancelling the detected tail in a quadratic form.
4 Propagation of low-degree perturbations
Pauli expansions and low-degree approximations have been used to study \QAC [2, 4, 17]. Here regularity lets us replace the large product projections arising from conjugation by polynomials of small degree. The resulting approximation controls a perturbed vector along an exact reference trajectory.
Proposition 4.1 (Low-degree propagation). Let V be a circuit with a bounded number of analytic layers, and suppose the trajectory from \zeta, with \norm{\zeta}\le 1, is regular for V. Here k,K denote degree exponents: fix 0<k<K<1. For every operator E with
there is, eventually, an operator E' such that
The starting vector need not be a product vector.
Proof. We first prove the one-layer assertion with the stronger error o(\exp(-m^k)). Conjugation by a layer of one-qubit unitaries preserves both degree and operator norm and gives zero error. It remains to consider a layer
of reflections on pairwise disjoint supports. Set \xi=F\zeta.
A controlled local expansion. On one qubit use the unitary matrices I,X,Z,XZ, where
Their tensor products form an orthonormal basis for the inner product 2^{-m}\Tr(A^\dagger B). Thus the unique expansion of E is
Put \ell=\lfloor m^k\rfloor. Every summand in any degree-\ell decomposition of E has zero coefficient against a tensor D whose support is not contained in that summand’s support: a nonidentity factor of D outside the support has trace zero. Consequently c_D=0 whenever \abs{\supp D}>\ell. This conclusion requires no bound on the norms or coefficients of the original decomposition. Also,
because \abs{\Tr M}\le 2^m\norm{M} for every operator on m qubits. There are at most
possible nonzero coefficients, and hence \sum_D\abs{c_D}\le \exp(m^k)N_m.
Fix one such D, supported on J, and let \mathcal T be the gates whose supports meet J. Disjointness gives \abs{\mathcal T}\le\abs J\le\ell. All other reflections commute with D and cancel in FDF^\dagger. With P_{\mathcal L}=\prod_{g\in\mathcal L}P_g and empty products interpreted as identities, expansion on both sides gives
Factor the Hilbert space across J and J^c, writing D=D_J\otimes I and P_g=A_g\otimes B_g. The factors A_g and B_g are the corresponding product projections, possibly identities. If A_{\mathcal L}=\prod_{g\in\mathcal L}A_g, then each term factors as
Indeed, the exterior factors have disjoint supports for distinct gates, and repeated factors satisfy B_g^2=B_g. The operator M has norm at most one. Its displayed order is retained; no projection on J has been commuted through D_J. The sum of the absolute scalar coefficients in this expansion is
Replacing the exterior projections. Let H_Q count failures of the one-qubit factors of Q, extended by identity outside their sites. Thus Q=\one_{H_Q=0} on J^c; when this test is empty its count is zero. The operator H_Q is a partial sum of the commuting site counts in H_{\mathcal T}. In their common eigenbasis, its value is at most that of H_{\mathcal T}.
Choose fixed exponents
Such a choice exists since (L+p_1)/2<L; in particular, k<p_1<r<p_2<L<K. Regularity, used with (b,h,p)=(k,L,p_2), holds uniformly over \mathcal T and gives
Here the reference vector is exactly F\zeta, before applying M.
By Lemma 3.1, choose a real polynomial f of degree at most m^r, bounded in absolute value by \exp(m^r) on [0,m], whose error in approximating \one_{x=0} is at most \exp(-m^{p_1}) at every integer 0\le x\le m^L. The spectrum of H_Q is integral. Splitting \xi into counts at most m^L and larger counts therefore yields
In this display Q and f(H_Q) act as identity on J. Applying the contraction M afterwards cannot increase the error.
Define E_F by replacing each exterior Q in the expansion of FEF^\dagger by f(H_Q), retaining its coefficient and its factor M. The total absolute coefficient mass is at most
It follows that
eventually. To check the second inequality, use \log\Lambda_m=o(m^{p_1}), r<p_2, and p_1<p_2; each of the two bracketed contributions, after multiplication by \Lambda_m, is absorbed by the displayed bound.
Each new term has degree at most \ell+m^r: its factor on J has support size at most \ell, and expanding the polynomial in one-site counts gives degree at most m^r on the remaining sites. Its norm is at most \exp(m^r). Thus, eventually,
because k<r<K and \log\Lambda_m=O(m^k\log m). This proves the stronger one-layer assertion, uniformly over the admissible E.
A bounded number of layers. Pad by identity layers so that V=U_t\cdots U_1 has a fixed number t of layers. The case t=0 is immediate with E'=E. For t\ge1, choose a fixed increasing chain
Let \zeta_0=\zeta and \zeta_i=U_i\zeta_{i-1} be the exact regular reference trajectory. Set E_0=E and apply the one-layer result successively with exponents (k_{i-1},k_i) to obtain E_i with degree at most m^{k_i}, norm at most \exp(m^{k_i}), and local residual
For the exact perturbed evolution \eta_0=E\zeta, \eta_i=U_i\eta_{i-1}, put r_i=\eta_i-E_i\zeta_i. Then r_0=0 and the exact recurrence is
Unitarity implies
eventually. In particular, no later approximating operator acts on an earlier residual. Taking E'=E_t proves (4.1).
5 Transporting excitation tails
The next lemma compares two regular trajectories joined at their final endpoint by a product projection. Its proof uses the two filters of Section 3 in different directions. A tail filter T is propagated forward along the projected trajectory, producing an effective range on which the final projection can be approximated by a polynomial D. That polynomial is then propagated backwards along the original trajectory. The resulting scalar product is small because T suppresses low counts while the original vector has small high-count tails. Positivity of T converts this estimate into a tail bound for the projected vector.
Lemma 5.1 (Tail transport). Let V have a bounded number of analytic layers, let A and B be tests at its initial and final endpoints, respectively, and put
Assume that both the trajectory from \psi and the trajectory from \chi are regular for V. Fix 0\le b<1. Suppose that, for every fixed b<h<1 and 0<p<h, eventually
Then, for every such fixed pair h,p, eventually
The tests and vectors may vary along the sequence, and \chi is not normalized.
Figure 1 records the two uses of regularity. The forward propagation concerns T\chi, whereas the reverse propagation concerns DV\psi. Neither filtered vector is assumed to have a regular trajectory. In the diagram, K is the degree exponent produced by forward propagation. The zero filter D has degree at most m^r. Reverse propagation approximates V^\dagger DV\psi by G\psi, where G has degree at most m^{r'}; the proof below constructs these objects and proves the displayed bounds.
Figure 1: The two transports in Lemma 5.1. The forward step establishes a tail bound for VT\chi outside the count range m^K; the projection approximation is estimated on this vector. The backward step acts on the unfiltered reference V\psi. Its error is paired with T\chi, whose norm is bounded by two.
The proof descends from the automatic zero tail above m to the requested threshold. At one step, a known tail bound above m^u controls the tail filter’s global growth while the filter detects the new band m^h\le H_A\le m^u. The following lemma supplies compatible exponent gaps for this step. Here u,h are the exponents for the old and new count thresholds, with tail precision exponents u-\alpha and h-\beta. The tail filter has suppression exponent s and degree and logarithmic norm bounds with exponent k, enlarged to K under forward propagation; the zero filter has precision exponent q and degree and logarithmic norm bounds with exponent r, enlarged to r' under reverse propagation. Finally, v_0<v are initial count cutoff exponents, and \theta is the precision exponent used for the assumed input tail above m^{v_0}.
Lemma 5.2 (Exponent budget). Suppose
There are fixed exponents q,k,K,r,r',s,v_0,v,\theta satisfying
All these inequalities have strictly positive margins independent of m.
Proof. Write \eta=u-h and choose \alpha<\lambda<\nu<\beta. Set
Then q>h-\beta>0, k-q=\eta+\nu-\lambda>0, and k<h because \lambda>\alpha>\eta. In particular k<1. Choose
The interval available for the remaining filter exponents has width
With a_0=(K+q)/2, take
Thus
These choices give q<r<r'<s<k<h, as well as k<u-\alpha. Since \max\{b,r'\}<h, choose v_0,v strictly between these endpoints in the stated order and then choose r'<\theta<v_0. Each choice is made among fixed real numbers.
Proof of Lemma 5.1. Fix target exponents b<h_*<1 and 0<p_*<h_*. Set
Here N\ge1 is fixed and 0<\eta\le\delta/2. Define
We descend from h_0=1 to h_N=h_*, proving at step i\ge1 that
To start, the tail strictly above m^{h_0}=m is zero, since the spectrum of H_A is contained in \{0,\ldots,m\}. No estimate on the eigenspace of count m, and no regularity condition at exponent one, is needed.
Fix a step and abbreviate
Its induction hypothesis is
For i>1 this follows from the preceding, stronger inclusive bound. The parameters obey the hypotheses of Lemma 5.2: indeed, u-h=\eta<\delta\le\alpha and \beta\le2\delta<h_*\le h. Choose its exponents once for this step. All subsequent estimates are for sufficiently large m.
Forward propagation on the trajectory of \chi. Apply Lemma 3.2 with parameters v,h,u,s,k, and write T=T(H_A) for its polynomial evaluated at the initial count. It is self-adjoint and nonnegative. Its degree is at most m^k, its global norm is at most \exp(m^k), and
because \norm{\chi}\le1. Splitting at the previous scale gives
This is the first use of a global polynomial norm; it is paid for by k<u-\alpha.
Proposition 4.1, applied with exponents k<K to the regular reference trajectory from \chi, gives an operator E such that
The endpoint V\chi=P_BV\psi has exactly zero H_B count. By Lemma 2.5, \one_{H_B>m^K}EV\chi=0. Therefore the filtered vector has the effective-range bound
Approximating the final projection on the controlled side. Use Lemma 3.1 with precision exponent q, range exponent K, and degree exponent r. These satisfy 0<q<K<1 and r>(K+q)/2. Write D=D(H_B) for the resulting self-adjoint operator. It has degree at most m^r, norm at most \exp(m^r), and error at most \exp(-m^q) from P_B on every integer count at most m^K. The preceding bound and \norm{VT\chi}\le2 imply
Here q<r<k absorbs the global norm of D on the remaining tail. Only integer approximation is used, as required for the spectrum of H_B.
Let a_m=\ip{\chi}{T\chi}\ge0. Since T is self-adjoint and V\chi=P_BV\psi,
Moving the self-adjoint difference P_B-D to the first argument gives
Thus the projection is approximated on VT\chi, the vector for which an effective count range has just been proved.
Reverse propagation on the trajectory of \psi. The reversed trajectory starting at V\psi is regular for V^\dagger. Applying Proposition 4.1 to D with exponents r<r' gives an operator G satisfying
This application uses the unfiltered reference vector V\psi. In the scalar product its error is multiplied by the vector norm \norm{T\chi}\le2, so
The global operator norm of T introduces no factor here.
Splitting the scalar product by the initial count. Put Q=\one_{H_A\le m^v}. Its low-count contribution satisfies
For the high-count contribution, first observe that m^{v_0}+m^{r'}<m^v eventually. The degree-shift property implies
Using (5.1) with threshold exponent v_0>b and precision exponent \theta<v_0 gives
Orthogonality of Q and I-Q now yields
since s>r'>q and \theta>r'>q. These two strict gaps pay for the two uses of the global norm of G. In particular there is a constant C_0, independent of m, with
eventually. No commutation between G and the count projections has been assumed.
Positivity and descent. The tail filter is at least 1/4 on [m^h,m^u] and nonnegative on the entire spectrum. Consequently
Combining this band with the previous upper tail gives
Set a=h-\beta>0. The exponent budget gives q>a, and u-\alpha-a=(u-h)+(\beta-\alpha)>0. Multiplying the last right-hand side by \exp(2m^a) therefore makes both terms tend to zero. Taking the square root proves
eventually, closing the descending step. The strict power gap q>a absorbs the square root and all fixed constants.
There are only N descending steps. Each uses Proposition 4.1 over the same bounded number of layers with fixed positive exponent gaps K-k and r'-r. These gaps can be subdivided into that fixed number of positive increments as in its proof. Different descending steps retain only the improved tail assertion; their approximating operators are not composed. Thus every choice and every number of steps is independent of m, and the finitely many eventual estimates hold simultaneously after increasing the threshold for m.
At the final scale,
The final induction bound implies the desired estimate at h_*,p_*. Since these targets were arbitrary, the lemma follows.
6 Projection insertion and pruning
The tail-transport lemma assumes regularity of two trajectories. We first use it on successively longer suffixes to show that inserting a product projection preserves regularity. Two consequences for product starting states will then allow us to construct regular trajectories by deleting reflections with small projection probability. Gate deletion by a telescoping estimate also appears in the Pauli-spectrum approach of Nadimpalli et al. [17, Lemma 23 and Claim 24], where width controls a Frobenius-norm error. Here deletion depends on projection probability in the actual pruned-prefix state; the retained layer must then satisfy the regularity condition for every fixed exponent triple.
Proposition 6.1 (Projection insertion). Let W=U_t\cdots U_1 have a bounded number of layers, and suppose the trajectory
is regular, with \norm{\psi_0}\le1. For any product test B at the output, set
Then the trajectory (\chi_j)_{j=0}^t is regular for W.
Proof. All the vectors \chi_j have norm at most one. We prove their regularity at the layers in decreasing order of the layer index. Suppose regularity has already been established at every layer strictly after layer j. There is nothing to prove if U_j is a layer of one-qubit unitaries. Otherwise, fix 0\le b<1 and choose, at each member of the circuit sequence, a set S of at most m^b reflections in this layer. Let H_A=H_S be their joint count and put
This is the suffix strictly after layer j, and \chi_j=V^{\dagger}P_BV\psi_j. The trajectory of \psi_j on V is regular by hypothesis; that of \chi_j on V is regular by the induction hypothesis. Regularity of the original trajectory at layer j also gives, for every fixed b<h<1 and 0<p<h,
Lemma 5.1 therefore gives the same estimate for \chi_j. The count H_S commutes with every reflection of layer j, so this estimate holds on \chi_{j-1} as well.
The chosen sets S may vary with the circuit sequence. For each fixed triple (b,h,p), Lemma 2.2 consequently makes the estimate eventual and uniform over all eligible S. This proves regularity at layer j and completes the induction. Its first step uses the empty suffix, whose regularity hypotheses are vacuous.
Corollary 6.2 (Tail at a product input). Suppose \psi_0 is a normalized product state and its trajectory under W is regular. Let P_0=|\psi_0\rangle\langle\psi_0| be the full product projection and H_0 its count. For any product test B at the output and every fixed 0<p<h<1,
Proof. The original trajectory is regular by assumption and the projected trajectory is regular by Proposition 6.1. Since H_0\psi_0=0, the input-tail hypothesis of Lemma 5.1 holds with b=0. Applying that lemma to V=W proves the claim.
Corollary 6.3 (Overlap and output tail). Under the hypotheses of Corollary 6.2, write \psi_t=W\psi_0. For any product test B at the output and every fixed 0<p<h<1,
For each fixed (h,p), both this estimate and (6.1) hold eventually uniformly over the output test B.
Proof. Put \chi_t=P_B\psi_t and q_B=\norm{P_B\psi_t}^2. Apply Lemma 5.1 to the reverse circuit V=W^{\dagger}, starting at \chi_t, with initial count H_B and final projection P_0. The starting vector has zero H_B count. Its trajectory is regular by Proposition 6.1 and reversal. The projected-and-returned vector is exactly
Its reverse trajectory is the original trajectory multiplied by q_B\in[0,1], hence is regular too. The lemma, with b=0, now gives (6.2). In particular, the multiplier is the probability q_B, not its square root: no projected vector has been normalized.
For uniformity, fix (h,p) and suppose that either estimate fails for some test at arbitrarily large indices. Choose a violating test at those indices and any test at the others. The resulting single sequence of tests contradicts the estimate just proved. Thus tests may be selected using the exact circuit and its output state. The threshold may depend on the fixed exponents; no threshold uniform over all real exponent pairs is asserted.
Lemma 6.4 (A retained layer is regular). Let W have a regular trajectory from a normalized product state, and write \psi=W\psi_0. Consider a proposed next layer of disjoint reflections I-2P_g. Retain precisely the gates satisfying
The retained layer is regular on \psi, and hence after its action on \psi as well.
Proof. The mean bound and Markov’s inequality put substantial mass on low-weight product-basis outcomes. Counting these outcomes yields one of sufficiently large probability; recentering the test there changes every count by at most the outcome’s weight, so Corollary 6.3 supplies the required tail estimate.
We first bound the mean count of each retained gate. Fix \epsilon>0 and choose fixed exponents 0<p_0<h_0<\min\{\epsilon,1\}. Applied to the test of a retained gate, (6.2) gives
Since 0\le H_g\le mI and \norm{\psi}=1, spectral decomposition therefore gives
Corollary 6.3 makes this bound uniform over the retained gates.
Now fix a regularity triple 0\le b<h<1, 0<p<h, and choose \epsilon>0 so that b+2\epsilon<h. For any set S of at most m^b retained gates, disjointness of the supports gives
The empty set has zero tail, so we may suppose S is nonempty. Consider the distribution obtained by measuring the tested sites in the product basis consisting of each specified state and its orthogonal complement. Label the outcomes by binary strings, with 0 for the specified state. The Hamming weight of the resulting string is the measured value of H_S. With
Markov’s inequality puts at least half the probability on strings of weight at most R. If M\le m sites are tested, the number N_R of such strings satisfies, eventually,
Consequently one such outcome z has probability
Only linearity of the mean, Markov’s inequality, and counting have been used; the outcomes need not be independent.
Let B specify the local states of z on the tested sites and leave all other sites unconstrained. Then \rho=\norm{P_B\psi}^2. The operators H_B and H_S are diagonal in the same product basis. At a site where z is 0 their count terms agree; at a site where z is 1 they differ by an operator of norm one. Thus their eigenvalues on every common basis vector differ by at most |z|\le R. Choose fixed exponents
Because b+\epsilon<h'<h, eventually m^h-R\ge m^{h'}. The common basis then gives the spectral inclusion
Apply (6.2) to B with exponents (h',p'), and divide by its probability from (6.5):
The last inequality uses both p'>\beta and p'>p.
For each fixed target triple, the preceding bounds are uniform over S and its selected outcome z. Indeed the endpoint estimate is uniform over all product tests, including those selected from the current state. Equivalently, a sequence of violating choices would contradict Corollary 6.3 on that subsequence. Only finitely many auxiliary exponent choices were made for this triple. All uses of the corollary concern the already regular prefix W; the proposed next layer is not among its hypotheses. We have proved regularity before the retained layer, and commutation of H_S with that layer gives the same property afterward.
Proposition 6.5 (Pruning from a product state). For any sequence of circuits U=U_t\cdots U_1 on m qubits, with a bounded number t of analytic layers, and any normalized product starting states \psi_0, the following construction produces a circuit W with a regular trajectory from \psi_0. Leave all one-qubit layers unchanged. At a reflection layer, use the exact state reached by the pruned prefix and retain exactly the gates in (6.3). The output vectors satisfy
Proof. The empty prefix is regular. Appending a one-qubit layer adds no regularity condition, and Lemma 6.4 applies at each reflection layer. Induction therefore gives regularity of the whole pruned trajectory. The retention rule itself has no exponent choices: the auxiliary exponents above are used only to verify its regularity for each fixed triple.
For the error estimate, denote the retained version of layer U_j by \widetilde U_j and the exact pruned-prefix state before it by \psi_{j-1}. Each deleted reflection F_g=I-2P_g satisfies
Every other gate in that layer commutes with P_g, and is unitary. Hence this norm is unchanged if any other gates of the layer have already acted. Telescoping over the deleted gates, of which there are at most m because their nonempty supports are disjoint, yields
This bound is zero for a one-qubit layer. If \phi_j and \psi_j are the original and pruned states after layer j, respectively, then exactly
Unitarity and the triangle inequality give \norm{\phi_j-\psi_j}\le\norm{\phi_{j-1}-\psi_{j-1}}+2m^{-2}. Starting with \phi_0=\psi_0 proves (6.6).
7 The parity contradiction
We now prove Theorem 1.1. Reference qubits retain the classical input labels while the computation may freely change all its own registers. Their signed acceptance expectation will be bounded away from zero by correctness and forced to zero by Corollary 6.2.
Proof of Theorem 1.1. Fix positive integers d,k,C and 0<\varepsilon\le1/2, where k is now the resource exponent in the theorem. Suppose, toward a contradiction, that an unbounded set of input lengths n admits a depth-at-most-d circuit U with at most C(n+1)^k total qubits, whose success probability is at least 1/2+\varepsilon on every input. Choose one such circuit at each member of an increasing sequence of lengths. Write a for its number of ancillary qubits and I for its n input qubits.
Attach a register R of n reference qubits, initially zero, and let \operatorname{COPY} be the layer of disjoint CNOTs from input qubit I_i to reference qubit R_i. Our normalized product starting state is
The enlarged circuit (U\otimes I_R)\operatorname{COPY} has m=2n+a qubits. Splitting the original layers into the two analytic types of Section 2 gives at most t=2d+1 layers, including the copying layer. In particular the layer count is bounded, m\to\infty, and, since k\ge1,
Apply Proposition 6.5 to this circuit and \psi_0, and call the pruned circuit W. Every copying gate is retained for all sufficiently large m. Indeed its reflection projection is
and its probability on \psi_0 is |\langle1|+\rangle|^2|\langle-|0\rangle|^2=1/4\ge m^{-6} eventually. All later gates avoid R, so we can write
for a circuit \widetilde U on the original qubits. Let
Both states are normalized, the trajectory to \Omega is regular, and (6.6) gives \norm{\Phi-\Omega}\le2t m^{-2}.
Let P_B project the designated answer qubit onto |1\rangle, and let Z_R=\prod_{i=1}^n Z_{R_i}. The answer qubit belongs to the original circuit and may be one of its input qubits; in either case P_B acts outside R and commutes with Z_R. Set p_x=\Pr_U(1\mid x). The original coherent output is
The reference states are orthogonal, so
Here p_x\le1/2-\varepsilon on even-parity inputs and p_x\ge1/2+\varepsilon on odd-parity inputs, and there are equally many of each for n\ge1.
The self-adjoint observable Z_RP_B has norm at most one. For any two unit vectors its expectation changes by at most twice their distance, by expanding the difference in its two arguments. Hence
Thus approximating this one coherent state transfers the signed expectation needed below. No success claim for \widetilde U on individual basis inputs is required.
Because \widetilde U acts trivially on R, and a CNOT conjugates Z on its target to the product of Z on control and target,
The one-pair conjugation identity follows directly on a basis vector: the target bit after copying is r_i\mathbin{\oplus}x_i, so its Z eigenvalue is (-1)^{r_i+x_i}. Acting on \psi_0, the last operator in (7.4) gives
Let H_0 be the count associated with the full product state \psi_0. Every input factor of \psi'_0 is orthogonal to its specified |+\rangle state, while all other factors agree with their specified states. Consequently
Moving the unitary and Z_R across the inner product gives
This identity does not require commuting P_B through W or preserving an input register.
Choose fixed exponents
By (7.1), m^h=O(n^{kh})=o(n), so m^h<n eventually. The vector \psi'_0 then belongs to the range of \one_{H_0\ge m^h}. Cauchy–Schwarz and Corollary 6.2, applied to the regular trajectory of W, show that
This tends to zero, contradicting (7.3).
For the fixed d,k,C,\varepsilon, let \mathcal S be the set of input lengths admitting an admissible circuit with success at least 1/2+\varepsilon on every input. The contradiction excludes an unbounded \mathcal S; hence \mathcal S is finite. There is therefore a threshold n_0=n_0(d,k,C,\varepsilon) such that at every n\ge n_0, every circuit meeting the specified depth and total-qubit bounds has an input on which its success probability is strictly less than 1/2+\varepsilon. In particular, for every positive integer N, every n\ge\max\{N,n_0\} has this failure property. This proves Theorem 1.1 with the stated strict failure threshold.
Majority and symmetric-function consequences. Xu and Li’s Theorem 1 and Corollaries 2–3 [22], combined with Theorem 1.1, also exclude strict majority and broader symmetric families in our circuit model. More precisely, let f_n:\{0,1\}^n\to\{0,1\} be symmetric, let f_{n,i} be its value at Hamming weight i, and set \rho(f_n)=\max_{0\le i<n:\,f_{n,i}\ne f_{n,i+1}}\min\{i+1,n-i\}, with zero for constant functions. Its pointwise-error-1/3 approximate degree is the least total degree of a real polynomial p satisfying \lvert p(x)-f_n(x)\rvert\le1/3 for every x\in\{0,1\}^n. Assume either \rho(f_n)\ge n^\delta for all sufficiently large n for some fixed \delta>0, or this approximate degree is \Omega(n^{1/2+\eta}) for some fixed \eta>0. Then no fixed-depth, polynomial-total-qubit family achieves success at least 1/2+1/(\log n)^\gamma on every input at every sufficiently large length, for any fixed \gamma>0. Strict majority \operatorname{MAJ}_n(x)=\mathbf1_{\{|x|>n/2\}} has \rho=\lceil n/2\rceil.
The full formulation and output-model adjustment are recorded in the companion article [18, Section 7.3, Corollary 10 and its proof]. Xu and Li require 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, at a cost of one qubit and one layer. A family with the stated success would, after this adjustment, yield exact clean fanout through the cited reduction. The Hadamard-to-parity argument in Section 1 excludes such fanout using our own Theorem 1.1. Under the same circuit conventions, adjoining unit-cost primitive reversible unbounded threshold gates therefore strictly enlarges the class computed with worst-case success at least 2/3: the reversible gate \lvert x,b\rangle\mapsto\lvert x,b\mathbin\oplus\operatorname{MAJ}_n(x)\rangle computes majority exactly from a zero target.
State-preparation consequences. We justify the bounds stated in Section 1. Keep every register of a preparation when using its unitary and inverse. For felinity \eta>0 on h retained qubits of a depth-d preparation on M total qubits, the constructions in the proofs of Gretta et al. [9, Lemmas 4.9 and 4.1] give target probabilities a\ge1/2 on 0^h and b\ge\eta^2/2 on 1^h, in depth O(d+1) on O(M+h) qubits. The square occurs because the top Fourier coefficient has magnitude at least \eta, so its weight is at least \eta^2.
The exact step is the one-round case of Grier et al. [10, Theorem 7]. For unit vectors g,e, if a unitary V prepares V|0\rangle=(|g,0\rangle+\sqrt3|e,1\rangle)/2, where |0\rangle denotes its entire zero input and the last qubit is a flag, then
Indeed, \langle0|V^\dagger Z_{\rm flag}V|0\rangle=-1/2. A flag initialized to one can be given coefficient c=1/(2\sqrt{a+b})\le1 on zero separately under the two extreme target tests: use a one-qubit reflection sending |1\rangle to c|0\rangle+\sqrt{1-c^2}|1\rangle. Each conditional operation is a product reflection, so the two tests use two sequential Toffoli gates up to local conjugations. The flag-zero component is one half of the normalized union of the extreme branches. The displayed identity prepares that union exactly, with one-branch probability q=b/(a+b)\in[\eta^2/2,1/2], since a+b\le1 and b\le1-a\le a.
Prepare r=\lceil(\log 2)/(-\log(1-q))\rceil=O(\eta^{-2}) independent copies on fresh zeros. Disjoint columnwise reversible ORs into h new targets give probabilities u=(1-q)^r\in[1/4,1/2] on 0^h and v=1-u\in[1/2,3/4] on 1^h. Here (1-q)/2\le(1-q)^r\le1/2 and r\le(\log 2)/q+1. Giving these two branches flag-zero coefficients 1/(2\sqrt{2u}) and 1/(2\sqrt{2v}), respectively, and applying the same exact round yields
with unit branch states \alpha_0,\alpha_1 containing arbitrary garbage. The all-zero reflection is likewise a local conjugate of a Toffoli, and the ORs use Toffoli gates with local X gates. The source-dependent flag coefficients are permitted by nonuniformity. Rosenthal’s exact case [20, Theorem 3.1] converts this balanced state, using its complete preparation and inverse, to the exact parity unitary on arbitrary states of the h+1 data qubits, with every auxiliary qubit restored to zero, and hence to clean F_h by Hadamard conjugation. All copies run in parallel, and only a constant number of preparation and reflection stages are sequential. The resulting depth is O(d+1) and the total-qubit bound is O((M+h)\eta^{-2}+h).
For the Dicke bound, use the block calculation in the proof of the companion’s state-preparation corollary [18, Section 7.1, Corollary 8 and its proof]. Uniformly for n\ge2k and all sufficiently large k, it shows that an input at trace distance at most 1/(80k) from |D_k^n\rangle produces, with \ell=\lfloor k/\log k\rfloor fresh targets and three additional allowed layers, a retained state of felinity greater than 1/(40k). Applying the preceding promotion at arity \ell gives exact parity in fixed depth on O((M+n)k^2) total qubits. For fixed 0<\delta<1 and k\ge n^\delta, eventually \ell\ge\sqrt k, so n\le k^{1/\delta}\le\ell^{2/\delta} and k^2\le\ell^4 make this one fixed polynomial bound in \ell. A felinity violation \eta\ge n^{-A} similarly preserves one fixed polynomial bound at arity n. Both parity arities grow along any unbounded sequence of violations, contradicting the eventual pointwise Theorem 1.1.
References
- [1]Miklós Ajtai. \Sigma^1_1-Formulae on Finite Structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983. doi:10.1016/0168-0072(83)90038-6.
- [2]Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. On the Computational Power of \mathsf{QAC}^{0} with Barely Superlinear Ancillae. arXiv:2410.06499, 2025. Version 4, submitted 21 December 2025; PDF dated 23 December 2025. arXiv:2410.06499, https://arxiv.org/abs/2410.06499v4.
- [3]Anurag Anshu and Tony Metger. Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations. Quantum, 7:999, 2023. doi:10.22331/q-2023-05-11-999.
- [4]Yangjing Dong, Fengning Ou, and Penghui Yao. Linear-Size \mathsf{QAC}^{0} Channels: Learning, Testing and Hardness. arXiv:2510.00593, 2025. Version 2, 8 November 2025. arXiv:2510.00593, https://arxiv.org/abs/2510.00593v2.
- [5]Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. Quantum lower bounds for fanout. Quantum Information and Computation, 6(1):46–57, 2006. doi:10.26421/QIC6.1-3.
- [6]Stephen Fenner, Daniel Grier, Daniel Padé, and Thomas Thierauf. Tight bounds on depth-2 QAC-circuits computing parity. 2025. Version 1, submitted April 8, 2025; PDF dated April 10, 2025. arXiv:2504.06433, https://arxiv.org/abs/2504.06433v1.
- [7]Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13–27, 1984. doi:10.1007/BF01744431.
- [8]Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. Counting, fanout and the complexity of quantum ACC. Quantum Information and Computation, 2(1):35–65, 2002. Preprint: arXiv:quant-ph/0106017v1, 4 June 2001. doi:10.26421/QIC2.1-3, arXiv:quant-ph/0106017.
- [9]Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi. Parity \notin QAC0 \iff QAC0 is Fourier-Concentrated. 2026. Version 2, August 25, 2026. arXiv:2604.02793, https://arxiv.org/abs/2604.02793v2.
- [10]Daniel Grier, Jackson Morris, and Kewen Wu. \mathsf{QAC}^{0} Contains \mathsf{TC}^{0} (with Many Copies of the Input). 2026. Version 1, January 6, 2026. arXiv:2601.03243, https://arxiv.org/abs/2601.03243v1.
- [11]Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 6–20, Association for Computing Machinery, 1986. doi:10.1145/12130.12132.
- [12]Peter Høyer and Robert Špalek. Quantum Fan-out is Powerful. Theory of Computing, 1(5):81–103, 2005. doi:10.4086/toc.2005.v001a005.
- [13]Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright. Improved Lower Bounds for QAC0. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 2199–2209, 2026. Full version arXiv:2512.14643v4, August 25, 2026. doi:10.1145/3798129.3800922, arXiv:2512.14643.
- [14]Shiva Kintali. Parity in Shallow QAC Circuits: Correlation Decay and Exact Lower Bounds. 2026. Preprint dated September 5, 2026. https://shivakintali.github.io/papers/QAC.pdf.
- [15]Tomotaka Kuwahara, Itai Arad, Luigi Amico, and Vlatko Vedral. Local reversibility and entanglement structure of many-body ground states. Quantum Science and Technology, 2(1):015005, 2017. doi:10.1088/2058-9565/aa523d.
- [16]Cristopher Moore. Quantum Circuits: Fanout, Parity, and Counting. arXiv:quant-ph/9903046, 1999. Version 3, 17 March 1999. Also ECCC Report TR99-032. doi:10.48550/arXiv.quant-ph/9903046, arXiv:quant-ph/9903046.
- [17]Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli Spectrum of \mathsf{QAC}^{0}. arXiv:2311.09631, 2024. Version 4, submitted 17 July 2024; PDF dated 19 July 2024. doi:10.48550/arXiv.2311.09631, arXiv:2311.09631.
- [18]OpenAI. Product-projection localization and the \mathrm{QAC}^0 parity lower bound. OpenAI Math Release preprint PDF, 2026. Reading view on this site: Product-projection localization and the QAC0 parity lower bound.
- [19]Daniel Padé, Stephen Fenner, Daniel Grier, and Thomas Thierauf. Depth-2 QAC circuits cannot simulate quantum parity. 2020. Version 1, May 25, 2020. arXiv:2005.12169, https://arxiv.org/abs/2005.12169v1.
- [20]Gregory Rosenthal. Bounds on the \mathsf{QAC}^{0} Complexity of Approximating Parity. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 32:1–32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.32.
- [21]Alexander A. Sherstov. Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Computational Complexity, 18(2):219–247, 2009. https://web.cs.ucla.edu/~sherstov/pdf/incl-excl.pdf.
- [22]Boyan Xu and Lvzhou Li. Fanout Complexity of Symmetric Boolean Functions in \mathsf{QAC}^0. 2026. Version 1, September 4, 2026. arXiv:2609.05153, https://arxiv.org/abs/2609.05153v1.