Classical bit cost of randomized known-count search

Since $t\ge 1$, $\sqrt{N\mathrm{/}t}\le \sqrt{N}$ by [F5], hence $K\le \lceil \sqrt{N}\rceil \le 2^{\lceil n\mathrm{/}2\rceil }=\mathrm{h}\mathrm{i}$. The predicate $P(m):t{m}^2\ge N$ is false at $\mathrm{l}\mathrm{o}=0$, true at $\mathrm{h}\mathrm{i}$, and monotone by [F6]. At each step with width $d=\mathrm{h}\mathrm{i}-\mathrm{l}\mathrm{o}>1$, the upper midpoint $\mathrm{l}\mathrm{o}+\lceil d\mathrm{/}2\rceil$ lies strictly between the endpoints; replacing the endpoint with the same predicate value preserves the invariant and leaves width at most $\lceil d\mathrm{/}2\rceil$. Thus after $O(n)$ steps the width is one and $\mathrm{h}\mathrm{i}$ is the least positive integer satisfying $P$, namely $K$ by [F3].

The initial endpoint has $O(n)$ bits, so each midpoint does as well. A schoolbook square and multiplication compute $t{m}^2$ in $O(n^2)$ bit operations, and comparison with $N$ takes $O(n)$ more. The $O(n)$ predicate evaluations therefore cost $O(n^3)$.

The least $b\ge 0$ with $2^b\ge K$ satisfies $b\le \lceil n\mathrm{/}2\rceil$. The nine labels consume $9b=O(n)$ random bits and comparisons; forming or writing each at-most-$n$-bit address uses $O(n)$ more bookkeeping. Hence this work is within $O(n^3)$.

If $t>N\mathrm{/}2$, each of at most nine rounds measures the freshly prepared uniform quantum address. Handling these returned $n$-bit addresses and writing the result takes $O(n)$ classical bit operations in total; the state preparation and measurements are separate quantum operations, and no classical fair address bits are generated. For $n=0$, $N=t=1$ and the bookkeeping is constant. The bit-query invocations remain separately charged by [F4].