Grover's 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 both oracle phases equal to $\pi$, the good/bad matrix is $\left(\begin{array}{cc}\cos 2\chi & \sin 2\chi \\ -\sin 2\chi & \cos 2\chi \end{array}\right)$. Acting $r$ times on the initial vector $(\sin \chi ,\cos \chi )$ yields success ${\sin }^2((2r+1)\chi )$. For $0<\chi \le \pi /4$, the first crossing of one half is the displayed integer, since the rounded angle stays between $\pi /4$ and $3\pi /4$. With ${\sin }^2\chi =m/N\ll 1$ this is asymptotic to $(\pi /8)\sqrt{N/m}$. Iterating indefinitely is incorrect: the success oscillates after its first maximum.

Take normalized states with real positive overlap $a\in (0,1)$. The eigenvectors proportional to $|s⟩\pm |w⟩$ have energies $\Delta (1\pm a)$. With $\hslash =1$, their relative phase changes by $\pi$ after the displayed time, giving $e^{-iH{t}_{\ast }}|s⟩=-i{e}^{-i\Delta t_{\ast }}|w⟩$. For a uniform search state and one marked basis vector in dimension $D$, $a=D^{-1/2}$, so the time is proportional to $\sqrt{D}$. Implementing the marked projector assumes access to a search oracle; the formula does not supply oracle information for free.

Let $|s⟩=H^{\otimes n}|0^n⟩$, let $U_f$ be the marked-state phase oracle, and replace reflection about $|0^n⟩$ by reflection about a known computational basis vector $|y⟩$. Define $T_y={⨂}_{j=0}^{n-1}{Z}_j^{y_j}$, so $T_y|x⟩=(-1{)}^{x\cdot y}|x⟩$ and $H^{\otimes n}|y⟩=T_y|s⟩$. The resulting Grover iterate obeysbecause the two diagonal operators $T_y,U_f$ commute. Thus the good and bad uniform vectors are replaced by their signed vectors $T_y|g⟩,T_y|b⟩$, with exactly the same Grover rotation angle. Initializing in $H^{\otimes n}|y⟩$ gives $G_y^r|s_y⟩=T_y{G}^r|s⟩$. Computational-basis measurement probabilities are unchanged because $T_y$ only multiplies amplitudes by signs.

Under the promise of either no marked entry or one marked entry in an $N$-element Boolean quantum oracle search space, run the Grover search algorithm for the displayed number of iterations, measure a candidate, and make one additional oracle query to check it. Since $|(2k+1)\theta -\pi /2|\le \theta$, the marked-entry success probability is at least ${\cos }^2\theta =1-1/N$. For $N\ge 4$ this is at least $3/4$. If no entry is marked the verification never accepts, so there is no false positive. The query count is $k+1=O(\sqrt{N})$ because $\theta \ge 1/\sqrt{N}$. Measuring a candidate without verification would not determine whether a marked entry exists.

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

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.

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

If the marked fraction is $p$ and $\theta =\arcsin \sqrt{p}$, the success probability after $n$ Grover search algorithm iterations is ${\sin }^2((2n+1)\theta )$. For $0<p\le 1/2$, its first value at least $1/2$ occurs atBefore this integer the angle is below $\pi /4$, so success is below $1/2$. At this integer, the angle lies in $[\pi /4,\pi /4+2\theta )$, contained in $[\pi /4,3\pi /4)$, where squared sine is at least $1/2$. If $p\ge 1/2$, no iteration is needed. For small $p$, $n_{\min }$ is asymptotic to $\pi /(8\sqrt{p})$.

For one marked element among $N\ge 2$ candidates, set $\theta =\arcsin (N^{-1/2})$. The first nonnegative Grover search algorithm iteration count attaining marked probability at least ${\cos }^2\theta$ is the displayed integer. Before the first success interval, the angle $(2k+1)\theta$ is below $\pi /2-\theta$; entering that interval requires $k\ge \pi /(4\theta )-1$. Rounding up gives an angle less than $\pi /2+\theta$, so it cannot skip the interval. Moreover $k_{\min }<\pi /(4\theta )<\pi \sqrt{N}/4$. For $N=1$, the known candidate is already the answer and no iteration is needed; the two-dimensional marked--unmarked plane degenerates.

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.