One Grover iterate in the standard bit-query model

Gate model. The declared nonoracle model permits exact callable $H$ and $X$, each occurrence charged as one elementary gate. It supplies the exact reflection $R_s$ either as an explicitly costed primitive or through a declared costed circuit over the selected gate alphabet; for the displayed Hadamard conjugation, the all-zero reflection and both Hadamard layers must be supplied and charged. Standard bit queries are charged separately.

For a marked-search instance on $D_n$, let $\mathrm{\mid }s⟩=H^{\otimes n}\mathrm{\mid }{0}^n⟩=N^{-1\mathrm{/}2}{\sum }_{x\in D_n}\mathrm{\mid }x⟩$ and $R_s=2\mathrm{\mid }s⟩⟨s\mathrm{\mid }-I$. Prepare a response qubit from $\mathrm{\mid }0⟩$ by applying $X$ and then $H$, giving $\mathrm{\mid }-⟩$. Apply the standard bit query $U_f$ to the address and response registers; phase kickback applies $O_M$ to the address and leaves the response in $\mathrm{\mid }-⟩$. Then apply $R_s$ to the address register. This defines $G=R_s{O}_M$ with one standard bit query and no intermediate measurement. Repeated iterates reuse the response qubit in $\mathrm{\mid }-⟩$. The query count is separate from the preparation and reflection gate costs. A reflection about $\mathrm{\mid }s⟩$ may be represented as $H^{\otimes n}(2\mathrm{\mid }{0}^n⟩⟨0^n\mathrm{\mid }-I)H^{\otimes n}$, whose reflection cost must be charged under the declared gate model.