CKS stopping-time and success-mass instantiation

In the finite Hermitian eigenbasis write $b={\sum }_k{c}_k{v}_k$, $A{v}_k={\lambda }_k{v}_k$, where $1\mathrm{/}\kappa \le \mathrm{\mid }{\lambda }_k\mathrm{\mid }\le 1$. Thus $1\le x\le \kappa$. The supplied-permutation sparse block circuit uses the certified entry bound $h=1$ for the decoded Hermitian matrix $\tilde{A}$. Hermiticity lets the row enumeration on the swapped system register serve as the column enumeration, and the supplied reverse-location map makes each matching slot unique. Since $\mathrm{\mid }{\tilde{A}}_{ij}\mathrm{\mid }\le 1$, its value flag matrix is unitary and has flag-zero amplitude ${\tilde{A}}_{ij}$ on the zero input. The row and column neighbor states have coefficient $1\mathrm{/}\sqrt{d}$ on each listed slot, so their unique matching pair contributes ${\tilde{A}}_{ij}\mathrm{/}d$ to the all-zero flag compression; the support-coverage promise ensures every nonzero decoded entry is listed, any listed slot whose decoded value is zero contributes zero, and padded sentinels have no overlap. Hence the actual PUE block is exactly $\tilde{A}\mathrm{/}d$, within ${ϵ}_{\mathrm{v}\mathrm{a}\mathrm{l}}\mathrm{/}d$ of the ideal $A\mathrm{/}d$. On the ideal block $A\mathrm{/}d$, eigenvalue $\lambda$ gives normalized eigenvalue $\lambda \mathrm{/}d$. The odd stage polynomial with gap ${\delta }_j={\varphi }_j\mathrm{/}d$ approximates the target multiplier $\mathrm{sgn}(\lambda ){\varphi }_j\mathrm{/}(2\mathrm{\mid }\lambda \mathrm{\mid })={\varphi }_j\mathrm{/}(2\lambda )$ within its declared scalar error for $\mathrm{\mid }\lambda \mathrm{\mid }\ge {\varphi }_j$. Diluting by ${\varphi }_m\mathrm{/}{\varphi }_j$ gives the common ideal multiplier $1\mathrm{/}(\alpha \lambda )$, where $\alpha =2\mathrm{/}{\varphi }_m$. By [F2], the actual QSVT block on $\tilde{A}\mathrm{/}d$ differs from the ideal transform of $A\mathrm{/}d$ by at most $4D_j\sqrt{{ϵ}_{\mathrm{B}\mathrm{E},j}}$ plus the declared polynomial/phase errors; these are included in the per-stage compression budget ${\eta }_I$. The real-extraction success projector includes its control and all zero workspace. The finite SVD therefore gives the ideal supported target $Xb\mathrm{/}\alpha$, with actual stage compression within ${\eta }_I$. Also $4\kappa \le \alpha <8\kappa$ (the endpoint inequalities may be replaced by non-strict upper bounds).

In the ideal comparison circuit, QPE at dyadic label size $M\ge 64\pi \mathrm{/}\varphi$ estimates the eigenphase modulo $2\pi$. The exact Fourier kernel obeys $\mathrm{Pr}[d_{\mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}}(y\mathrm{/}M,\lambda \mathrm{/}(2\pi ))\ge a]\le 1\mathrm{/}[2(Ma-1)]$: indeed each label probability is at most $1\mathrm{/}[4M^2{d}_{\mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}}^2]$, since $\mathrm{\mid }\sin (\pi u)\mathrm{\mid }\ge 2\mathrm{\mid }u\mathrm{\mid }$ for $\mathrm{\mid }u\mathrm{\mid }\le 1\mathrm{/}2$, and summing each of the two reciprocal-square tails uses ${\sum }_{s\ge R}{s}^{-2}\le 1\mathrm{/}(R-1)$. Taking $a=\varphi \mathrm{/}(4\pi )$ gives failure at most $1\mathrm{/}30$. Circular phase error below $\varphi \mathrm{/}2$ places the unwrapped phase magnitude on the correct side of $3\varphi \mathrm{/}2$ for each of the two promises. Since $\mathrm{\mid }\lambda \mathrm{\mid }\le 1<\pi$, this unwrapping is unambiguous on the good event. For $r_0$ independent coherent QPE copies on this eigenvector, the squared amplitudes of label strings factor. If $B$ counts incorrect comparisons, $\mathbb{E}[4^B]\le (11\mathrm{/}10{)}^{r_0}$, hence $\mathrm{Pr}[B\ge r_0\mathrm{/}2]\le (11\mathrm{/}20{)}^{r_0}$. The declared odd $r_0\ge 8\ln (1\mathrm{/}{\zeta }^2)+8$ makes this at most ${\zeta }^2$. A reversible majority stores this decision without measurement, so the wrong-branch amplitude is at most $\zeta$.

For a simulator call at signed time $t$, differentiating $e^{-iA(t-s)}{e}^{-i\tilde{A}s}$ and integrating from $0$ to $t$ gives $\mathrm{\parallel }{e}^{\pm iAt}-e^{\pm i\tilde{A}t}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\mid }t\mathrm{\mid }\mathrm{\parallel }A-\tilde{A}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\mid }t\mathrm{\mid }{ϵ}_{\mathrm{v}\mathrm{a}\mathrm{l}}\mathrm{.}$ Thus call site $q$ differs from the ideal $e^{\pm iA{t}_q}$ by at most ${\xi }_q+\mathrm{\mid }{t}_q\mathrm{\mid }{ϵ}_{\mathrm{v}\mathrm{a}\mathrm{l}}$. Taking controlled direct sums or adjoints preserves that norm bound. By [F6] and the budget in [F7], each complete actual base list is within ${\eta }_S$ of its ideal-$A$ comparison on clean inputs, including arbitrary references; actual simulator work remains coherent.

For fixed supported $\lambda$, let $j_{\ast }$ be the first stage with $2{\varphi }_{j_{\ast }}\le \mathrm{\mid }\lambda \mathrm{\mid }$. It exists by the chosen $m$, and $2^{j_{\ast }}\le 4\mathrm{/}\mathrm{\mid }\lambda \mathrm{\mid }$. Before stage $j_{\ast }-1$, the low-eigenphase promise holds, so stopping there has probability at most ${\zeta }^2$ per stage. At $j_{\ast }$ the high-eigenphase promise holds, so failing to stop has probability at most ${\zeta }^2$. The intermediate stage is unconstrained and either branch is allowed. Apart from a total probability at most $(m+1){\zeta }^2\le 2m{\zeta }^2$, all histories stop at $j_{\ast }-1$ or $j_{\ast }$, and satisfy $\mathrm{\mid }\lambda \mathrm{\mid }\ge {\varphi }_j$ at their inverse stage. This is the full adjacent-stage ambiguity analysis; it makes no unique-estimate assumption.

Correct histories stop by time $4H\mathrm{/}\mathrm{\mid }\lambda \mathrm{\mid }$. Orthogonality of eigenvectors and histories gives ideal RMS square at most $16H^2{\sum }_k\mathrm{\mid }{c}_k{\mathrm{\mid }}^2\mathrm{/}{\lambda }_k^2$, with wrong-history mass contributing at most $16H^2{\kappa }^2(2m{\zeta }^2)$. By step 1.3, the actual controlled simulations have total clean-input isometry difference at most ${\eta }_S$ on the base list, with a reference register; the diagonal stopping-time-squared observable on the orthogonal clock histories has norm at most $16H^2{\kappa }^2$. For unit vectors at distance at most ${\eta }_S$, the difference of its expectations is at most $2{\eta }_S$ times this norm, by expanding the two quadratic forms and applying the triangle inequality. Consequently $T_{\mathrm{a}\mathrm{v}}^2\le 16H^2{x}^2+16H^2{\kappa }^2(2m{\zeta }^2+2{\eta }_S)\le 17H^2{x}^2,$ using [F1]'s budgets and $x\ge 1$. Thus $T_{\mathrm{a}\mathrm{v}}\le 5Hx$, while $T_{\max }=H{2}^m\le 4H\kappa \le 2H\alpha$. The inverse stage occurs only after stopping, so its unsuccessful workspace does not affect any later stopping probability.

In the ideal-$A$ comparison circuit let the joint eigenvalue/history projection select first stops with $\mathrm{\mid }\lambda \mathrm{\mid }\ge {\varphi }_j$. Its complement, including a final no-stop history, has mass at most $2m{\zeta }^2$ by step 2.1. On valid histories, compare the actual successful inverse compression with the common scalar $X\mathrm{/}\alpha$; summing the stage errors conservatively gives $m{\eta }_I$. On the complement, the actual projected output has norm at most $\sqrt{2m}\zeta$ by contractivity, while the comparison vector produced by $A^{\mathrm{\prime }}Xb\mathrm{/}\alpha$ has norm at most $(\kappa \mathrm{/}\alpha )\sqrt{2m}\zeta \le \sqrt{2m}\zeta \mathrm{/}2$. By step 1.3, simulation hybrids contribute at most ${\eta }_S$ for $A$ and at most $(\kappa \mathrm{/}\alpha ){\eta }_S$ for the comparison circuit $A^{\mathrm{\prime }}$. Therefore, with all auxiliary inputs clean and internal $F=0$, $\mathrm{\parallel }{\mathrm{\Pi }}_{F}AB\mathrm{\mid }0⟩-A^{\mathrm{\prime }}(\mathrm{\mid }0{⟩}_{F,\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}}Xb\mathrm{/}\alpha )\mathrm{\parallel }\le m{\eta }_I+3\sqrt{m}\zeta +2{\eta }_S\le \frac{\epsilon }{128\alpha }\mathrm{.}$ This compares projected output vectors and uses no full-space simulator bound.

Put $D=\epsilon \mathrm{/}(128\alpha )$. Step 3.2 gives $\mathrm{\mid }\sqrt{p}-x\mathrm{/}\alpha \mathrm{\mid }\le D$, hence $p\ge x^2\mathrm{/}(4{\alpha }^2)$ and $T_{\mathrm{a}\mathrm{v}}\mathrm{/}\sqrt{p}\le 10H\alpha$. Applying the actual unitary $(A^{\mathrm{\prime }}{)}^{†}$ preserves the vector error. For nonzero vectors $v,w$, the triangle inequality gives $\mathrm{\parallel }v\mathrm{/}\mathrm{\parallel }v\mathrm{\parallel }-w\mathrm{/}\mathrm{\parallel }w\mathrm{\parallel }\mathrm{\parallel }\le 2\mathrm{\parallel }v-w\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }w\mathrm{\parallel }$; apply it with $\mathrm{\parallel }w\mathrm{\parallel }=x\mathrm{/}\alpha \ge 1\mathrm{/}\alpha$ to obtain conditional output error at most $\epsilon \mathrm{/}64$. The external herald is copied or measured before this uncompute; the comparison internal flag is clean and any actual residual is included in the vector error. The preparation-work register $W_B$ was clean initially and is untouched by $A^{\mathrm{\prime }}$ and $(A^{\mathrm{\prime }}{)}^{†}$. Finally project all work, including $W_B$, onto zero as specified in [F1]. Before that test, the pure joint conditional vector is within $\epsilon \mathrm{/}64$ of target times clean work, so the test fails with probability at most ${\epsilon }^2\mathrm{/}4096\le \rho \mathrm{/}4096$. Its successful normalized system vector is within $\epsilon \mathrm{/}32\le ϵ$ of the desired vector by the same normalization inequality.

Let $s_i$ be the original good-or-unfinished mass at interval $i$, defined by the algorithm's projector for $1\le i\le m$: the orthogonal union of branches with $F=1$, $T=0$, and first-stop clock word $C_1=\cdots =C_{j-1}=0,C_j=1$ for some $j\le i$ (later clock bits remain zero), and branches with $F=0$, $T=0$, and $C_1=\cdots =C_i=0$. Previously stopped bad branches and the terminal bad branch are excluded; since $T$ is set after stage $m$, the unfinished term is empty at $i=m$. It is at least $p$ because all future good mass lies in the unfinished branch; the clean $W_B$ factor does not change this mass. If the prior amplified selected mass is $r_{i-1}$, then the next sampler has $q_i=r_{i-1}{s}_i\mathrm{/}{s}_{i-1}$. At the pre-stage index set $r_0=s_0=1$: preparation has run, every clock bit and $F,T$ is zero, and the entire state is unfinished. In particular $q_1=s_1\ge p$ and $r_0\ge 1\mathrm{/}(16n)$, establishing the induction base. Suppose inductively $r_{i-1}\ge 1\mathrm{/}(16n)$; then $q_i\ge p\mathrm{/}(16n)\ge 1\mathrm{/}(64n{\alpha }^2)>p_{\min }$. On the estimator-good event, ${\widehat{q}}_i>1\mathrm{/}(9n)$ gives the unamplified $r_i=q_i>(100\mathrm{/}101)\mathrm{/}(9n)>1\mathrm{/}(16n)$, with loss one. If $0<{\widehat{q}}_i\le 1\mathrm{/}(9n)$, [F5] gives the same floor and the claimed multiplicative loss. A zero estimate or exhausted bounded crossing does not occur on this event. The induction proves every promised estimator floor and the final amplifier's lower bound $1\mathrm{/}(18n)$. Fresh production after every classical construction transcript and ordinary amplification preserve the exact conditional good state of the actual sampler.

Step 3.1 and step 4.1 give precisely the source-scale RMS and success quantities: $T_{\mathrm{a}\mathrm{v}}^2=\tilde{O}(d^2{\sum }_k\mathrm{\mid }{c}_k{\mathrm{\mid }}^2\mathrm{/}{\lambda }_k^2)$, $\sqrt{p}=\tilde{\mathrm{\Theta }}({\alpha }^{-1}({\sum }_k\mathrm{\mid }{c}_k{\mathrm{\mid }}^2\mathrm{/}{\lambda }_k^2{)}^{1\mathrm{/}2})$ and $T_{\mathrm{a}\mathrm{v}}\mathrm{/}\sqrt{p}=\tilde{O}(d\kappa )$ when the actual quantum interval budget is $H=d\mathrm{poly}(\log (d\kappa \mathrm{/}ϵ),\log (1\mathrm{/}\rho ))$ (with the declared sparse/control/implementation overhead). Here the concrete chosen common normalization is $\alpha =O(\kappa )$; all supplied nonstandard costs remain in $H$. The original Fourier/table alternate mode retains its distinct charged construction and SELECT costs; its cost is not substituted for this efficient-mode estimate.