CKS nearly-linear condition-number guarantee

For each quantum coordinate construct $H$ from the finite stage/control/inverse/reflection/dilution lists as in [F1]. For gate coordinates its computed bound also includes the QFT/efficient-grid rounding/median overhead over the estimator's finite allowed scales, so the sampler-call estimate multiplies actual ordinary-gate overhead rather than ignoring it. The assigned dyadic times have increments ${\mathrm{\Delta }}_j$, and every interval's reflection-pair and reversible-predicate cost is included in its increment. Set $r_0=s_0=1$ and $v_0=0$, before the first interval. Let $s_j$ be original good-or-unfinished mass, $r_j$ the amplified selected mass, $q_j=r_{j-1}{s}_j\mathrm{/}{s}_{j-1}$ and $v_j$ the amplified circuit cost. With $d_j=2k_j+1$ the ordinary amplification multiplier, $v_j\le d_j(v_{j-1}+{\mathrm{\Delta }}_j)$. Here the $d_j$ sampler/inverse invocations plus $k_j$ reflection pairs fit this allocated budget; none of those costs is free.

To evaluate $H$, put $e_{\ast }=\min (ϵ,\rho )$ and $\mathrm{\Lambda }=1+\log (d\kappa \mathrm{/}{e}_{\ast })$. Since $m=O(1+\log \kappa )$ and $\alpha \le 8\kappa$, the prescribed ${\eta }_I=e_{\ast }\mathrm{/}(4096m\alpha )$ and largest-dyadic $\zeta ={\eta }_S$ give $\log (1\mathrm{/}{\eta }_I),\log (1\mathrm{/}\zeta ),\log (1\mathrm{/}{\eta }_S)=O(\mathrm{\Lambda })$. The exact choice $e_j=\min ({\varphi }_j\mathrm{/}(2d),{\eta }_I\mathrm{/}8)$ likewise has $\log (1\mathrm{/}{e}_j)=O(\mathrm{\Lambda })$. The degree supplier with the stated least bounds gives $D_j=O(d{2}^j\mathrm{\Lambda })$, so $\log D_j=O(\mathrm{\Lambda })$. Across both base lists, there are $Q_0=O(m^2\mathrm{\Lambda })$ QPE simulator sites and total absolute time $T_0=O(\kappa \mathrm{\Lambda })$. Hence the requested simulator tolerance ${\eta }_S\mathrm{/}(2\max (1,Q_0))$ has inverse logarithm $O(\mathrm{\Lambda })$. The value budget can be met at ${ϵ}_{\mathrm{v}\mathrm{a}\mathrm{l}}\le \min \{{\eta }_S\mathrm{/}(2\max (1,T_0)),d{\min }_j({\eta }_I\mathrm{/}(32D_j){)}^2\}$; this sufficient requested bound also has inverse logarithm $O(\mathrm{\Lambda })$. Actual fixed access must meet the requests or the constructor returns INVALID_ACCESS. Phase tolerance $e_j\mathrm{/}100$ and per-slot tolerance ${\eta }_I\mathrm{/}(8N_j)$ have inverse logarithm $O(\mathrm{\Lambda })$ because the explicit stage has $N_j=O(D_j+\mathrm{poly}(m,\mathrm{\Lambda }))$ slots. Smaller certified actual errors do not trigger additional precision requests. Thus an inverse stage has gap ${\delta }_j={\varphi }_j\mathrm{/}d$ and polynomial degree $O(d{2}^j\mathrm{\Lambda })$, and exactly that many signal calls plus one more phase slot by [F6]. The real-extraction, dilution and success-projector circuits are explicit. Gapped phase estimation uses the least admissible dyadic label size $O(2^j)$ and $O(\log (1\mathrm{/}\zeta ))$ coherent repetitions. At each QPE power, the actual QA25 small-time-aware simulation has $O(d\mathrm{\mid }t\mathrm{\mid }+\log (1\mathrm{/}\eta ))$ signal cost, with a separately counted zero-signal branch for sufficiently small time; summing its dyadic evolution times gives $O(d{2}^j)$ and summing the additive precision term gives only additional logarithmic factors. Controlled/inverse calls and sparse block construction carry their actual costs. Thus the query-coordinate interval bound is $H=O(d\mathrm{polylog}(d\kappa \mathrm{/}ϵ,1\mathrm{/}\rho ))$, with an additional $O(\log (d+1))$ factor only if the optional sorted-XOR sparse bridge is chosen. Under the explicit gate specialization in the Statement, the $B$ and sparse-access calls, controlled/inverse forms, QA25 simulator, phase compiler, reflections, clock predicates, dilution rotations and final instrument have the stated uniform gate costs; substituting these bounds into the same interval list gives $H=O(d\mathrm{polylog}(N,d,\kappa ,1\mathrm{/}ϵ,1\mathrm{/}\rho ))$ for the gate coordinate. No bare matrix or arbitrary black-box unitary is assigned free access.

Put $S_i={\sum }_{j\le i}{\mathrm{\Delta }}_j\sqrt{s_{j-1}}$ and $S=S_m$. Expanding the recurrence and substituting $q_j$ telescopes the probability factors. The product loss in [F4], together with $r_{j-1}\ge 1\mathrm{/}(16n)$, gives $v_i\le 6\sqrt{n}\sqrt{r_i\mathrm{/}{s}_i}{S}_i$. Also $s_{j-1}\le p+u_{j-1}$, where $u$ is original unfinished mass. The first dyadic increment is at most $T_{\mathrm{a}\mathrm{v}}$ and later increments equal the preceding deadline, so ${\mathrm{\Delta }}_j\sqrt{u_{j-1}}\le T_{\mathrm{a}\mathrm{v}}$. Thus by [F2], $S\le T_{\max }\sqrt{p}+m{T}_{\mathrm{a}\mathrm{v}}\le 12nH\alpha \sqrt{p}\mathrm{.}$ Consequently the next unamplified sampler's cost $b_i=v_{i-1}+{\mathrm{\Delta }}_i$ satisfies $\frac{b_i}{\sqrt{q_i}}\le \frac{10\sqrt{n}S}{\sqrt{p}}\le 128n^{3\mathrm{/}2}H\alpha \mathrm{.}$ These estimates also hold at the initial interval with $r_0=s_0=1$ and $v_0=0$.

Use confidence $\beta =\rho \mathrm{/}(16n)$ for each of at most $n$ generic estimator invocations and relative error $c=1\mathrm{/}100$. On the intersection of their joint accuracy-and-cost events, [F3] and step 2.1 bound the total quantum estimation cost by $n\cdot 4160(r\mathrm{/}c)\cdot 128n^{3\mathrm{/}2}H\alpha <2^{20}(r\mathrm{/}c)n^{5\mathrm{/}2}H\alpha$. The floors and both scheduler branches are valid by [F2]. The final production cost is at most $72n^{3\mathrm{/}2}H\alpha$, since $r_m\le 1$ in the bound for $v_m$.

The final lower-bound amplifier has $p_0=1\mathrm{/}(18n)$, dyadic trial range $M<4\sqrt{18n}<17\sqrt{n}$, and $R\le 1+\ln (4\mathrm{/}\rho )\mathrm{/}\ln (4\mathrm{/}3)$. Its sampler/reflection budget is therefore at most $2^{13}R{n}^{2}H\alpha$. The median repetition choice in [F3] implies $R\le 32r$ by comparing its defining geometric confidence inequality with $(3\mathrm{/}4{)}^R\le \rho \mathrm{/}4$. The final cost is at most $2^{18}r{n}^{2}H\alpha$. All these costs fit strictly below the specified cap $K=\lceil 2^{30}(r\mathrm{/}c)H\alpha n^4\rceil$. Thus on the good confidence event the resource-timeout branch is never reached, and on every transcript the primitive-cost budget is at most $K$.

The union bound for the estimator events is at most $n\beta \le \rho \mathrm{/}16$, including their joint cost failures. Conditional on the good construction transcript, [F5] fails with probability at most $\rho \mathrm{/}4$. The final zero-work test has additional failure at most $\rho \mathrm{/}4096$ by [F2]. Hence the finite solver succeeds with probability at least $1-5\rho \mathrm{/}16-\rho \mathrm{/}4096\ge 1-\rho$. For a fixed good construction transcript, [F5] gives the same conditional good-state density operator as the actual sampler on every successful terminal amplification branch. Let $g$ be its phase-fixed one-attempt good unit vector, to which [F2] applies. A unit ket on any such branch is $cg$ with $\mathrm{\mid }c\mathrm{\mid }=1$. Applying the actual internal uncompute and projecting work onto zero multiplies the resulting canonical system vector by the same $c$; normalization preserves this unit phase. Thus choosing the representative with this phase removed gives exactly the normalized vector estimate of [F2], and every other unit representative satisfies the stated bound after multiplication by a unit scalar. The external herald is recorded before uncomputing internal flag/bucket work. No relative phase between eigencomponents or coherent stages is changed. All numerical implementation errors used here are the deterministic vector bounds already allocated in [F1], so they are not omitted probabilistic failures.

Since $n=O(1+\log \kappa )$, $\alpha \le 8\kappa$ and $r=O(1+\log ((2+\log (1\mathrm{/}{p}_{\min }))\mathrm{/}\rho ))$, the cap in step 4.1 is $O(d\kappa \mathrm{polylog}(d\kappa \mathrm{/}ϵ,1\mathrm{/}\rho ))$ in the query specialization, and has only the stated polynomial-logarithmic gate overhead. Fixing a constant $\rho <1\mathrm{/}3$ gives the original source target. If a smaller support-gap promise $1\mathrm{/}{\kappa }^{\mathrm{\prime }}$ is supplied, run the same construction with that declared parameter and replace $\kappa$ throughout. Output remains a quantum state. Classical polynomial/phase generation, exact algebraic comparisons, arithmetic bit implementation and compiler construction remain separately charged coordinates; this quantum gate/query result asserts no polylogarithmic total bit-time for them. The retained full Fourier-table and capped alternates preserve their actual costs and are not used to infer the efficient-mode bound.