grover's search algorithm

Problem: Given $N=2^n$ items, find a particular item

• We have a function $f(x)$ s.t. $f(x)=1;x=z$ where z is the item of interest and $0$ everywhere else
• A classical algorithm takes $O(N)$ steps on average while Grover's algorithm takes $O(\sqrt{N})$ steps

$P_0$ Transformation

We define the conditional phase shift transformation as$$P_0 : |x\rangle \mapsto \begin{cases} |x\rangle &\quad{} x=0 \ -|x\rangle &\quad{} x>0\end{cases}$$$$P_0 = 2|0\rangle\langle0| - I$$

${\mathcal{U}}_f$ Transformation

Consider the standard oracle setup$$\mathcal{U}_f: |x \rangle |y \rangle \mapsto|x\rangle |y \oplus f(x)\rangle$$

• If $f(x)=1$ then $|y\oplus f(x)⟩=-|y⟩$
• If $f(x)=0$ then $|y\oplus f(x)⟩=|y⟩$

We can generalize this to$$\mathcal{U}_f: |x\rangle | y\rangle \mapsto (-1)^{f(x)} |x\rangle |y\rangle$$Rewriting $|x⟩$ as $\sum _x{\alpha }_x|x⟩$ and dropping $|y⟩$ for simplicity we get$$\mathcal{U}_f: \sum_x \alpha_x |x\rangle \mapsto (-1)^{f(x)} \alpha_x |x\rangle$$
Example: $$|s\rangle := |00\rangle + |01\rangle + |10\rangle + |11\rangle \hspace{3em} z:= |10\rangle$$$$\mathcal{U}_f |s\rangle = |00\rangle + |01\rangle - |10\rangle + |11\rangle $$

${\mathcal{U}}_s$ Transformation

Consider an arbitrary ket $|\psi ⟩$ $$|\psi\rangle = \sum a_x|x\rangle$$ $$\begin{array}{ll}\langle s|\psi\rangle &= \displaystyle \frac{1}{\sqrt 2^n} \sum_{x,x'} a_x \langle x|x'\rangle \ &= \displaystyle \frac{1}{\sqrt 2^n} \sum_x a_x\end{array}$$

Action of ${\mathcal{U}}_s$ arbitrary key$$\begin{array}{ll}\mathcal{U}_s |\psi \rangle &= (2|s\rangle\langle s| - I)|\psi \rangle\&=2|s\rangle\langle s | \psi \rangle - |\psi\rangle\&= (2 \sqrt{2^n} \bar{a})|s\rangle - |\psi\rangle \ &= \displaystyle(2 \sqrt{2^n} ,\bar{a}) \frac{1}{\sqrt{2^n}} \sum_x |x\rangle - \sum_x a_x |x\rangle \ &= \sum_x(2\bar{a} - a_x) |x\rangle\end{array}$$
Compare this to the original value of ket $|\psi ⟩=\sum _x{\alpha }_x|x⟩$. Let's compare the Amplitude w.r.t mean

Grover's Operator

Grover's operator causes a rotation of $2\theta$ where $\frac{\pi }{2}-\theta$ is the angle between $|s⟩$ and $|z⟩$

Thus, we can perform this operation $m$ times to align the ket's together. Since each operation of this operator rotates it by $2\theta$ and we want to align it with $\frac{\pi }{2}-\theta$ $$\begin{array}{ll}m(2\theta) &= \frac{\pi}{2} - \theta \ m &= \frac{\pi}{4\theta} - \frac{1}{2} \ m &\approx\frac{\pi \sqrt N}{4}\end{array}$$ since $\theta \approx \sin \theta =\frac{1}{\sqrt{N}}$

Example: Consider the 3 qubit case wherein we are interested in $z=|4⟩$ from $|\psi ⟩=\frac{1}{\sqrt{2^2}}\sum _x|x⟩$.In the standard ket $|s⟩$ each basis has an amplitude of $\frac{1}{\sqrt{8}}$
Consider the application of ${\mathcal{U}}_f$:$$\mathcal{U}_f | \psi \rangle = \frac{1}{\sqrt 8}( |0\rangle + |1\rangle + \ldots | 8\rangle) - \frac{1}{\sqrt8} |4\rangle$$The new mean amplitude $\overline{a}$ becomes:$$\bar{a} = \frac{1}{8}[\frac{7}{\sqrt8} - \frac{1}{\sqrt8}] = \frac{3}{8 \sqrt2}$$Now, consider the application of ${\mathcal{U}}_s$:

• for every unmarked state the amplitude becomes $$2(\frac{3}{8 \sqrt2}) - \frac{1}{2\sqrt2} = \frac{1}{4\sqrt2}$$
• for every marked state the amplitude becomes $$2(\frac{3}{8 \sqrt2}) + \frac{1}{2\sqrt2} = \frac{5}{4\sqrt2}$$