Variable-time amplitude-amplification theorem

Group the original operation-count execution into dyadic deadlines, assigning each stopped branch the first deadline after its original stopping count. All counts are positive integers in the declared coordinate. Treat an original stage as indivisible: group all stages ending by each deadline and use twice that deadline as its padded cumulative budget. The interval then covers every grouped whole-stage call. This changes maximum and RMS counts by at most four and leaves stopped branches untouched. There are at most $n$ intervals with increments ${\mathrm{\Delta }}_j$ summing to at most $4T_{\max }$. Their input/selected-reflection and preparation/control budgets are included, rather than treated as free additional operations. We retain this factor in the numerical constants below.

Let $s_j$ be the original probability of being already good or still unfinished at deadline $j$, with $s_{-1}=1$. It decreases, is at least $p>0$, and has final value $p$. Construct $B_j$ by running the preceding amplified list and continuing the original algorithm only on unfinished branches. Inductively its selected component is proportional to the original selected component, with probability $q_j=r_{j-1}{s}_j\mathrm{/}{s}_{j-1}$; initially $r_{-1}=1$. Amplify by the chosen odd multiplier. By [F2] this preserves the conditional selected state, and at the last deadline that state is the exact original conditional good state.

Let $v_j$ be the production-list cost and $d_j$ its amplification multiplier. Then $v_j\le d_j(v_{j-1}+{\mathrm{\Delta }}_j)$, with $v_{-1}=0$. The supplied-regime certificate or [F3] gives $d_j\le \sqrt{r_j\mathrm{/}{q}_j}(1-2\mathrm{/}(5n){)}^{-1\mathrm{/}2}$ on amplified intervals, with no loss on unamplified intervals. Expand the recurrence. For each summand, ${\prod }_{\mathrm{\ell }=j}^h\sqrt{r_{\mathrm{\ell }}\mathrm{/}{q}_{\mathrm{\ell }}}=\sqrt{\frac{r_h{s}_{j-1}}{r_{j-1}p}}\mathrm{.}$ The total loss is at most $\sqrt{5\mathrm{/}3}$, and $r_{j-1}\ge 1\mathrm{/}(16n)$ (with initial value one), so $v_h\le 6\sqrt{n{r}_h\mathrm{/}p}{\sum }_j{\mathrm{\Delta }}_j\sqrt{s_{j-1}}\mathrm{.}$ The same bound holds for every prefix with its corresponding $r_i,s_i$.

In the uniform regime use [F4] with $c=1\mathrm{/}100$, floor $q_{\min }=p_0\mathrm{/}(64n)$ and failure $\beta =\rho \mathrm{/}(16n)$ at each of at most $n$ intervals. All estimation workspaces are fresh construction data, discarded before production. On the estimator-good event, a returned $\widehat{q}>1\mathrm{/}(9n)$ uses $d=1$ and actual $r=q>(100\mathrm{/}101)\mathrm{/}(9n)>1\mathrm{/}(16n)$, with loss one. Otherwise choose the least odd $d$ with $d^2\widehat{q}\ge 1\mathrm{/}(9n)$; search only through $k\le \lceil 1\mathrm{/}\sqrt{q_{\min }}\rceil$ and return failure if no crossing is found. [F3] gives the same surviving floor and loss bound in this case. Inductively $q_j\ge p\mathrm{/}(16n)\ge p_0\mathrm{/}(16n)>q_{\min }$, so every estimator promise is met on this joint event; a zero estimate or exhausted search is then impossible. The actual upper bound $r\le 1\mathrm{/}n$ is neither claimed nor used.

Write $u_{j-1}$ for original unfinished mass at the preceding deadline. Since $s_{j-1}\le p+u_{j-1}$ and ${\mathrm{\Delta }}_j\sqrt{u_{j-1}}\le 2T_{\mathrm{a}\mathrm{v}}$ by the dyadic stopping convention (also at the first interval, because stopping counts are at least one), $S:={\sum }_j{\mathrm{\Delta }}_j\sqrt{s_{j-1}}\le 4(T_{\max }\sqrt{p}+n{T}_{\mathrm{a}\mathrm{v}})\mathrm{.}$ In the supplied-data regime apply [F5] at lower bound $\mathrm{\ell }\ge r_h\mathrm{/}2$ and constant failure $1\mathrm{/}2$. Its $O(r_h^{-1\mathrm{/}2})$ factor cancels $\sqrt{r_h}$ in step 3.1, proving production cost $O(T_{\max }\sqrt{n}+(T_{\mathrm{a}\mathrm{v}}\mathrm{/}\sqrt{p})n^{3\mathrm{/}2})$. Substitute $n=O(\ln L_T)$ and add the actual $C_{\mathrm{b}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}}$, including its probability-acquisition oracle calls. Independent repetitions give the stated confidence. No construction-cost bound follows solely from existence of true-probability-selected multipliers.

The prefix version of step 3.1 and $r_{j-1}\ge 1\mathrm{/}(16n)$ give the next sampler cost $b_i$ the bound $b_i\mathrm{/}\sqrt{q_i}\le 10\sqrt{n}S\mathrm{/}\sqrt{p}$. Use step 4.1 and [F4] to charge every estimation call. Summing at most $n$ stages gives at most $2^{18}(r\mathrm{/}c)(n^{3\mathrm{/}2}{T}_{\max }+n^{5\mathrm{/}2}{T}_{\mathrm{a}\mathrm{v}}\mathrm{/}\sqrt{p})$ with slack for dyadic padding. Final production has $v_h\le 6\sqrt{n}S\mathrm{/}\sqrt{p}$. Apply [F5] with floor $1\mathrm{/}(18n)$ and failure $\rho \mathrm{/}4$: its range is $M<17\sqrt{n}$, and its trial count $R$ is at most $32r$. Thus its complete additional cost fits within $2^{20}(r\mathrm{/}c)n^{5\mathrm{/}2}(T_{\max }+T_{\mathrm{a}\mathrm{v}}\mathrm{/}\sqrt{p})$, again with slack for the already charged reflection/interval overhead. This proves the stated joint-event bound and includes the quantum cost of acquiring probability data.

The computable integer $P_0$ satisfies $P_0\ge 1\mathrm{/}\sqrt{p_0}$ and $P_0<2\mathrm{/}\sqrt{p_0}$. Since $T_{\mathrm{a}\mathrm{v}}\le T_{\max }$ and $p\ge p_0$, the joint-event cost in step 5.1 is below $K$. Count all construction, production, inverse/control/reflection stage calls and final amplification against $K$, stopping before an excess. The resource timeout therefore never occurs on the joint estimator-good event. Its complement has probability at most $n\beta \le \rho \mathrm{/}16$ by [F4] and the union bound. Conditional on the good construction event, final capped amplification fails with probability at most $\rho \mathrm{/}4$. Total failure is at most $5\rho \mathrm{/}16<\rho$. Every heralded good branch has the same conditional original state by step 2.1, even after averaging the classical construction transcript. The procedure is finite on every branch by its explicit caps.