BBHT search when the marked count is unknown

Gate model. Use the nonoracle model of One Grover iterate in the standard bit-query model, with exact callable $H$ and $X$ charged per occurrence and an explicitly supplied, costed exact reflection implementation. Each invoked Grover iterate retains its separate standard-bit-query and nonoracle costs.

Input $N=2^n$ and standard bit-query access to $f=1_M$, with no input giving $t=\mathrm{\mid }M\mathrm{\mid }$. Fix $c=3\mathrm{/}2$ and initialize $\mathrm{\ell }=0$. In each round increment $\mathrm{\ell }$ and put $M_{\mathrm{\ell }}=\lceil c^{\mathrm{\ell }}\rceil$. First draw one uniform address $x\in D_n$ and verify it by one standard bit query; if $f(x)=1$, return $x$. Otherwise choose $j$ uniformly from $\{1,\dots ,M_{\mathrm{\ell }}\}$, prepare a fresh address register as $\mathrm{\mid }s⟩=H^{\otimes n}\mathrm{\mid }{0}^n⟩$ and a fresh response qubit as $\mathrm{\mid }-⟩$ using $X$ then $H$, apply the Grover iterate exactly $j$ times, measure the address register, and verify the candidate by a separate standard bit query. Return a verified marked item and otherwise begin the next round. Every random choice and quantum register is fresh in each round. The algorithm has no false positive; when $t=0$ it continues forever and does not produce a finite-time emptiness decision. The gate and state-preparation costs are charged separately from the bit-query count.