Known-subset Grover search ($O(\sqrt{|B|/k})$)

For a known finite set $B$, prepare the uniform superposition state $|s_B⟩$ and implement its reflection operator $2|s_B⟩⟨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$.

Suppose a known list of $2^m$ distinct $n$-bit strings $a_j$ is available and computational basis transpositions on $n+m$ qubits have polynomial-size implementations. Start with the uniform superposition state of index labels $j$, leaving the data zero. First swap $|0^n,j⟩$ with $|a_j,j⟩$ for each nonzero $a_j$. Next, for each $j\ne 0$, swap $|a_j,j⟩$ with $|a_j,0^m⟩$. Distinct index labels separate the first-stage pairs, and distinct data strings separate the second-stage pairs. Thus no later transposition disturbs an earlier term. At most $2^{m+1}-1$ transpositions prepare the uniform data state and return the quantum ancilla to zero. For $m=O(\log n)$ the quantum circuit has polynomial size. This assumes the list is available; a membership predicate alone does not supply it.