A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 2 · Moore's parity conjecture for $\mathrm{QAC}^0$
Product-projection localization and the QAC0 parity lower bound
expertly designed by an internal OpenAI model · released 2026-09-24
· original PDF
IntroductionParity 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 \(\mathop{\mathrm{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\lvert 0\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 \(\mathop{\mathrm{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 \(\lvert 0\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 1 resolves positively the conjecture \(\mathop{\mathrm{PARITY}}\notin\mathrm{QAC}^0\), with bounded error, polynomially many ancillas, and only a measured output required. History and significanceIn 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\mathop{\mathrm{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]; 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]. 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]. Dong, Ou, and Yao increased this ancilla range to \(\widetilde O(n^{1+2^{-d}})\) [5]. 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]. 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]. 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 argumentUnbounded 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 \[M=\sum_{i\in S}(I-\lvert v_i\rangle\!\langle v_i\rvert)_i;\] 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 \[\left\lVert [M\ge N^t]UAU^\dagger[M=0]\right\rVert\le e^{-N^s} \qquad(0\le s<t)\] 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. 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 (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 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 \(\left\lVert HQP\right\rVert^2=\left\lVert HQPQH\right\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 (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 (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]. 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 \(\mathrm{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] 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. ConsequencesLocalization 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 [10]. In particular, strict majority, \(\operatorname{MAJ}_n(x)=\mathbf 1\{|x|>n/2\}\), where \(|x|\) is the Hamming weight, cannot be computed in this circuit model with worst-case advantage \(1/(\log n)^\gamma\) for any fixed \(\gamma>0\) (3). This separates the model from the corresponding one with unbounded threshold gates. The state-preparation consequences rule out inverse-polynomial measurement probabilities for both a string and its bitwise complement, and sufficiently accurate preparation of uniform superpositions of strings of a fixed Hamming weight \(k\) with \(n^\delta\le k\le n/2\) for fixed \(\delta>0\) (1). For a single measured output, define its expected sign as the probability of zero minus the probability of one. Localization implies that its Fourier coefficients have total squared weight that decays faster than every inverse power of \(n\) on input subsets of size at least \(n^\delta\), for every fixed \(0<\delta\le1\) (2). Finally, majority cannot be computed with average success at least \(1-\tfrac12 n^{-\delta}\) on uniformly random inputs, for any fixed \(\delta>0\) (4). The precise quantifiers and proofs appear after the parity proof in 7. Organization.2 states the localization theorem and fixes the circuit model. 3 proves the polynomial approximation. 4 reduces small-support projections to the preceding depth, and 5 completes the finite scale induction. 6 derives 1, and 7 proves the consequences just described. Product projections and localizationThe 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 \(\left\lVert \cdot\right\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 \[ M=\sum_{i\in S}\bigl(I-\lvert v_i\rangle\!\langle v_i\rvert\bigr)_i, \qquad S\subseteq\{1,\ldots,N\},\quad \left\lVert v_i\right\rVert=1. \tag{1}\] The subscript indicates the qubit on which the summand acts. The reference vector \(v_i\in\mathbb C^2\) can be chosen separately at each qubit. The summands commute, and the spectrum of \(M\) is contained in \(\{0,\ldots,|S|\}\). A product projection is a tensor product of rank-one one-qubit projections on a subset, with identity on the complement. Its support is the selected subset. The empty product is \(I\). These are precisely the projections \([M=0]\). In particular, a product projection need not have rank one on \(\mathcal H_N\). We use a slightly enlarged gate set of product-state reflections, as in [23]. Let \(\mathcal U_d(N)\) be the set of unitaries \[ U=(L_dR_d)\cdots(L_1R_1)L_0, \tag{2}\] 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 1. Indeed, if \(C\) projects onto all controls being \(1\), a Toffoli gate equals \[(I-C)\otimes I+C\otimes X =I-2C\otimes\lvert -\rangle\!\langle -\rvert, \qquad \lvert -\rangle=\frac{\lvert 0\rangle-\lvert 1\rangle}{\sqrt2}.\] Grouping the local gates in each parallel step gives (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) 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 \[ U^\dagger=L_0^\dagger R_1L_1^\dagger\cdots R_dL_d^\dagger \in\mathcal U_d(N). \tag{3}\] 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 \[ \left\lVert [M\ge N^t]\,U[D=0]U^\dagger[M=0]\right\rVert \le \exp(-N^s). \tag{4}\] 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 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 (3). The next two sections supply the approximation and depth-reduction estimates. The proof of 2 is completed in 5. A polynomial approximation with controlled coefficientsWe 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_kx^k\), define its weighted coefficient norm by \[W_N(f)=\sum_k|c_k|N^k.\] This bounds the sum of absolute coefficients in the later operator expansion. The construction uses Chebyshev approximation together with exact roots at the first integer points, a classical approximation-and-interpolation pattern; see Sherstov [24]. Controlling this sum is in the same general spirit as tracking the total local norm of Anshu and Metger [3]. We supply the exact bounds needed here, including intervals whose endpoint exceeds the maximum count \(N\). Lemma 1. 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 \[ \deg p\le N^u, \qquad W_N(p)\le \exp(N^u), \qquad p(0)=1, \tag{5}\] and \[ |p(x)|\le \exp(-N^a) \qquad\text{for every integer }1\le x\le \lceil N^b\rceil. \tag{6}\] The threshold for \(N\) depends only on \(a,b,u\). No restriction \(b\le1\) is imposed. Proof. Put \[r=\lceil N^a\rceil, \qquad m=\lceil N^b\rceil, \qquad \ell=\left\lceil 2\sqrt{mr}\log m\right\rceil.\] Since \(a<b\), we have \(m\ge2r\) once \(N\) is sufficiently large. Define the root polynomial \[F(x)=\prod_{j=1}^{r}\left(1-\frac{x}{j}\right).\] 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 \[T_0(x)=1,\qquad T_1(x)=x,\qquad T_{j+1}(x)=2xT_j(x)-T_{j-1}(x).\] Induction in this recurrence, using the corresponding addition identities, gives \[T_j(\cos\theta)=\cos(j\theta), \qquad T_j\!\left(\frac{h+h^{-1}}2\right) =\frac{h^j+h^{-j}}2\quad(h>0).\] In particular, \(|T_j(x)|\le1\) on \([-1,1]\). Set \[ p(x)=F(x) \frac{T_\ell\!\left((m+r-2x)/(m-r)\right)} {T_\ell\!\left((m+r)/(m-r)\right)}. \tag{7}\] 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 \[\frac{h+h^{-1}}2=\frac{m+r}{m-r}, \qquad \log h=2\int_0^q\frac{dy}{1-y^2}\ge2q.\] Consequently \[T_\ell\!\left(\frac{m+r}{m-r}\right) \ge \frac12\exp\!\left(2\ell\sqrt{r/m}\right) \ge \frac12 m^{4r}.\] 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 [eq:polynomial-construction] lies in \([-1,1]\), and each factor \(|1-x/j|\) is at most \(m\). Thus \[|p(x)|\le 2m^{-3r}\qquad(r\le x\le m).\] 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 [eq:polynomial-decay]. 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 \[\prod_{j=1}^r(1+N/j)\le(1+N)^r.\] For \(z(x)=(m+r-2x)/(m-r)\), we have \[\beta:=W_N(z)=\frac{m+r+2N}{m-r}\le3+2N.\] 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 \[2\beta A^j+A^{j-1}\le A^{j+1}, \qquad A^2-2\beta A-1=2\beta\ge0.\] 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 [eq:polynomial-construction] is at least \(1\), we obtain \[W_N(p)\le(1+N)^r\bigl(11(1+N)\bigr)^\ell, \qquad \deg p\le r+\ell.\] Finally, with \(\gamma=(a+b)/2>a\), the rounded definitions imply \[r=O(N^a),\qquad \ell=O(N^\gamma\log N),\qquad \log W_N(p)=O\!\left(N^\gamma(\log N)^2\right).\] Both \(r+\ell\) and \(\log W_N(p)\) are \(o(N^u)\) because \(u>\gamma\). All constants depend only on the fixed exponents, proving [eq:polynomial-bounds] with the asserted uniform threshold. ◻ Depth reduction for small-support projectionsWe begin the proof of 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 2 (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\mathop{\mathrm{supp}}Q\). Write \(\lvert v_i\rangle\) for the reference vectors of \(M\) and \(\lvert w_i\rangle\) for the projected vectors of \(Q\) on \(I_*\). Set \[p_i=1-|\langle w_i\mid v_i\rangle|^2\qquad(i\in I_*).\] Every vector in the range of \(P\) has the fixed tensor factor \(\bigotimes_{i\in S}\lvert 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 \[\bigotimes_{i\in I_*}\lvert w_i\rangle\otimes \bigotimes_{i\in S\setminus I_*}\lvert v_i\rangle,\] 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\), \[\begin{align*} \left\lVert [M\ge r]QP\right\rVert^2 &\le \prod_{i\in I_*}(1-p_i)\,\Pr(K\ge r)\\ &\le 2^{-r}\prod_{i\in I_*}(1-p_i)(1+p_i) \le 2^{-r}. \end{align*}\] 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\lVert [M\ge N^t]QP\right\rVert\le\exp(-\tfrac12(\log 2)N^t)\), 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 3 (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 \[ \left\lVert [M\ge N^\beta]B[M<N^\alpha]\right\rVert \le \exp(-N^\sigma) \tag{8}\] 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 \[[M<N^\alpha]=\sum_{\substack{F\subseteq S\\ |F|<N^\alpha}} [M^F=0].\] These counts are diagonal in the same product basis, and pointwise in that basis \(M^F\ge M-|F|I\). Choose fixed exponents \[\max\{\alpha,\sigma\}<\sigma'<\beta'<\beta.\] For all sufficiently large \(N\), uniformly over the indicated \(F\), \(N^\beta-|F|\ge N^{\beta'}\). Thus \[\begin{align*} \left\lVert [M\ge N^\beta]B[M^F=0]\right\rVert &\le\left\lVert [M^F\ge N^{\beta'}]B[M^F=0]\right\rVert\\ &\le\exp(-N^{\sigma'}), \end{align*}\] where the last inequality is \(\mathcal 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 (8) by \[\exp\!\left((\lceil N^\alpha\rceil+1)\log(1+N) -N^{\sigma'}\right) \le\exp(-N^\sigma)\] 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 4 (Small-support depth reduction). Fix \(d\ge1\) and assume \(\mathcal 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 \[ \left\lVert [M\ge N^t]UAU^\dagger[M=0]\right\rVert \le\exp(-N^w) \tag{9}\] 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 \[U=VR_1L_0,\qquad V=(L_dR_d)\cdots(L_2R_2)L_1\in\mathcal U_{d-1}(N),\] 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 \(\mathop{\mathrm{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 \[ (1+2)^{2k}=9^k. \tag{10}\] Conjugation by \(V\) turns each such term into a product \(B_1B_2B_3\), with \[B_1=VP_{\mathrm{left}}V^\dagger,\qquad B_2=VA'V^\dagger,\qquad B_3=VP_{\mathrm{right}}V^\dagger.\] Each \(B_j\) is therefore a contraction to which 3 applies. No commutation between these three factors is asserted or needed. Choose fixed exponents \[\max\{w,u\}<w'<\tau_1<\tau_2<t,\] and set \[P=[M=0],\quad H=[M\ge N^t],\quad E_1=[M<N^{\tau_1}],\quad E_2=[M<N^{\tau_2}].\] 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: \[\begin{align*} HB_1B_2B_3P ={}&HB_1B_2(I-E_1)B_3P\\ &+HB_1(I-E_2)B_2E_1B_3P\\ &+HB_1E_2B_2E_1B_3P. \end{align*}\] 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, 3 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 \[\left\lVert HB_1B_2B_3P\right\rVert\le3\exp(-N^{w'}).\] Summing with (10) gives \[\left\lVert HUAU^\dagger P\right\rVert \le3\exp\!\left((\log9)N^u-N^{w'}\right) \le\exp(-N^w)\] 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 inductionThe 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 5 (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 \[0\le s<t<b<2t-s.\] If \(\mathcal B_d(t,b)\) holds, then \(\mathcal B_d(s,t)\) holds. Proof. Choose fixed auxiliary exponents \[s<a<2t-b,\qquad \frac{a+b}{2}<u<w<t.\] 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: \[ 0\le s<a<u<w<t<b,\qquad u>\frac{a+b}{2}. \tag{11}\] Fix \(U\in\mathcal U_d(N)\) and counts \(M,D\), and put \[P=[M=0],\qquad H=[M\ge N^t],\qquad C=UDU^\dagger,\qquad Q=[C=0]=U[D=0]U^\dagger.\] Let \(p(x)=\sum_kc_kx^k\) be the polynomial in 1 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\), 4 applies to every such monomial with the same fixed exponents \(u,w,t\). Since \(p(C)=Up(D)U^\dagger\), its coefficient bound gives \[ \left\lVert Hp(C)P\right\rVert \le e^{-N^w}\sum_k|c_k|N^k \le e^{N^u-N^w}. \tag{12}\] The constant term causes no difficulty: it is a multiple of \(I\), and \(HP=0\). Also, \(\left\lVert C\right\rVert\le N\) gives \[ \left\lVert p(C)\right\rVert\le\sum_k|c_k|N^k\le e^{N^u}. \tag{13}\] 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\): \[\begin{align*} \left\lVert HQP\right\rVert^2 &=\left\lVert HQPQH\right\rVert\\ &\le \left\lVert Hp(C)PQH\right\rVert+\left\lVert H(Q-p(C))PQH\right\rVert\\ &\le \left\lVert Hp(C)P\right\rVert+\left\lVert (Q-p(C))PQ\right\rVert. \tag{14}\end{align*}\] 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 \[ \left\lVert (Q-p(C))PQ\right\rVert \le e^{-N^a}+(1+e^{N^u})\left\lVert [C\ge N^b]PQ\right\rVert. \tag{15}\] The remaining factor is exactly the transition controlled by the inverse circuit. Unitary conjugation gives \[\begin{align*} \left\lVert [C\ge N^b]PQ\right\rVert &=\left\lVert [D\ge N^b]\,U^\dagger[M=0]U[D=0]\right\rVert\\ &\le e^{-N^t}. \tag{16}\end{align*}\] Here \(\mathcal B_d(t,b)\) applies with circuit \(U^\dagger\), mismatch count \(D\), and projected count \(M\). Inverse closure (3) and the universal quantifiers in \(\mathcal B_d(t,b)\) are both used. Combining (12), (14), (15), and (16) yields \[ \left\lVert HQP\right\rVert^2 \le e^{N^u-N^w}+e^{-N^a}+(1+e^{N^u})e^{-N^t}. \tag{17}\] By (11), each term is eventually at most \(\tfrac13e^{-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 2. The case \(d=0\) is 2. 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 \[g=t-s,\qquad \eta=\frac{g^2}{100},\qquad s_0=s,\quad t_0=t,\] and define \[ s_{i+1}=t_i,\qquad t_{i+1}=2t_i-s_i-3\eta. \tag{18}\] Writing \(g_i=t_i-s_i\), we have \[g_i=g-3i\eta,\qquad t_{i+1}-t_i=g_{i+1}.\] Let \(K=\lceil2/g\rceil\). Since \(0<g\le1\), \[3K\eta\le \frac{3(2/g+1)g^2}{100} \le0.09g<\frac g2.\] Thus \(g_i>g/2\) for \(i\le K\), and \[t_K=t+\sum_{i=1}^K g_i>t+Kg/2\ge t+1>1.\] 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. \[\underbrace{\mathcal B_d(s_0,t_0)}_{\text{target}} \ \Longleftarrow\ \mathcal B_d(s_1,t_1) \ \Longleftarrow\ \cdots\ \Longleftarrow\ \underbrace{\mathcal B_d(s_J,t_J)}_{t_J>1:\ \text{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 \[t_i<t_{i+1}=2t_i-s_i-3\eta<2t_i-s_i.\] Thus 5 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 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 parityWe 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 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 2, \(W\in\mathcal U_d(N)\) after padding with identity layers. Let \(O\) project the output qubit onto \(\lvert 0\rangle\), and put \[B=W^\dagger OW,\qquad p_0(x)=\langle x,0\rvert B\lvert x,0\rangle.\] 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 \[\lvert \xi_h\rangle =\bigotimes_{j=1}^n \frac{\lvert 0\rangle+(-1)^{h_j}\lvert 1\rangle}{\sqrt2}, \qquad \bar h=(1-h_1,\ldots,1-h_n).\] Let \(M_h\) be the count on the input qubits whose reference vectors are the factors of \(\xi_h\). The vectors \(\lvert \xi_h,0\rangle\) and \(\lvert \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)\), 2 gives \[ \left|\langle \xi_{\bar h},0\rvert B\lvert \xi_h,0\rangle\right| \le e^{-N^s} \qquad\text{for every }h. \tag{19}\] 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_jx_j\). To see this, note that \(\langle x\mid\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 \[\begin{align*} \mathbb E_h\langle \xi_{\bar h},0\rvert B\lvert \xi_h,0\rangle &=2^{-n}\sum_{x,y}(-1)^{|x|} \mathbb E_h(-1)^{h\cdot(x+y)}\langle x,0\rvert B\lvert y,0\rangle\\ &=2^{-n}\sum_x(-1)^{|x|}p_0(x). \tag{20}\end{align*}\] 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 (20) is at least \(\varepsilon\). But (19) 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 parityThe direct parity proof is complete. Localization next bounds complementary-output probabilities, and a construction of Gretta, Gupta, and Joshi [10] 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 preparationGretta, Gupta, and Joshi [10] 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 \[p_y=\langle y\rvert\rho\lvert y\rangle,\qquad \mathcal F_n(\rho)=2\sum_{y\in\{0,1\}^n}p_y p_{\bar y},\] where \(\bar y\) is the bitwise complement of \(y\). This is the felinity of \(\rho\) [10]. Also write \[\lvert D_k^n\rangle=\binom{n}{k}^{-1/2}\sum_{|y|=k}\lvert y\rangle, \qquad \operatorname{TD}(\rho,\sigma)=\tfrac12\left\lVert \rho-\sigma\right\rVert_1\] for the weight-\(k\) Dicke state and trace distance, respectively. Corollary 1 (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 \[\mathcal F_n(\rho)<n^{-a}.\] Moreover, for every integer \(k\) with \(n^\delta\le k\le n/2\), \[\operatorname{TD}(\rho,\lvert D_k^n\rangle\!\langle D_k^n\rvert)>\frac1{80k}.\] 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\lvert 0^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 \(\left\lVert P_y\psi\right\rVert^2=p_y\). Fix \(0<s<t<1/c\). For sufficiently large \(n\), \(N^t<n\), so the complementary-string projection satisfies \(P_{\bar y}\le[M_y\ge N^t]\). Localization gives \[\sqrt{p_y p_{\bar y}} =\left\lVert P_{\bar y}QP_y\right\rVert\le e^{-N^s} \qquad\text{for every }y.\] The threshold is uniform in \(y\). Cauchy–Schwarz gives \(\sum_y\sqrt{p_y p_{\bar y}}\le1\), and hence \[\mathcal F_n(\rho) \le2e^{-N^s}\sum_y\sqrt{p_y p_{\bar y}} \le2e^{-N^s}<n^{-a}\] 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 \[\ell=\lfloor k/\log k\rfloor,\qquad p=k/n,\qquad \lvert v\rangle=\sqrt{1-p}\lvert 0\rangle+\sqrt p\lvert 1\rangle.\] 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 \[(I-A_j)\otimes I+A_j\otimes X, \qquad A_j=(\lvert v\rangle\!\langle v\rvert)^{\otimes b_j}.\] Each gate equals \(I-2A_j\otimes\lvert -\rangle\!\langle -\rvert\), 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 \(\lvert D_k^n\rangle\). Its all-one probability is \[r_1=|\langle v^{\otimes n}\mid D_k^n\rangle|^2 =\binom nk p^k(1-p)^{n-k}.\] 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 \[(4\sqrt k+1)r_1\ge\Pr(|B-k|<2\sqrt k)\ge\frac34, \qquad r_1\ge\left(\frac3{16}-o(1)\right)k^{-1/2},\] 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=\left\lVert \Pi\lvert D_k^n\rangle\right\rVert^2\), where \(\Pi=\prod_j(I-A_j)\). To bound it, use the unit vector \[\lvert \nu\rangle=(\sqrt{1-p}\lvert 0\rangle-\sqrt p\lvert 1\rangle)^{\otimes n}.\] Since \(b_j\ge n/\ell-1\), \(p\le1/2\), and \(k/\ell\ge\log k\), \[\langle\nu|A_j|\nu\rangle=(1-2p)^{2b_j} \le e^{-4pb_j}\le e^2k^{-4}.\] The commuting projections satisfy \(I-\Pi\le\sum_jA_j\), so \(\left\lVert (I-\Pi)\nu\right\rVert\le e k^{-3/2}\). Moreover, \(|\langle\nu\mid D_k^n\rangle|=\sqrt{r_1}\), because every term of the Dicke state has weight \(k\). Therefore \[\sqrt{r_0}\ge\sqrt{r_1}-e k^{-3/2},\qquad \mathcal F_\ell(\sigma_*)\ge4r_0r_1 \ge\frac{9/64-o(1)}k>\frac1{8k}.\] 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 \[|\mathcal F_\ell(\tau)-\mathcal F_\ell(\tau')| \le4\sum_y|q_y-q'_y| \le8\operatorname{TD}(\tau,\tau').\] Thus \(\operatorname{TD}(\rho,\lvert D_k^n\rangle\!\langle D_k^n\rvert)\le1/(80k)\) would imply \[\mathcal F_\ell(\sigma)>\frac1{8k}-\frac8{80k} =\frac1{40k}.\] 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 1 is measured in the number \(n\) of target qubits. Gretta, Gupta, and Joshi [11] 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 concentrationGretta, Gupta, and Joshi [10] 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 \[\begin{align*} f_C(x)&=\langle x,0^{N-n}\rvert C^\dagger Z_tC\lvert x,0^{N-n}\rangle\in[-1,1],\\ \widehat f_C(S)&=2^{-n}\sum_{x\in\{0,1\}^n} f_C(x)(-1)^{\sum_{i\in S}x_i}. \end{align*}\] Write \(W_{\ge k}[f_C]=\sum_{|S|\ge k}|\widehat f_C(S)|^2\). This is the absolute squared Fourier tail, not a fraction of the total weight \(\mathbb E_x f_C(x)^2\le1\). Corollary 2 (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\le k\le n\) satisfy \[W_{\ge k}[f_C]\le\frac{N}{\gamma_d(k)}.\] In particular, fix \(c\ge1\), \(0<\delta\le1\), and \(B>0\). For all sufficiently large \(n\), uniformly over these circuits with \(N\le n^c\), \[W_{\ge\lceil n^\delta\rceil}[f_C]\le n^{-B}.\] The sufficient threshold depends only on \(d,c,\delta,B\). Proof. Fix a circuit \(C\) and let \(Q=C^\dagger O_0C\), where \(O_0\) projects its output qubit onto \(\lvert 0\rangle\). For \(h\in\{0,1\}^n\), let \(\xi_h\) be the Hadamard product vector from the proof of 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 (20), with \(\bar h\) replaced by \(h\oplus\mathbf 1_S\), gives \[\widehat f_C(S) =2\mathbb E_h\langle \xi_{h\oplus\mathbf 1_S},0\rvert Q\lvert \xi_h,0\rangle \qquad(S\ne\varnothing),\] since \(f_C(x)=2\langle x,0\rvert Q\lvert x,0\rangle-1\). For fixed \(h\), the vectors \(\lvert \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 \[\begin{align*} W_{\ge k}[f_C] &\le4\mathbb E_h\sum_{|S|\ge k} \left|\langle \xi_{h\oplus\mathbf 1_S},0\rvert Q\lvert \xi_h,0\rangle\right|^2 \\ &\le4\sup_h\left\lVert [M_h\ge k]Q[M_h=0]\right\rVert^2. \tag{21}\end{align*}\] For any fixed \(0<\sigma<\tau\), 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 \[b_d(k)=\sup\frac{W_{\ge k}[f_C]}{N},\] where the supremum ranges over all allowed depth-at-most-\(d\) circuits, all designated outputs, and all input and total sizes \(k\le n\le N\). Parseval’s identity gives \(W_{\ge k}[f_C]\le\mathbb E_x f_C(x)^2\le1\), so \(0\le b_d(k)\le1/k\). Fix \(A\ge1\). If \(N\ge k^A\), then \(W_{\ge k}[f_C]/N\le k^{-A}\). For the remaining sizes \(k\le N<k^A\), choose fixed \(0<\sigma<\tau<1/A\). For sufficiently large \(k\), we have \(N^\tau<k\), so (21) gives \[\frac{W_{\ge k}[f_C]}{N}\le\frac{4e^{-2k^\sigma}}{k}.\] 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 \[\gamma_d(k)=\frac1{b_d(k)+e^{-k}}\] satisfies \(\gamma_d(k)/k^B\to\infty\) for every \(B>0\), and the definition of \(b_d\) gives \(W_{\ge k}[f_C]\le N/\gamma_d(k)\). Finally, choose \(B'>(c+B)/\delta\) in this superpolynomial growth property to obtain the asserted cutoff consequence. ◻ Majority and symmetric functionsThe reductions of Xu and Li turn the parity lower bound into a worst-case lower bound for majority and broader symmetric families. For a symmetric \(f_n:\{0,1\}^n\to\{0,1\}\), let \(f_{n,i}\) be its value on inputs of Hamming weight \(i\), and define its transition radius by \[\rho(f_n)=\max_{\substack{0\le i<n\\f_{n,i}\ne f_{n,i+1}}} \min\{i+1,n-i\},\] 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 \[\widetilde{\deg}_{1/3}(f_n)=\Theta\!\left(\sqrt{n\rho(f_n)}\right).\] Thus the approximate-degree hypothesis below also forces a polynomially large transition radius. Corollary 3 (Majority and symmetric functions). Let \((f_n)\) be a symmetric Boolean family satisfying either \(\rho(f_n)\ge 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 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 \(\operatorname{MAJ}_n(x)=\mathbf 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 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 \[\lvert x,b\rangle\longmapsto \lvert x,b\mathbin{\oplus}\mathbf 1\{|x|\ge t\}\rangle, \qquad t\in\{0,\ldots,n\},\] while retaining the same depth, disjoint-support, qubit, ancilla, and output conventions. The enlarged model contains the original one and computes strict majority exactly with one such gate at \(t=\lfloor n/2\rfloor+1\), whereas Corollary 3 excludes even worst-case success \(2/3\) for majority in the original model. High average accuracy for majorityThe preceding obstruction assumes an advantage on every input. The high-average-accuracy consequence of Gretta, Gupta, and Joshi [10] also follows directly from our Fourier-concentration bound: majority retains a polynomial Fourier tail at a polynomially growing cutoff. Corollary 4 (High-average-accuracy majority obstruction). For every fixed \(\delta>0\), no nonuniform family \((C_n)\) in the circuit model of 1, with fixed depth and polynomially many total qubits, satisfies \[2^{-n}\sum_{x\in\{0,1\}^n} f_{C_n}(x)(-1)^{\operatorname{MAJ}_n(x)}\ge1-n^{-\delta}\] 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-\tfrac12 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 \[\|f_{C_n}-g_n\|_2^2 \le 2\bigl(1-\mathbb E_x f_{C_n}(x)g_n(x)\bigr) \le 2n^{-\delta_0},\] 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\), \[W_{\ge k}[g_n]>\varepsilon \quad\text{whenever $k$ is odd and }1\le k\le\frac1{7\varepsilon^2}.\] This is [19]. 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 \[\sqrt{W_{\ge k_n}[f_{C_n}]} \ge \sqrt{W_{\ge k_n}[g_n]}-\|f_{C_n}-g_n\|_2 > (2-\sqrt2)n^{-\delta_0/2}.\] On the other hand, \(k_n\ge\lceil n^{\delta_0}\rceil\) eventually. Applying 2 at the latter cutoff, with \(B=\delta_0+1\), yields \(W_{\ge k_n}[f_{C_n}]\le n^{-(\delta_0+1)}\), a contradiction. ◻ This conclusion does not assert a constant average-case gap or exclude \(1-1/\operatorname{polylog}n\) correlation.
|
| ||||||||
|