Relative probability estimation with a charged finite cap

The dyadic sequence $M_j=4\cdot 2^j$ has unbounded squares, so its positive rational threshold in [F1] is eventually reached. Since $p_{\min }\le 1$, its least cap index has $L\ge 3$, and minimality gives $M_{L-1}^2{p}_{\min }<1024$, hence $M_L<64\mathrm{/}\sqrt{p_{\min }}$. The geometric sequence $(4\mathrm{/}5{)}^r$ tends to zero, so the least positive odd $r$ in [F1] exists. The final scale is a finite dyadic ceiling of a rational number and satisfies $16M_J\mathrm{/}c\le N<32M_J\mathrm{/}c$. Every raw call has dyadic size at least four. Thus all schedule choices are executable by finite rational arithmetic.

For each raw output $z\in [0,1]$, the rounding instruction finds $t=\lfloor M^{2}z\rfloor$ by finite binary search with [F7], including equality and the endpoint $z=1$. Its returned rational $b=t\mathrm{/}{M}^2$ satisfies $0\le z-b<M^{-2}$, with equality $b=z$ when $M^{2}z$ is integral, and returns exactly zero when $y=0$. Binary search uses $O(\log M)$ comparisons. Its rational output has $O(\log M)$ numerator and denominator bits. Every comparison terminates by [F7], and all its internal refinement and output operations remain charged under [F8]. In efficient-grid mode [F9] supplies the same range, zero branch and $M^{-2}$ error directly, with its separately proved finite polynomial resource bound; no exact-comparison refinement is used in that mode. There are at most $L+1$ detection medians and one final median, each with finitely many calls, so the entire procedure terminates.

By [F6], one rounded call at size $M$ uses $M-1$ controlled $A$ calls, $M-1$ controlled $A^{\ast }$ calls and one ordinary $A$ preparation, for $2M-1$ sampler-and-inverse invocations. A median costs at most $2rM$ such invocations, with separately charged $r(M-1)$ occurrences of each controlled reflection and control phase. Since ${\sum }_{j=0}^L{M}_j<2M_L$, detection costs less than $4r{M}_L$. A final median, if invoked, has size $N<32M_L\mathrm{/}c$ and costs less than $64r{M}_L\mathrm{/}c$. Thus every execution, including unsuccessful estimates reaching the cap, has $C<4r{M}_L+64r{M}_L\mathrm{/}c<65r{M}_L\mathrm{/}c<4160r\mathrm{/}(c\sqrt{p_{\min }})$, because $4c<1$.

By [F5], $8\mathrm{/}{\pi }^2>8\mathrm{/}(22\mathrm{/}7{)}^2>4\mathrm{/}5$, $2\pi <8$, and ${\pi }^2<16$. Therefore [F4] and step 2.1 imply that each rounded output lies in the interval $I_M=[p-8\sqrt{p}\mathrm{/}M-17\mathrm{/}{M}^2,p+8\sqrt{p}\mathrm{/}M+17\mathrm{/}{M}^2]$ with failure probability at most $1\mathrm{/}5$. Let $B_i$ indicate failure of copy $i$ in a median, and put $B={\sum }_{i=1}^r{B}_i$. Independence gives $\mathbb{E}{4}^B={\prod }_i\mathbb{E}{4}^{B_i}\le (8\mathrm{/}5{)}^r$. Since ${\mathbf{1}}_{\{B\ge r\mathrm{/}2\}}\le 4^B\mathrm{/}{4}^{r\mathrm{/}2}$, taking expectations gives $\mathrm{Pr}\{B\ge r\mathrm{/}2\}\le (4\mathrm{/}5{)}^r\le \delta$. If fewer than half of the samples miss $I_M$, their middle order statistic lies in $I_M$: an order statistic outside that interval would put at least $(r+1)\mathrm{/}2$ samples on the same outside side. Consequently each median misses $I_M$ with probability at most $\delta$. This also holds conditional on every earlier classical transcript, because the chosen size is then fixed and this median uses independent fresh workspaces.

Call a median good when it belongs to $I_M$, and put $x=M\sqrt{p}$. At a good detection stage, $x^2-8x-17\le M^{2}b\le x^2+8x+17$. A good stage that detects therefore has $x>11$, since for $0\le x\le 11$ its upper bound is at most $121+88+17=226<256$. A good stage with $x\ge 32$ certainly detects, since $x^2-8x-17$ is increasing there and is at least $751>256$. For a positive promised $p$, $M_L\sqrt{p}\ge 32$, so a good cap stage detects.

If detection occurs at a good stage $J$, then the fresh final scale has $x^{\mathrm{\prime }}=N\sqrt{p}\ge 16M_J\sqrt{p}\mathrm{/}c>176\mathrm{/}c$. When its final median is good, $\mathrm{\mid }\widehat{p}-p\mathrm{\mid }\mathrm{/}p\le 8\mathrm{/}{x}^{\mathrm{\prime }}+17\mathrm{/}(x^{\mathrm{\prime }}{)}^2<c\mathrm{/}22+17c^2\mathrm{/}{176}^2<c$, using $0<c<1\mathrm{/}4$. At most $L+2$ medians are invoked, and each has conditional failure probability at most $\delta$ by step 3.1. The union bound therefore makes the probability of any invoked bad median at most $(L+2)\delta \le \beta$. On the complementary event, a positive input detects by the cap and satisfies the relative estimate just proved. At $p=0$, [F4] gives raw output zero with certainty; step 2.1 and the algorithm's zero-label branch make every rounded value and median zero. No positive threshold is met, so the algorithm returns zero exactly.

Suppose $p>0$. Let $j_{\ast }$ be the first index with $M_{j_{\ast }}\sqrt{p}\ge 32$. It exists by the promise and satisfies $j_{\ast }\le L$, $j_{\ast }>0$, and $M_{j_{\ast }}<64\mathrm{/}\sqrt{p}$. For analysis, preassign independent hypothetical median outcomes to all detection stages, and reveal them only if reached; this finite product of independent experiments has exactly the procedure's law. To reach stage $j_{\ast }+t\le L$, every one of the $t$ preceding stages beginning at $j_{\ast }$ must have a bad median, since a good one at these scales would detect by step 4.1. Thus $\mathrm{Pr}\{\text{reach }{j}_{\ast }+t\}\le {\delta }^t$. If $S$ is the sum of sizes of invoked detection stages, finite summation and $\delta \le 1\mathrm{/}16$ give $\mathbb{E}S<2M_{j_{\ast }}+M_{j_{\ast }}{\sum }_{t\ge 1}(2\delta {)}^t\le (2+1\mathrm{/}7)M_{j_{\ast }}<3M_{j_{\ast }}$. The infinite geometric sum here is only an upper bound on a finite expected cost.

Detection costs at most $2rS$. If detection occurs, $M_J\le S$ and the final median costs less than $64r{M}_J\mathrm{/}c$; otherwise that cost is zero. Hence $\mathbb{E}C\le (2+64\mathrm{/}c)r\mathbb{E}S<200r{M}_{j_{\ast }}\mathrm{/}c<12800r\mathrm{/}(c\sqrt{p})$. If $p=0$, there is no final median and $C<4r{M}_L<256r\mathrm{/}\sqrt{p_{\min }}$. Both cases imply $\mathbb{E}C=O(r\mathrm{/}(c\sqrt{p_{\ast }}))$. On the probability-$1-\beta$ event of step 5.1, a positive input stops by $j_{\ast }$, so the deterministic calculation of step 2.2, with $M_{j_{\ast }}$ replacing $M_L$, gives $C<65r{M}_{j_{\ast }}\mathrm{/}c<4160r\mathrm{/}(c\sqrt{p})$. For $p=0$ the deterministic cap already gives the claimed $p_{\ast }$ bound. This establishes the simultaneous probability assertion.

Minimal dyadic threshold choice gives $L=O(1+\log (1\mathrm{/}{p}_{\min }))$. Since $r$ is the least positive odd integer with $(4\mathrm{/}5{)}^r\le \delta$, it is at most two above the real threshold $\log (1\mathrm{/}\delta )\mathrm{/}\log (5\mathrm{/}4)$, apart from the harmless minimum value one. Also $1\mathrm{/}\delta =\max \{16,(L+2)\mathrm{/}\beta \}$, so $r=O(1+\log ((L+2)\mathrm{/}\beta ))$. Substituting into step 6.1 gives the stated expected bound. Rounding's precision and finite comparison count are those of step 2.1, and [F8] keeps their actual bit costs, along with the ordinary quantum resources in [F6], separate from this query bound. Finally, by [F1] every measured estimation workspace is discarded and the output is classical. Conditional on any resulting transcript, a subsequent fresh execution initializes its own declared input and applies its own prescribed sampler. Its output state, and therefore its conditional good state when that event has positive probability, is precisely that prescribed for the fresh sampler; the measured construction registers are not inputs to it.