= Known-subset Grover search
{title2=$O(\sqrt{|B|/k})$}
For a known finite set $B$, prepare the <uniform superposition state> $|s_B\rangle$ and implement its <reflection operator> $2|s_B\rangle\langle s_B|-I$. If exactly $k$ basis states in $B$ are marked, the same two-dimensional <Grover rotation angle> argument uses $O(\sqrt{|B|/k})$ phase queries. Preparation and reflection are known operations with no calls to the unknown predicate. Their gate cost must be accounted for separately. The success guarantee requires $k>0$, and choosing the optimal iteration number uses a known $k$.
Back to article page
