Unknown-amplitude search has no false positives and halts almost surely

Assume $0<a<1$, and let $0<\theta <\pi \mathrm{/}2$ satisfy ${\sin }^2\theta =a$. The identity ${\sin }^{2}x=(1-\cos (2x))\mathrm{/}2$ gives $p_M=\frac{1}{M}{\sum }_{j=1}^M{\sin }^2((2j+1)\theta )=\frac{1}{2}-\frac{1}{2M}{\sum }_{j=1}^M\cos ((4j+2)\theta )\mathrm{.}$ The cosine sum is the real part of $e^{i6\theta }{\sum }_{r=0}^{M-1}{e}^{i4r\theta }$. By [F6], this finite geometric sum has modulus $\frac{\mathrm{\mid }1-e^{i4M\theta }\mathrm{\mid }}{\mathrm{\mid }1-e^{i4\theta }\mathrm{\mid }}=\frac{\mathrm{\mid }\sin (2M\theta )\mathrm{\mid }}{\mathrm{\mid }\sin (2\theta )\mathrm{\mid }}\le \frac{1}{\mathrm{\mid }\sin (2\theta )\mathrm{\mid }}\mathrm{.}$ Taking real parts therefore gives $p_M\ge \frac{1}{2}-\frac{1}{2M\mathrm{\mid }\sin (2\theta )\mathrm{\mid }}\mathrm{.}$

If $0<a<3\mathrm{/}4$, then $\sin (2\theta )=2\sqrt{a(1-a)}\ge \sqrt{a}$. Since $M_{\mathrm{\ell }}\to \mathrm{\infty }$, some finite round has $M_{\mathrm{\ell }}\ge 2\mathrm{/}\sqrt{a}$, after which [F1]–[F2] give a conditional per-round success probability at least $p_{M_{\mathrm{\ell }}}\ge 1\mathrm{/}4$. If $a\ge 3\mathrm{/}4$, the direct sample in each round succeeds with probability at least $3\mathrm{/}4$. Thus in either case there is a finite round after which every fresh round has conditional success probability bounded below by a fixed positive constant.

Registers and randomness are fresh each round, so after $r$ rounds beyond the finite threshold in step 2.1, the probability of still not returning is at most $(3\mathrm{/}4{)}^r$ in the first case and $(1\mathrm{/}4{)}^r$ in the second. Both tend to zero. Since every output is returned only after the good instrument outcome (and verification when required), no bad output is returned; on every positive-probability good branch [F4] supplies its conditional state.

If $a=0$, every fresh preparation has zero projection onto $\mathrm{ran}{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, so each good outcome has probability zero by [F3]. The procedure therefore never returns and runs forever, as specified in [F1].