Expected cost of unknown-amplitude search

For $0<a<3\mathrm{/}4$, write $s=\sin (2\theta )=2\sqrt{a(1-a)}\ge \sqrt{a}$. Once $M_{\mathrm{\ell }}\ge 8\mathrm{/}s$, [F2] gives amplification-attempt success at least $7\mathrm{/}16$, so the conditional probability of reaching the next round is at most $(1-a)(9\mathrm{/}16)\le 9\mathrm{/}16$. If $M_{\mathrm{\ell }}\ge 8$, then $M_{\mathrm{\ell }+1}\le \frac{3}{2}{M}_{\mathrm{\ell }}+1\le \frac{13}{8}{M}_{\mathrm{\ell }},$ and the survival-weighted cost ratio of later rounds is at most $(9\mathrm{/}16)(13\mathrm{/}8)=117\mathrm{/}128<1$.

Let $q=3\mathrm{/}2$. For every $\mathrm{\ell }\ge 1$, $q^{\mathrm{\ell }}\ge \mathrm{\ell }$: it holds directly for $\mathrm{\ell }=1,2$, and if it holds for $\mathrm{\ell }\ge 2$, then $q^{\mathrm{\ell }+1}\ge (3\mathrm{/}2)\mathrm{\ell }\ge \mathrm{\ell }+1$. Thus $M_{\mathrm{\ell }}\ge \mathrm{\ell }$. With $N=\lceil 8\mathrm{/}s\rceil$, we have $M_N\ge N\ge 8\mathrm{/}s$, so the first threshold index $L$ is at most $N=O(1\mathrm{/}s)$. If $L\ge 2$, then $M_{L-1}<8\mathrm{/}s$ and $M_L=\lceil q^L\rceil \le q{M}_{L-1}+1<12\mathrm{/}s+1\le 13\mathrm{/}s$; the same bound holds when $L=1$. Before that threshold the $M_{\mathrm{\ell }}$ grow geometrically, so their sum is $O(1\mathrm{/}s)$; the $L$ direct preparations and fixed-cost verifications also cost $O(1\mathrm{/}s)$. A round that reaches its amplification attempt makes at most four named calls per iterate, at most one extra preparation call, and at most one verifier call for each of its two samples; including the first direct sample, its total is at most $4M_{\mathrm{\ell }}+4$. After the threshold, [F1], step 1.1, and $M_{\mathrm{\ell }+1}\le (13\mathrm{/}8)M_{\mathrm{\ell }}$ make the survival-weighted worst-case round costs contract by at most $(9\mathrm{/}16)(13\mathrm{/}8)=117\mathrm{/}128<1$. Since $s\ge \sqrt{a}$, the total is $O(a^{-1\mathrm{/}2})$. If $a\ge 3\mathrm{/}4$, each direct sample succeeds with probability at least $3\mathrm{/}4$, and $M_{\mathrm{\ell }+1}\le 2M_{\mathrm{\ell }}$ for $M_{\mathrm{\ell }}\ge 2$; worst-case round costs grow by at most a factor $2$, so survival-weighted costs contract by at most $1\mathrm{/}2$, giving $O(1)=O(a^{-1\mathrm{/}2})$. Each bound applies to every finite prefix, and taking the supremum in [F4] proves the upper bound without an infinite-history expectation.

For a lower bound at small $a$, fix $u=1\mathrm{/}100$ and let $L$ be the first round with $M_L\ge u\mathrm{/}\sqrt{a}$. For every integer $n\ge 1$, induction with [F6] gives $\mathrm{\mid }\sin (n\theta )\mathrm{\mid }\le n\sin \theta$: the base case is equality, and the addition formula bounds the next value by $\mathrm{\mid }\sin (n\theta )\mathrm{\mid }+\mathrm{\mid }\sin \theta \mathrm{\mid }$. Therefore the success probability before round $L$ is at most $a+9a{M}_{\mathrm{\ell }}^2$, accounting for the direct sample and $a(2M_{\mathrm{\ell }}+1{)}^2\le 9a{M}_{\mathrm{\ell }}^2$ for the amplified sample. As proved in step 2.1, $M_{\mathrm{\ell }}\ge \mathrm{\ell }$; therefore $L\le \lceil u\mathrm{/}\sqrt{a}\rceil$. For sufficiently small $a$, $L\ge 2$, $M_{L-1}<u\mathrm{/}\sqrt{a}$, and $M_{\mathrm{\ell }}\le (3\mathrm{/}2{)}^{\mathrm{\ell }}+1$; geometric summation gives [given, F1, F3, F6, step 2.1, algebra] ${\sum }_{\mathrm{\ell }<L}{M}_{\mathrm{\ell }}^2\le \frac{(3\mathrm{/}2{)}^2}{(3\mathrm{/}2{)}^2-1}\frac{u^2}{a}+\frac{2(3\mathrm{/}2)}{(3\mathrm{/}2)-1}\frac{u}{\sqrt{a}}+L=\frac{1.8u^2}{a}+\frac{6u}{\sqrt{a}}+L\mathrm{.}$ Hence the chance of any earlier success is at most $16.2u^2+54u\sqrt{a}+10aL\le 16.2u^2+64u\sqrt{a}+10a$, which tends to $16.2u^2<1\mathrm{/}4$. For all sufficiently small $a$, round $L$ is reached with probability at least $1\mathrm{/}2$.

At round $L$, the direct sample fails with probability at least $1\mathrm{/}2$ for sufficiently small $a$. Conditional on its fresh amplification attempt, $j$ is uniform on $\{1,\dots ,M_L\}$, so [given, F1, F4, step 3.1, algebra] $\mathbb{E}[j]=\frac{1}{M_L}{\sum }_{j=1}^{M_L}j=\frac{M_L+1}{2}\ge \frac{u}{2\sqrt{a}}\mathrm{.}$ The probability of reaching and entering this attempt is at least $1\mathrm{/}4$, so this round alone contributes $\mathrm{\Omega }(a^{-1\mathrm{/}2})$ total access calls. For $a$ bounded away from zero, the first direct sample always makes one $A$-call while $a^{-1\mathrm{/}2}$ is bounded, giving the same aggregate lower bound with a smaller constant.

If $a=0$, every round executes its direct preparation and the process never halts by [F2]. Finite-prefix expected query counts therefore grow without bound with the number of completed rounds, so their supremum in [F4] is $+\mathrm{\infty }$. Gate and classical costs remain separate as required by [F5].