Known-count Grover search by exact integer maximization

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$, standard bit-query access to $f=1_M$, and the exact integer $t=\mathrm{\mid }M\mathrm{\mid }$. If $t=0$, return none without a query. If $t>0$, find $K$ as the least positive integer with $t{K}^2\ge N$: start with $\mathrm{l}\mathrm{o}=0,\mathrm{h}\mathrm{i}=1$, repeatedly set $\mathrm{l}\mathrm{o}=\mathrm{h}\mathrm{i},\mathrm{h}\mathrm{i}=2\mathrm{h}\mathrm{i}$ while $t{\mathrm{h}\mathrm{i}}^2<N$, then use upper-midpoint binary search on the false/true interval until $\mathrm{h}\mathrm{i}-\mathrm{l}\mathrm{o}=1$. Thus $K=\mathrm{h}\mathrm{i}=\lceil \sqrt{N\mathrm{/}t}\rceil$. Prepare $\mathrm{\mid }s⟩=H^{\otimes n}\mathrm{\mid }{0}^n⟩$, set $q=1-2t\mathrm{/}N$, and compute exactly the rational recurrence $T_0(q)=1,T_1(q)=q,T_{m+1}(q)=2q{T}_m(q)-T_{m-1}(q)(1\le m\le 2K)\mathrm{.}$ Compute the recurrence through index $m=2K+1$. For each integer $k=0,\dots ,K$, compute $p_k=(1-T_{2k+1}(q))\mathrm{/}2$. Choose the least $k$ attaining the maximum of this finite rational list, apply One Grover iterate in the standard bit-query model exactly $k$ times, measure the address register, and make one separate standard bit query to verify the candidate. Return the candidate if marked and the failure symbol otherwise. The state preparation, all-zero reflection, classical recurrence and comparison work, and oracle queries are distinct costs; this definition makes no polynomial-time preprocessing claim.