Unknown-count search halts almost surely when a marked item exists

If $t=0$, then $M=\mathrm{\varnothing }$ by [F2]. Every directly sampled and every quantum-measured candidate is therefore unmarked, and [F1] verifies each before returning. Thus no round returns and the loop does not halt.

Suppose $t>0$ and write $a=t\mathrm{/}N$. If $a\ge 3\mathrm{/}4$, the initial uniform sample in every round is marked with probability $a\ge 3\mathrm{/}4$. Fresh independent samples imply failure through $r$ rounds is at most $(1\mathrm{/}4{)}^r$, which tends to zero.

If $0<a<3\mathrm{/}4$, the schedule $M_{\mathrm{\ell }}=\lceil (3\mathrm{/}2{)}^{\mathrm{\ell }}\rceil$ tends to infinity, so some finite $L$ satisfies $M_L\ge 4\mathrm{/}\sqrt{a}$. From round $L$ onward, conditional on reaching that round and on the direct sample having failed, [F3] gives quantum-search success at least $3\mathrm{/}8$; fresh random labels and registers make this conditional law independent of the direct sample. Thus a round succeeds with probability at least $a+(1-a)(3\mathrm{/}8)\ge 3\mathrm{/}8$. Fresh rounds then give failure through round $r\ge L$ at most $(5\mathrm{/}8{)}^{r-L+1}$.

The verification query returns the actual value $f(x)$, so any returned address is marked by [F1]–[F2]. The bounds in steps 1.2 and 1.3 tend to zero; therefore the algorithm returns a marked element with probability $1$ whenever $t>0$.