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 \[F=\prod_g (I-2P_g)\] 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 \[X=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.\] Their tensor products form an orthonormal basis for the inner product \(2^{-m}\mathop{\mathrm{Tr}}(A^\dagger B)\). Thus the unique expansion of \(E\) is \[E=\sum_D c_DD, \qquad c_D=2^{-m}\mathop{\mathrm{Tr}}(D^\dagger E).\] 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{\mathop{\mathrm{supp}}D}>\ell\). This conclusion requires no bound on the norms or coefficients of the original decomposition. Also, \[\abs{c_D} \le 2^{-m}\,2^m\norm{D^\dagger E} =\norm{E},\] because \(\abs{\mathop{\mathrm{Tr}}M}\le 2^m\norm{M}\) for every operator on \(m\) qubits. There are at most \[N_m=\sum_{j=0}^{\ell}\binom mj3^j \le (\ell+1)(3m)^\ell\] 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 \[FDF^\dagger =\sum_{\mathcal L,\mathcal R\subseteq\mathcal T} (-2)^{\abs{\mathcal L}+\abs{\mathcal R}} P_{\mathcal L}DP_{\mathcal R}.\] 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 \[P_{\mathcal L}DP_{\mathcal R}=M\otimes Q, \qquad M=A_{\mathcal L}D_JA_{\mathcal R}, \qquad Q=\prod_{g\in\mathcal L\cup\mathcal R}B_g.\] 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 \[\sum_{\mathcal L,\mathcal R\subseteq\mathcal T} 2^{\abs{\mathcal L}+\abs{\mathcal R}} =9^{\abs{\mathcal T}}\le 9^\ell.\]

Replacing the exterior projections. Let \(H_Q\) count failures of the one-qubit factors of \(Q\), extended by identity outside their sites. Thus \(Q=\mathbf 1_{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 \[k<p_1<L<K, \qquad \frac{L+p_1}{2}<r<p_2<L.\] 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 \[\norm{\mathbf 1_{H_Q>m^L}\xi} \le \norm{\mathbf 1_{H_{\mathcal T}\ge m^L}\xi} \le \exp(-m^{p_2}).\] Here the reference vector is exactly \(F\zeta\), before applying \(M\).

By Lemma 7, 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 \(\mathbf 1_{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 \[\begin{align*} \norm{(Q-f(H_Q))\xi} &\le \exp(-m^{p_1})\norm{\xi} +\bigl(1+\exp(m^r)\bigr) \norm{\mathbf 1_{H_Q>m^L}\xi}\\ &\le \exp(-m^{p_1}) +\bigl(1+\exp(m^r)\bigr)\exp(-m^{p_2}). \end{align*}\] 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 \[\Lambda_m =\exp(m^k)(\ell+1)(27m)^\ell, \qquad \log\Lambda_m=O(m^k\log m).\] It follows that \[\begin{align*} \norm{FE\zeta-E_FF\zeta} &\le \Lambda_m\left[ \exp(-m^{p_1}) +\bigl(1+\exp(m^r)\bigr)\exp(-m^{p_2}) \right]\\ &\le 3\exp\bigl(-\tfrac12m^{p_1}\bigr) =o\bigl(\exp(-m^k)\bigr) \end{align*}\] 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, \[\deg E_F\le\ell+m^r\le m^K, \qquad \norm{E_F}\le\Lambda_m\exp(m^r)\le\exp(m^K),\] 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 \[k=k_0<k_1<\cdots<k_t=K.\] 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 \[\delta_i =U_iE_{i-1}\zeta_{i-1}-E_i\zeta_i, \qquad \norm{\delta_i}=o\bigl(\exp(-m^{k_{i-1}})\bigr).\] 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 \[r_i=U_i r_{i-1}+\delta_i.\] Unitarity implies \[\norm{r_t}\le\sum_{i=1}^t\norm{\delta_i} =o\bigl(\exp(-m^k)\bigr) \le\exp(-m^k)\] eventually. In particular, no later approximating operator acts on an earlier residual. Taking \(E'=E_t\) proves (7). ◻

Proof. Write \(\eta=u-h\) and choose \(\alpha<\lambda<\nu<\beta\). Set \[k=u-\lambda, \qquad q=h-\nu.\] Then \(q>h-\beta>0\), \(k-q=\eta+\nu-\lambda>0\), and \(k<h\) because \(\lambda>\alpha>\eta\). In particular \(k<1\). Choose \[0<e<\min\{\nu-\lambda,1-k\}, \qquad K=k+e.\] The interval available for the remaining filter exponents has width \[w=\left(k-\frac{\eta}{2}\right)-\frac{K+q}{2} =\frac{\nu-\lambda-e}{2}>0.\] With \(a_0=(K+q)/2\), take \[r=a_0+\frac w4, \qquad r'=a_0+\frac w2, \qquad s=a_0+\frac{3w}{4}.\] Thus \[r-a_0=r'-r=s-r'=k-s-\frac\eta2=\frac w4>0.\] 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 10. Fix target exponents \(b<h_*<1\) and \(0<p_*<h_*\). Set \[\delta=\frac{h_*-p_*}{4}, \qquad N=\left\lceil\frac{2(1-h_*)}{\delta}\right\rceil, \qquad \eta=\frac{1-h_*}{N}.\] Here \(N\ge1\) is fixed and \(0<\eta\le\delta/2\). Define \[h_i=1-i\eta, \qquad \alpha_i=\delta+\frac{i\delta}{N} \qquad (0\le i\le N).\] We descend from \(h_0=1\) to \(h_N=h_*\), proving at step \(i\ge1\) that \[\norm{\mathbf 1_{H_A\ge m^{h_i}}\chi} \le\exp\bigl(-m^{h_i-\alpha_i}\bigr).\] 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 \[u=h_{i-1},\qquad h=h_i,\qquad \alpha=\alpha_{i-1},\qquad \beta=\alpha_i.\] Its induction hypothesis is \[\norm{\mathbf 1_{H_A>m^u}\chi} \le\exp\bigl(-m^{u-\alpha}\bigr).\] For \(i>1\) this follows from the preceding, stronger inclusive bound. The parameters obey the hypotheses of Lemma 11: 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 8 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 \[\norm{\mathbf 1_{H_A\le m^v}T\chi}\le\exp(-m^s),\] because \(\norm{\chi}\le1\). Splitting at the previous scale gives \[\begin{align*} \norm{T\chi} &\le \norm{\mathbf 1_{H_A\le m^u}\chi} +\norm{T}\,\norm{\mathbf 1_{H_A>m^u}\chi}\\ &\le 1+\exp\bigl(m^k-m^{u-\alpha}\bigr) \le2. \end{align*}\] This is the first use of a global polynomial norm; it is paid for by \(k<u-\alpha\).

Proposition 9, applied with exponents \(k<K\) to the regular reference trajectory from \(\chi\), gives an operator \(E\) such that \[\norm{VT\chi-EV\chi}\le\exp(-m^k), \qquad \deg E\le m^K, \qquad \norm{E}\le\exp(m^K).\] The endpoint \(V\chi=P_BV\psi\) has exactly zero \(H_B\) count. By Lemma 6, \(\mathbf 1_{H_B>m^K}EV\chi=0\). Therefore the filtered vector has the effective-range bound \[\norm{\mathbf 1_{H_B>m^K}VT\chi}\le\exp(-m^k).\]

Approximating the final projection on the controlled side. Use Lemma 7 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 \[\begin{align*} \norm{(P_B-D)VT\chi} &\le 2\exp(-m^q) +\bigl(1+\exp(m^r)\bigr)\exp(-m^k)\\ &=O\bigl(\exp(-m^q)\bigr). \end{align*}\] 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=\langle \chi,T\chi\rangle\ge0\). Since \(T\) is self-adjoint and \(V\chi=P_BV\psi\), \[a_m=\langle VT\chi,P_BV\psi\rangle.\] Moving the self-adjoint difference \(P_B-D\) to the first argument gives \[\begin{align*} \abs{a_m-\langle VT\chi,DV\psi\rangle} &=\abs{\langle (P_B-D)VT\chi,V\psi\rangle}\\ &\le\norm{(P_B-D)VT\chi}\,\norm{V\psi} =O\bigl(\exp(-m^q)\bigr). \end{align*}\] 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 9 to \(D\) with exponents \(r<r'\) gives an operator \(G\) satisfying \[\norm{V^\dagger DV\psi-G\psi}\le\exp(-m^r), \qquad \deg G\le m^{r'}, \qquad \norm{G}\le\exp(m^{r'}).\] 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 \[\abs{a_m-\langle T\chi,G\psi\rangle} \le O\bigl(\exp(-m^q)\bigr)+2\exp(-m^r) =O\bigl(\exp(-m^q)\bigr).\] The global operator norm of \(T\) introduces no factor here.

Splitting the scalar product by the initial count. Put \(Q=\mathbf 1_{H_A\le m^v}\). Its low-count contribution satisfies \[\abs{\langle QT\chi,QG\psi\rangle} \le\exp(-m^s)\,\exp(m^{r'}).\] For the high-count contribution, first observe that \(m^{v_0}+m^{r'}<m^v\) eventually. The degree-shift property implies \[(I-Q)G\mathbf 1_{H_A\le m^{v_0}}=0.\] Using (8) with threshold exponent \(v_0>b\) and precision exponent \(\theta<v_0\) gives \[\begin{align*} \norm{(I-Q)G\psi} &\le\norm{G}\,\norm{\mathbf 1_{H_A>m^{v_0}}\psi}\\ &\le\exp\bigl(m^{r'}-m^\theta\bigr). \end{align*}\] Orthogonality of \(Q\) and \(I-Q\) now yields \[\begin{align*} \abs{\langle T\chi,G\psi\rangle} &\le\exp\bigl(m^{r'}-m^s\bigr) +2\exp\bigl(m^{r'}-m^\theta\bigr)\\ &=O\bigl(\exp(-m^q)\bigr), \end{align*}\] 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 \[0\le a_m\le C_0\exp(-m^q)\] 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 \[\norm{\mathbf 1_{m^h\le H_A\le m^u}\chi}^2 \le4a_m\le4C_0\exp(-m^q).\] Combining this band with the previous upper tail gives \[\norm{\mathbf 1_{H_A\ge m^h}\chi}^2 \le4C_0\exp(-m^q) +\exp\bigl(-2m^{u-\alpha}\bigr).\] 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 \[\norm{\mathbf 1_{H_A\ge m^h}\chi}\le\exp(-m^{h-\beta})\] 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 9 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, \[h_N-\alpha_N=h_*-2\delta =\frac{h_*+p_*}{2}>p_*.\] The final induction bound implies the desired estimate at \(h_*,p_*\). Since these targets were arbitrary, the lemma follows. ◻

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 \[V=U_t\cdots U_{j+1}.\] 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\), \[\norm{\mathbf 1_{H_A\ge m^h}\psi_j}\le \exp(-m^p) \quad\text{eventually}.\] Lemma 10 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 3 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. ◻

Proof. The original trajectory is regular by assumption and the projected trajectory is regular by Proposition 12. Since \(H_0\psi_0=0\), the input-tail hypothesis of Lemma 10 holds with \(b=0\). Applying that lemma to \(V=W\) proves the claim. ◻

Proof. Put \(\chi_t=P_B\psi_t\) and \(q_B=\norm{P_B\psi_t}^2\). Apply Lemma 10 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 12 and reversal. The projected-and-returned vector is exactly \[\begin{align*} W P_0 W^{\dagger}\chi_t &=\psi_t\,\langle \psi_0,W^{\dagger}P_BW\psi_0\rangle\\ &=q_B\psi_t. \end{align*}\] 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 (10). 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. ◻

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 14 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, (10) gives \[\norm{\mathbf 1_{H_g\ge m^{h_0}}\psi} \le m^6\exp(-m^{p_0}).\] Since \(0\le H_g\le mI\) and \(\norm{\psi}=1\), spectral decomposition therefore gives \[ \langle \psi,H_g\psi\rangle \le m^{h_0}+m^{13}\exp(-2m^{p_0}) \le m^{\epsilon} \quad\text{eventually}. \tag{12}\] Corollary 14 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 \[H_S=\sum_{g\in S}H_g, \qquad \langle \psi,H_S\psi\rangle\le m^{b+\epsilon}.\] 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 \[R=2m^{b+\epsilon},\qquad \beta=b+2\epsilon,\] 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, \[\begin{align*} N_R\le\sum_{j=0}^{\lfloor R\rfloor}\binom mj &\le (\lfloor R\rfloor+1)m^{\lfloor R\rfloor},\\ \log(2N_R)&=O(m^{b+\epsilon}\log m)=o(m^{\beta}). \end{align*}\] Consequently one such outcome \(z\) has probability \[ \rho\ge\frac{1}{2N_R}\ge\exp(-m^{\beta}) \quad\text{eventually}. \tag{13}\] 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 \[\max\{p,\beta\}<p'<h'<h.\] Because \(b+\epsilon<h'<h\), eventually \(m^h-R\ge m^{h'}\). The common basis then gives the spectral inclusion \[\mathbf 1_{H_S\ge m^h}\le\mathbf 1_{H_B\ge m^{h'}}.\] Apply (10) to \(B\) with exponents \((h',p')\), and divide by its probability from (13): \[\begin{align*} \norm{\mathbf 1_{H_S\ge m^h}\psi} &\le\norm{\mathbf 1_{H_B\ge m^{h'}}\psi}\\ &\le\rho^{-1}\exp(-m^{p'})\\ &\le\exp(m^{\beta}-m^{p'}) \le\exp(-m^p) \quad\text{eventually}. \end{align*}\] 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 14 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. ◻

Proof. The empty prefix is regular. Appending a one-qubit layer adds no regularity condition, and Lemma 15 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 \[\norm{(F_g-I)\psi_{j-1}} =2\norm{P_g\psi_{j-1}}<2m^{-3}.\] 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 \[\norm{(U_j-\widetilde U_j)\psi_{j-1}}\le2m^{-2}.\] 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 \[\phi_j-\psi_j =U_j(\phi_{j-1}-\psi_{j-1}) +(U_j-\widetilde U_j)\psi_{j-1}.\] 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 (14). ◻

Proof of Theorem 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 \[\psi_0=|+\rangle_I^{\otimes n} \otimes|0\rangle^{\otimes a} \otimes|0\rangle_R^{\otimes n}, \qquad |+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt2}.\] 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\), \[ m=2n+a\le(C+2)(n+1)^k. \tag{15}\]

Apply Proposition 16 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 \[P_g=|1\rangle\langle1|_{I_i} \otimes|-\rangle\langle-|_{R_i}, \qquad |-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2},\] 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 \[W=(\widetilde U\otimes I_R)\operatorname{COPY}\] for a circuit \(\widetilde U\) on the original qubits. Let \[\Phi=(U\otimes I_R)\operatorname{COPY}\psi_0, \qquad \Omega=W\psi_0.\] Both states are normalized, the trajectory to \(\Omega\) is regular, and (14) 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 \[\Phi=2^{-n/2}\sum_{x\in\{0,1\}^n} U\bigl(|x\rangle_I\otimes|0\rangle^{\otimes a}\bigr) \otimes|x\rangle_R.\] The reference states are orthogonal, so \[ \langle \Phi,Z_RP_B\Phi\rangle =2^{-n}\sum_x(-1)^{|x|}p_x \le\frac12\!\left(\left(\frac12-\varepsilon\right) -\left(\frac12+\varepsilon\right)\right) =-\varepsilon. \tag{16}\] 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 \[ \langle \Omega,Z_RP_B\Omega\rangle \le-\varepsilon+4t m^{-2}. \tag{17}\] 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, \[ W^{\dagger}Z_RW =\operatorname{COPY}^{\dagger}Z_R\operatorname{COPY} =Z_I Z_R, \qquad Z_I=\prod_{i=1}^n Z_{I_i}. \tag{18}\] 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 (18) gives \[\psi'_0=W^{\dagger}Z_RW\psi_0 =|-\rangle_I^{\otimes n} \otimes|0\rangle^{\otimes a} \otimes|0\rangle_R^{\otimes n}.\] 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 \[\norm{\psi'_0}=1,\qquad H_0\psi'_0=n\psi'_0.\] Moving the unitary and \(Z_R\) across the inner product gives \[ \langle \Omega,Z_RP_B\Omega\rangle =\langle \psi'_0,W^{\dagger}P_BW\psi_0\rangle. \tag{19}\] This identity does not require commuting \(P_B\) through \(W\) or preserving an input register.

Choose fixed exponents \[0<p<h<\min\{1,1/k\}.\] By (15), \(m^h=O(n^{kh})=o(n)\), so \(m^h<n\) eventually. The vector \(\psi'_0\) then belongs to the range of \(\mathbf 1_{H_0\ge m^h}\). Cauchy–Schwarz and Corollary 13, applied to the regular trajectory of \(W\), show that \[\left|\langle \Omega,Z_RP_B\Omega\rangle\right| \le\norm{\mathbf 1_{H_0\ge m^h}W^{\dagger}P_BW\psi_0} \le\exp(-m^p).\] This tends to zero, contradicting (17).

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 with the stated strict failure threshold. ◻