QMA Verification and Local Hamiltonian

Regard the nonnegative weights $p_j=\left(\genfrac{}{}{0px}{}{d}{j}\right)x^j(1-x{)}^{d-j}$ as a finite distribution. [F1] gives ${\sum }_j{p}_j=1$. Reindexing the first count in [F2] gives $\mathbb{E}K={\sum }_{j}j{p}_j=dx$. For $d\ge 2$, reindexing the second count gives $\mathbb{E}[K(K-1)]={\sum }_{j}j(j-1)p_j=d(d-1)x^2$; for $d=1$ this expectation is $0=d(d-1)x^2$ directly. Since $K^2=K(K-1)+K$, it follows that $\mathbb{E}(K\mathrm{/}d-x{)}^2=x(1-x)\mathrm{/}d\le 1\mathrm{/}(4d)$.

Since $\mathrm{\mid }\sqrt{u}-\sqrt{v}\mathrm{\mid }\le \sqrt{\mathrm{\mid }u-v\mathrm{\mid }}$ for $u,v\ge 0$, [F3] gives $\mathbb{E}\sqrt{\mathrm{\mid }K\mathrm{/}d-x\mathrm{\mid }}\le \sqrt{\mathbb{E}\mathrm{\mid }K\mathrm{/}d-x\mathrm{\mid }}$ and $\mathbb{E}\mathrm{\mid }K\mathrm{/}d-x\mathrm{\mid }\le \sqrt{\mathbb{E}(K\mathrm{/}d-x{)}^2}$. Therefore $\mathrm{\mid }{B}_d(x)-\sqrt{x}\mathrm{\mid }\le (\mathbb{E}(K\mathrm{/}d-x{)}^2{)}^{1\mathrm{/}4}\le (4d{)}^{-1\mathrm{/}4}\mathrm{.}$ The bound is uniform in $x$, and solving $(4d{)}^{-1\mathrm{/}4}\le \eta$ gives the stated degree choice.

For every vector $v$, $\mathrm{\parallel }Mv\mathrm{\parallel }\ge \mathrm{\parallel }Uv\mathrm{\parallel }-\mathrm{\parallel }(M-U)v\mathrm{\parallel }\ge (1-\epsilon )\mathrm{\parallel }v\mathrm{\parallel }$. Thus $M$ is injective and hence bijective in finite equal dimension. The eigenvalues of $M^{\ast }M$ are ${\sigma }_j^2$, where each singular value obeys $1-\epsilon \le {\sigma }_j\le 1+\epsilon$ by the triangle inequality and [F2].

By [F1], define $(M^{\ast }M{)}^{-1\mathrm{/}2}$ by applying the positive scalar inverse-square-root to its positive eigenvalues. Then $Q^{\ast }Q=I$, so $Q$ is unitary; moreover the singular-value decomposition, obtained by diagonalizing $M^{\ast }M$, gives $\mathrm{\parallel }Q-M\mathrm{\parallel }={\max }_j\mathrm{\mid }1-{\sigma }_j\mathrm{\mid }\le \epsilon$. Consequently $\mathrm{\parallel }Q-U\mathrm{\parallel }\le \mathrm{\parallel }Q-M\mathrm{\parallel }+\mathrm{\parallel }M-U\mathrm{\parallel }\le 2\epsilon$. Finally, $X=M^{\ast }M-I$ has norm at most $2\epsilon +{\epsilon }^2\le 17\mathrm{/}64<1\mathrm{/}2$; the binomial series for $(I+X{)}^{-1\mathrm{/}2}$ converges absolutely in operator norm, and its geometric tail bound gives effective truncations from effective entries of $M$.

Set $K=\mathrm{\parallel }{H}_1\mathrm{\parallel }$. By [F1], the Hermitian compression $H_1{\mathrm{\mid }}_S$ has a unit eigenvector $u\in S$ with eigenvalue ${\lambda }_S$. Since $H_{2}u=0$, its Rayleigh quotient for $H_1+H_2$ is ${\lambda }_S$, so ${\lambda }_{\min }(H_1+H_2)\le {\lambda }_S$.

If $S^{\perp }=\{0\}$, then $S=H$ and $H_2=0$, so the conclusion is equality. Otherwise both $S$ and $S^{\perp }$ are nonzero. For a unit vector $x\in H$, write $x=\alpha u+\beta w$ with $u\in S$, $w\in S^{\perp }$ unit and $\alpha ,\beta \ge 0$, ${\alpha }^2+{\beta }^2=1$; absorb the phases into $u,w$. If either component of $x$ is zero, choose any unit vector in its nonzero subspace for the unused direction. Self-adjointness of $H_2$ and $H_2{\mathrm{\mid }}_S=0$ make its cross terms zero, so $⟨H_{2}x,x⟩\ge J{\beta }^2$. Also $⟨H_{1}u,u⟩\ge {\lambda }_S$, $⟨H_{1}w,w⟩\ge -K$, and $\mathrm{\mid }⟨H_{1}u,w⟩\mathrm{\mid }\le K$.

Expanding the quadratic form and using ${\lambda }_S\ge -K$ gives $⟨(H_1+H_2)x,x⟩\ge {\lambda }_S+(J-2K){\beta }^2-2K\beta \mathrm{.}$ Indeed the $S$-diagonal term is ${\alpha }^2⟨H_{1}u,u⟩\ge {\alpha }^2{\lambda }_S={\lambda }_S-{\beta }^2{\lambda }_S\ge {\lambda }_S-K{\beta }^2$, the $S^{\perp }$ term is at least $-K{\beta }^2$, and $\alpha \le 1$ bounds the cross term below by $-2K\beta$.

The scalar quadratic $(J-2K){\beta }^2-2K\beta$ has minimum $-K^2\mathrm{/}(J-2K)$ by completing the square. Thus every unit Rayleigh quotient is at least ${\lambda }_S-K^2\mathrm{/}(J-2K)$; [F1] identifies the least eigenvalue with the minimum Rayleigh quotient. This proves the lower bound.

Direct determinants give $\det (iH)=i^2\det (H)=1$ because $\det (H)=-1$, and $\det (e^{-i\pi \mathrm{/}8}T)=e^{-i\pi \mathrm{/}4}{e}^{i\pi \mathrm{/}4}=1$. Unitarity is preserved by unit-modulus scalars, so $h,t\in SU(2)$.

Density of the group generated by $h,t$ is [F1]. For any fixed finite word, replacing each normalized generator by its physical gate multiplies the whole word by the product of the corresponding scalar phases, which is a single scalar on the entire one-qubit subcircuit. Such a scalar does not affect any outcome probability when the subcircuit is applied unconditionally. If the word is controlled, this scalar acts only on the active control block and is therefore not irrelevant; the statement explicitly excludes that use without correction.

If $D=1$, output the empty circuit: the scalar $1\times 1$ unitary is immaterial up to the allowed whole-circuit phase. Assume $D\ge 2$. Every Pauli-$X$ requested anywhere in this construction is emitted as the QC14 word $H{T}^{4}H$: the exact matrices in [F9] give $T^4=Z$ and $HZH=X$. First construct exact computational-basis transpositions for row pivoting. For bit strings $x,y$, flip their differing positions in order to form a Gray path $g_0=x,\dots ,g_d=y$. The adjacent swap $g_j\leftrightarrow g_{j+1}$ is an $X$ on their differing bit, controlled on the other $q-1$ fixed bits; for each control required to be $0$, apply the same exact $H{T}^{4}H$ word to that control wire before computing the control conjunction (or before the one-control gate), then undo it after the controlled operation and any conjunction uncomputation. A conjunction of at least two controls is computed into clean bits by a chain of Toffoli gates, the target $X$ is applied under the last conjunction bit, and the chain is reversed; with no controls use the same $H{T}^{4}H$ word, and with one positive control use CNOT. Toffoli is exact over the gate alphabet: for bits $a,b,c$, $4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c)\mathrm{.}$ Compute each parity into a clean bit by CNOTs, apply $T$ for positive terms and $T^{†}$ for negative terms, and uncompute; the resulting phase is $(-1{)}^{abc}$. Conjugating the third bit by $H$ gives Toffoli. The product of swaps along the path except its last edge, followed by the last swap and the reversed prefix, is exactly the transposition of $x,y$. In column $j$, earlier columns have already been made zero below row $j$, so the remaining tail has norm one by unitarity. Approximate its entry magnitudes to error at most $1\mathrm{/}(8D)$ and choose the least row among those with largest approximate magnitude as pivot; the selected exact magnitude is at least $1\mathrm{/}\sqrt{D}-1\mathrm{/}(4D)\ge 1\mathrm{/}(2\sqrt{D})$. Move that row to $j$ by the exact transposition just constructed, which preserves earlier zeros. For each lower entry $b$ and pivot $a$, use the determinant-one Givens block $r^{-1}\left(\begin{array}{cc}\bar{a}& \bar{b}\\ -b& a\end{array}\right)$, $r=(\mathrm{\mid }a{\mathrm{\mid }}^2+\mathrm{\mid }b{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$; direct multiplication sends $(a,b{)}^T$ to $(r,0{)}^T$. The pivot remains bounded below, so every division is conditioned and no exact zero test is needed. Fixed dimension, [F7], and the pivot lower bound give polynomial-time Cauchy names for the Givens factors and a diagonal unitary remainder. If the recorded left multipliers are $Q_1,\dots ,Q_s$, the terminal upper-triangular unitary is $\mathrm{\Delta }=Q_s\cdots Q_{1}U$; its first column has only a unit-modulus first entry, orthogonality forces the rest of the first row to vanish, and induction on the trailing principal block shows $\mathrm{\Delta }$ is diagonal. Hence $U=Q_1^{-1}\cdots Q_s^{-1}\mathrm{\Delta }$, an exact factorization in reverse chronological application order.

Each Givens factor from step 1.1 is an $SU(2)$ block on two basis strings $x,y$, in the two-level sense of [F8]. Flip their differing bit positions in order to form a Gray path $g_0=x,\dots ,g_d=y$. Controlled-$X$ gates on the other fixed bits swap $g_j,g_{j+1}$ for $j<d-1$; for the desired ordered block $V$, the final controlled one-qubit gate uses native block $V$ when the differing target bit of $g_{d-1}$ is $0$, and $XVX$ when that bit is $1$. In the latter case the native target order is $(y,g_{d-1})$, so conjugating by $X$ gives precisely $V$ in the required order $(g_{d-1},y)$. Reversing the swaps therefore gives the exact ordered two-level action. Both possible native blocks remain in $SU(2)$ and have polynomial-time Cauchy names. Every intermediate controlled-$X$ is implemented by the conjunction and target construction of step 1.1, including the exact $H{T}^{4}H$ expansion for its target $X$. With middle block $X$, the same path conjugation is the exact basis transposition used in step 1.1. When $q=1$, the order-corrected native block is itself an unconditional one-qubit $SU(2)$ gate. For $q\ge 2$, reduce each multi-control to one control by computing its $q-1$-bit conjunction into clean bits with the exact Toffoli gates from step 1.1 and then uncomputing. For a one-controlled $SU(2)$ block, choose $R_z(\alpha )R_y(\beta )R_z(\gamma )$. For $R=R_z$ or $R_y$, the chronological sequence “apply $R(\theta \mathrm{/}2)$ to the target, CNOT, apply $R(-\theta \mathrm{/}2)$ to the target, CNOT” has denotation $\mathrm{CNOT}(I\otimes R(-\theta \mathrm{/}2))\mathrm{CNOT}(I\otimes R(\theta \mathrm{/}2))\mathrm{.}$ On control $0$ the two rotations cancel; on control $1$, $XR(-\theta \mathrm{/}2)X=R(\theta \mathrm{/}2)$ by the exact $R_y,R_z$ matrices in [F9], so the active block is $R(\theta )$. This proves the controlled Euler product using only unconditional one-qubit rotations and CNOTs. The closed forms from [F9] give $R_z(\theta +4\pi )=R_z(\theta )$ and $R_y(\theta +4\pi )=R_y(\theta )$; reduce each Euler angle modulo $4\pi$ to a representative in $[0,4\pi )$. For a candidate mesh angle $\theta \in [0,16]$ and $a\in \{y,z\}$, write $R_a(\theta )=e^{A_a(\theta )}$ with $A_a(\theta )=-i\theta {\sigma }_a\mathrm{/}2$. Since $\mathrm{\parallel }{A}_a(\theta )\mathrm{/}9\mathrm{\parallel }\le 8\mathrm{/}9<1$, the interval routine [F7] evaluates $e^{A_a(\theta )\mathrm{/}9}$ in its stated domain; multiplying nine such matrices evaluates $R_a(\theta )$, with guard precision chosen so each three-rotation product and target has certified Frobenius error at most $\eta \mathrm{/}(100C_D)$. Put $M=\lceil 1600C_D\mathrm{/}\eta \rceil$ and use the rational mesh $\{16j\mathrm{/}M:0\le j\le M\}$ in each coordinate. Since $4\pi <16$, each reduced Euler angle is within $16\mathrm{/}M\le \eta \mathrm{/}(100C_D)$ of a mesh point. The exact rotation formula gives $\mathrm{\parallel }{R}_a(u)-R_a(v)\mathrm{\parallel }\le \mathrm{\mid }u-v\mathrm{\mid }\mathrm{/}2$, so the product at one such mesh triple is within $\eta \mathrm{/}(8C_D)$ of the target. For each candidate, compute a certified Frobenius-distance upper bound from the entry intervals; its square-root input is scaled by $1\mathrm{/}9$, since the squared distance between two $2\times 2$ unitaries is at most $8$, and then rescaled by $3$. Select the first mesh product whose upper bound is at most $\eta \mathrm{/}(4C_D)$; the guaranteed nearby mesh point passes because its true Frobenius distance is at most $\sqrt{2}\eta \mathrm{/}(8C_D)$ and the interval error is at most $\eta \mathrm{/}(100C_D)$. Every selected product therefore has operator error at most $\eta \mathrm{/}(4C_D)$. Here $C_D\ge 1$ is a fixed upper bound for the total number of rotation factors requiring approximation, including the recursive diagonal construction described below; for example, for $q\ge 1$ take $C_D=\max \{1,3D(D-1)+(D-1)(2q-1)\}$. The search uses $O((C_D\mathrm{/}\eta {)}^3)$ candidates and only rational interval comparisons, not an exact-real branch test.

Factor the diagonal remainder as $\mathrm{\Delta }=d_0\mathrm{diag}(1,(d_z\mathrm{/}{d}_0{)}_{z\mathrm{\ne }0})$. Since $\mathrm{\mid }{d}_0\mathrm{\mid }=1$, every ratio ${\tilde{d}}_z=d_z\mathrm{/}{d}_0$ is a unit scalar with a polynomial-time Cauchy name by [F7]: the denominator has the uniform lower bound one. For each $z\mathrm{\ne }0$, choose a bit position where $z$ is one, compute the condition that all other bits match $z$, and apply $\mathrm{diag}(1,{\tilde{d}}_z)$ to the chosen bit controlled by that condition; this phases $\mathrm{\mid }z⟩$ and leaves its partner with chosen bit zero unchanged. If $q=1$ the condition is empty and the phase is unconditional. The common factor $d_0$ is the single global scalar for the complete diagonal remainder. Approximate each ${\tilde{d}}_z$ by scanning an $M$-point rational angle grid, with $M\ge 16\pi D\mathrm{/}\eta$, and accept a grid point whose certified chordal distance is at most $4\pi \mathrm{/}M$; a nearest grid point is within $\pi \mathrm{/}M$, so a valid one is found after $O(M)$ evaluations using [F7]. Write its phase as $e^{i\theta }$. Implement a phase on a pattern of $k$ original data bits by induction on $k$. For $k=1$, use $\mathrm{diag}(1,e^{i\theta })=e^{i\theta \mathrm{/}2}{R}_z(\theta )$ on that data bit (conjugated by exact $X$ gates for pattern zero), retaining its scalar as a whole-circuit scalar. For $k\ge 2$, choose an original data target and compute the conjunction of the other $k-1$ original data controls with the exact Boolean circuits of step 1.1 (one control needs no workspace). Apply controlled $R_z(\theta )$ to the original target by the two target rotations and two CNOTs of step 2.1, and uncompute the conjunction immediately. For a signed pattern, conjugate the zero-valued controls by exact $X$ gates before computing the conjunction and undo them immediately after uncomputing; conjugate a zero-valued target by $X$ around the controlled rotation. Thus all data bits are restored to their original pattern coordinates before recursion. Apply, recursively, phase $e^{i\theta \mathrm{/}2}$ on the matching pattern of the $k-1$ original control data bits. On a nonmatching control pattern both ideal operations are identity; on a matching one their product is $e^{i\theta \mathrm{/}2}{R}_z(\theta )=\mathrm{diag}(1,e^{i\theta })$ on the target, or its $X$-conjugate when the target pattern bit is zero. This proves the required pattern phase, up to just the base case's whole-circuit scalar. Crucially, every rotation is on an original data bit: no computed flag receives a rotation or an approximating word. Each conjunction block is uncomputed before recursion changes any of its data controls. Its clean bits therefore return exactly to zero even when arbitrary one-qubit words replace the target rotations, because those words and their controlling CNOTs never alter the conjunction inputs or flags. The same argument applies to the Givens blocks in step 2.1. The phase recursion uses $b_1=1$, $b_k=b_{k-1}+2=2k-1$ one-qubit factors and $O(k^2)$ exact Boolean gates, reusing $O(k)$ clean bits. Thus the diagonal remainder is implemented by unconditional rotations, CNOTs and the fixed conjunction circuits above, with total phase error at most $\eta \mathrm{/}4$, since there are fewer than $D$ entries and $M\ge 16\pi D\mathrm{/}\eta$.

All one-qubit rotations in step 2.1 and step 3.1 are unconditional factors. Compile their determinant-one matrices using [F2]–[F3]; any scalar phases from normalized Clifford–T letters then multiply the full circuit by a single global scalar, never a control block. Since $D$ is fixed, take $M_D=C_D$, which also bounds the recursive phase factors. The accepted mesh approximations in step 2.1 contribute at most $\eta \mathrm{/}4$ total error, and step 3.1 contributes at most $\eta \mathrm{/}4$ for diagonal phases. For each factor request Solovay–Kitaev error $\min \{\eta \mathrm{/}(2M_D),{\eta }_0\}$; this lies in the compiler's stated domain and is no larger than $\eta \mathrm{/}(2M_D)$, so synthesis contributes at most $\eta \mathrm{/}2$. After factoring out whole-circuit scalars, the telescoping identity bounds total operator error by the sum, at most $\eta$. The Givens pivots stay at least $1\mathrm{/}(2\sqrt{D})$; the Euler mesh has $O((C_D\mathrm{/}\eta {)}^3)$ candidates and each diagonal phase grid has $O(D\mathrm{/}\eta )$ candidates, with fixed $C_D,D$. Parse the binary numerator and denominator of $\eta$ in $O(\mathrm{\ell }(\eta ))$ time. The mesh sizes, rational comparisons, and compiler tolerances are computed by integer arithmetic on numbers of $O(\mathrm{\ell }(\eta )+\log (1\mathrm{/}\eta )+1)$ bits. The certified arithmetic precision is $O(\log (1\mathrm{/}\eta )+1)$; [F1] charges each target query polynomial time in $b$ plus this precision, and [F3] also charges the encoding length of each derived tolerance. Thus all arithmetic and compiler bit time, including reading $\eta$ and printing the full gate list, is polynomial in $b+\mathrm{\ell }(\eta )+1\mathrm{/}\eta$. The number of rotation factors is fixed, and [F3] bounds each compiled word length polynomially in $\log (1\mathrm{/}\eta )+1$, giving the claimed gate-count bound independent of the tolerance encoding length. In the coordinates of [F10], the output gate count and wire count are polynomial, as is the deterministic full-list generator time; the ancilla count is constant because $q$ is fixed and the decompositions reuse $O(q)$ work bits. Each compiled word acts only on original data wires; the exact Boolean compute/control/uncompute blocks return every work bit exactly to zero, so the resulting data operator $V$ is well-defined with exact clean-ancilla return, not merely small workspace leakage.

Request each of the at most $D^2$ entries of each $H_j$ to absolute complex error at most $\tau \mathrm{/}(2mD)$. Replace each entry by its rational approximation and symmetrize the matrix by $(A+A^{\ast })\mathrm{/}2$; this preserves rationality and Hermiticity, and does not increase the Frobenius error beyond the entrywise bound. The Frobenius norm of a $D\times D$ error matrix is at most $D$ times its largest entry error, so [F3] gives $\mathrm{\parallel }{H}_j-{\tilde{H}}_j\mathrm{\parallel }\le \tau \mathrm{/}(2m)$. The precision request has $O(\log (mD\mathrm{/}\tau ))$ bits beyond the input description and is computed in polynomial time by [F1]. The term list and common embedding are those of [F4].

Identity embedding preserves operator norm, so $\mathrm{\parallel }H-\tilde{H}\mathrm{\parallel }\le {\sum }_j\mathrm{\parallel }{H}_j-{\tilde{H}}_j\mathrm{\parallel }\le \tau \mathrm{/}2\le \tau$. For each unit $v$, $\mathrm{\mid }⟨Hv,v⟩-⟨\tilde{H}v,v⟩\mathrm{\mid }\le \tau$; taking minima over the same unit sphere in both directions and using [F2] yields $\mathrm{\mid }{\lambda }_{\min }(H)-{\lambda }_{\min }(\tilde{H})\mathrm{\mid }\le \tau$. If ${\lambda }_{\min }(H)\le a$, then ${\lambda }_{\min }(\tilde{H})\le a+\tau$; if ${\lambda }_{\min }(H)\ge b$, then ${\lambda }_{\min }(\tilde{H})\ge b-\tau$. Their new gap is $\mathrm{\Delta }-2\tau \ge 3\mathrm{\Delta }\mathrm{/}4$.

The effective encoding and fixed arity in [F5] give a fixed-dimensional matrix with computable entries. By Hermiticity and the norm bound, every eigenvalue $\lambda$ of $K\mathrm{/}B$ lies in $[-1,1]$; hence the eigenvalues of $E$ lie in $[0,1]$. The finite-dimensional spectral theorem therefore gives positive square roots $S=\sqrt{E}$ and $R=\sqrt{I-E}$. The block matrix $U_0=U=\left(\begin{array}{cc}S& R\\ R& -S\end{array}\right)$ is unitary: $S,R$ are commuting functions of $E$, $S^2+R^2=I$, and the off-diagonal products cancel. For input flag $0$, its flag-$0$ block is $S$. Follow the dilation by $X$ on the flag, so the accepted branch is labeled outcome $1$; define the marked-accept dilation $U_{acc}$ to be this full unitary. Its accepted effect is $S^{\ast }S=E$.

Choose degree $d\ge 1\mathrm{/}(4{\delta }^4)$ and use [F1] to form Bernstein polynomials $S_d=B_d(E)$ and $R_d=B_d(I-E)$. Functional calculus on the eigenbasis gives $\mathrm{\parallel }{S}_d-S\mathrm{\parallel },\mathrm{\parallel }{R}_d-R\mathrm{\parallel }\le \delta$. Thus the block matrix $M=\left(\begin{array}{cc}{S}_d& R_d\\ R_d& -S_d\end{array}\right)$ satisfies $\mathrm{\parallel }M-U\mathrm{\parallel }\le 2\delta$ by the triangle inequality for its two block columns. Taking $\delta \le 1\mathrm{/}16$ and applying [F2] gives an exactly unitary polar correction $Q$ with $\mathrm{\parallel }Q-U\mathrm{\parallel }\le 4\delta$.

Polynomial-time Cauchy names for the ideal dilation require a precision-polynomial construction. For $A=E$ or $I-E$, put $X_0=I$, $X_{j+1}=(X_j+A{X}_j^{-1})\mathrm{/}2$. On each eigenvalue $a\in [0,1]$, the scalar iterate satisfies $x_j\ge \max \{\sqrt{a},2^{-j}\}$ and $0\le x_{j+1}-\sqrt{a}=(x_j-\sqrt{a}{)}^2\mathrm{/}(2x_j)\le (x_j-\sqrt{a})\mathrm{/}2$. Thus $\mathrm{\parallel }{X}_j-\sqrt{A}\mathrm{\parallel }\le 2^{-j}$ and $\mathrm{\parallel }{X}_j^{-1}\mathrm{\parallel }\le 2^j$, even when $a=0$. For error $2^{-p}$, take $m=p+3$, approximate $A$ once to operator error $h=2^{-10(m+1{)}^2}$, and round every iterate to dyadic entries with total operator rounding error at most $h$. If the iterate error is $e_j\le 2^{-j-1}$, the inverse identity bounds inverse error by $2^{2j+1}{e}_j$ and approximate inverse norm by $2^{j+1}$. Therefore $e_{j+1}\le 2^{2j+2}{e}_j+2^{j+1}h+h$. With $e_0=0$, this gives $e_j\le 2^{2(m+1{)}^2}h$ for $j\le m$, smaller than $2^{-m}$ and $2^{-j-1}$, so the bounds hold throughout. In fixed local dimension $D$, rational inversion by adjugate and determinant uses a fixed number of arithmetic operations; the approximate iterates have least singular value at least $2^{-j-1}$ and determinant modulus at least $2^{-D(j+1)}$. Rounding after each iteration keeps all stored entries at $O_D(m^2)$ bits. The $m$ iterations and the input approximation consequently cost polynomial time in the encoding length and $p$. They supply polynomial-time Cauchy names for $S,R$ and $U_{acc}$.

Select $\delta \le \eta \mathrm{/}16$, and compile $Q$ to a circuit with a phase representative $V^{\mathrm{\prime }}$ satisfying $\mathrm{\parallel }{V}^{\mathrm{\prime }}-Q\mathrm{\parallel }\le \eta \mathrm{/}4$ using [F3]. The accepted flag outcome effect of the physical circuit is $\tilde{E}=V_{00}^{\ast }{V}_{00}$, where $V_{00}$ is the flag-$0$ compression before the final $X$ relabeling; the global scalar relating the physical unitary to $V^{\mathrm{\prime }}$ cancels in this effect. Compressions are contractions, so $\mathrm{\parallel }\tilde{E}-E\mathrm{\parallel }\le \mathrm{\parallel }{V}^{\mathrm{\prime }\ast }{P}_0{V}^{\mathrm{\prime }}-U^{\ast }{P}_{0}U\mathrm{\parallel }\le 2\mathrm{\parallel }{V}^{\mathrm{\prime }}-U\mathrm{\parallel }\le 2(\eta \mathrm{/}4+4\delta )\le \eta \mathrm{.}$ The fixed dimension is at most $2^{k+1}$; Bernstein degree is $O({\eta }^{-4})$, and its coefficients and matrix products have polynomially many bits at the needed precision. The polar series and fixed-width synthesis also have polynomial generator cost by [F2]–[F3]. Step 2.2 supplies polynomial-time Cauchy entries for $U_{acc}=(X_{flag}\otimes I)U_0$, so the same fixed-dimensional synthesis applies to the block diagonal matrix $I\oplus U_{acc}$ after adding one selector bit. Thus no controlled operation is assumed without synthesis.

Let $r(n)=3+2\lceil {\log }_2\max \{2,W(n)\}\rceil$ be a fixed record width, with three type bits and two address fields, and let $B(n)=L(n)r(n)$ be the padded program bit length. For each bit position $1\le i\le B(n)$, define a fixed polynomial-time machine $M^{\mathrm{\prime }}(x,i)$ that runs $M(x)$ and returns the $i$th bit of its padded record string. Apply [F1] to $M^{\mathrm{\prime }}$. The uniform generator can specialize the index input $i$ to each constant $1,\dots ,B(n)$, enumerate every Boolean gate record using [F4]'s logarithmic-space size/type/predecessor queries, and concatenate the $B(n)$ circuits. The resulting multi-output Boolean circuit computes the entire gate program; it has polynomial size and is generated in polynomial time from $1^n$.

Allocate one clean value wire per Boolean node and traverse the circuit's topological order. A constant zero leaves its target zero; a constant one applies $X=H{T}^{4}H$; a NOT node writes $1\oplus a$ by $X$ followed by CNOT; an AND node writes $ab$ into a zero target with Toffoli; and an OR node writes $a\oplus b\oplus ab=a\vee b$ with two CNOTs and one Toffoli. If both input ports name the same source, one CNOT copies that source for either AND or OR. Copy each designated circuit output into its separate program bit by CNOTs, then reverse all node computations to return their value wires to zero. The exact Toffoli circuit is supplied by [F5]'s construction.