Gate and reflection accounting for randomized known-count search

Applying $H$ to each of the $n$ address wires sends $\mathrm{\mid }{0}^n⟩$ to $2^{-n\mathrm{/}2}{\sum }_x\mathrm{\mid }x⟩=\mathrm{\mid }s⟩$ by the tensor-product action, using exactly $n$ occurrences of $H$ by [F2] and [F5]. The $n=0$ case has no such occurrences.

Since $H^{\otimes n}\mathrm{\mid }{0}^n⟩=\mathrm{\mid }s⟩$ and $(H^{\otimes n}{)}^{†}=H^{\otimes n}$, conjugating $R_0$ gives $H^{\otimes n}{R}_0{H}^{\otimes n}=2\mathrm{\mid }s⟩⟨s\mathrm{\mid }-I=R_s$. This costs $2n$ Hadamards plus the declared $C(R_0)$; [F3]–[F4] do not make the all-zero reflection free.

In the $t\le N\mathrm{/}2$ branch each round has at most one fresh preparation, two gates $X,H$ for the response qubit, and at most $K-1$ iterates. Each iterate has the nonoracle cost in step 2.1; its query is excluded from this gate total by [F5]–[F6]. Multiplying the per-round bound by nine gives the stated upper bound, including rejected rounds as zero-cost cases.

When $t>N\mathrm{/}2$, each of at most nine direct rounds only prepares $\mathrm{\mid }s⟩$ and measures/verifies, so there are at most $9n$ Hadamards and no diffusion reflection. The t=0 branch returns before preparation.