Grover search algorithm

Grover search rotates a uniform state toward a marked subspace and finds one of $M$ marked entries using order $\sqrt{N/M}$ oracle calls.

For a permutation $f$ of an $N$-element set and a known marked output subset of size $K$, exactly $K$ inputs have marked outputs. The uniform quantum superposition thus has good probability $K/N$, independent of which permutation the oracle represents. This allows a known-angle amplitude amplification schedule without counting unknown preimages.

To find an input of a permutation whose output lies in a known $K$-element subset, compute the output, apply its marked-state phase oracle, and use uncomputation. A modular-addition quantum oracle costs two forward queries per marked reflection, because modular-oracle inversion by negation supplies its inverse. Amplitude amplification then uses $O(\sqrt{N/K})$ queries for fixed success probability. Positive-square outputs have $K=\lfloor \sqrt{N-1}\rfloor$ and hence query cost $O(N^{1/4})$.

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$.

For $|s⟩=H^{\otimes n}|0^n⟩$, the diffusion operator is $2|s⟩⟨s|-I=-H^{\otimes n}{I}_0{H}^{\otimes n}$, where $I_0=I-2|0^n⟩⟨0^n|$.

The diffusion operator sends every computational-basis amplitude $a_x$ to $2\overline{a}-a_x$, where $\overline{a}$ is their arithmetic mean.

If $M$ of $N$ items are marked and $\sin \theta =\sqrt{M/N}$, each Grover iteration rotates the state by $2\theta$ in the marked--unmarked plane, so after $r$ iterations the marked amplitude is $\sin ((2r+1)\theta )$.

For $N=4$ and one marked item, $\theta =\pi /6$. One Grover iteration gives marked amplitude $\sin (3\theta )=1$, so measurement returns the target with certainty.