###### tags: `Quantum Computing`

# Grover's Algorithm
Grover's algorithm is a quantum algprithms for counting or searching solutions. In classical calculations searching algorithms needs calculation cost of $O(N)$, while Grover's algorithm needs only $O(\sqrt{N})$.

## Procedures
1. Define states $\left|s\right>$, $\left|f\right>$ and $\left|\psi\right>$.
\begin{eqnarray}
\left|s\right> =&& \frac{1}{\sqrt{M}}\sum_{x:f(x)=1}^{} \left|x\right> \\
\left|f\right> =&& \frac{1}{\sqrt{N-M}}\sum_{x:f(x)=0}^{} \left|x\right> \\
\left|\psi\right> =:&& \frac{1}{\sqrt{N}}\sum_{x}^{} \left|x\right> \\
=&& \sqrt{\frac{M}{N}}\left|s\right> + \sqrt{\frac{N-M}{N}}\left|f\right>\\
=&& \sin\theta \left|s\right> + \cos\theta \left|f\right>
\end{eqnarray}

> $s,f$ stands for success and failure respectively.

2. Define Grover's operator $G$.
\begin{eqnarray}
G = -WV_f
\end{eqnarray}
where
\begin{eqnarray}
V_f =&& I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right|, \\
W =&& I - 2 \left|\psi\right>\left<\psi\right|
\end{eqnarray}

3. Prepare states $G^k \left|\psi\right>$.
\begin{eqnarray}
G^k \left|\psi\right> = \sin(2k+1)\theta \left|s\right> + \cos(2k+1)\theta \left|f\right>
\end{eqnarray}
where,
\begin{eqnarray}
\theta \sim \sqrt{\frac{M}{N}}
\end{eqnarray}

4. Find minimum positive $k=k_m$ that maximize the probability to measure $\left|s\right>$.

The probability in suceeding measuring $\left|s\right>$ can be written as
\begin{eqnarray}
\left|\left<s\middle|G^k\psi\right>\right|^2 = \sin^2(2k+1)\theta
\end{eqnarray}

Therefore,
\begin{eqnarray}
(2k_m+1)\sqrt{\frac{M}{N}} \sim \frac{\pi}{2} \\
k_m \sim O\left(\sqrt{\frac{N}{M}}\right)
\end{eqnarray}

## Applications
### Boyer, Brassard, Høyer, and Tapp 1998
### Brassard et al. 1997
### Ambainis et al. 2019
### Shimizu and Mori 2019
https://arxiv.org/pdf/1907.00529.pdf

## memo
### the unitarity of Grover's operator
\begin{eqnarray}
V_f =&& I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right|, \\
W =&& I - 2 \left|\psi\right>\left<\psi\right|
\end{eqnarray}

#### $V_f$
\begin{eqnarray}
V_f^\dagger =&& I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right| (= V_f)\\
\therefore V_f^\dagger V_f =&& (I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right|)(I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right|)\\
=&& I - 2\times 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right| + 4 \sum_{x:f(x)=1}^{} \left|x\right>\left<x\right| = I
\end{eqnarray}

#### $W$
\begin{eqnarray}
W^\dagger =&& I - 2\left|\psi\right>\left<\psi\right| (= W)\\
\therefore W^\dagger W =&& (I - 2\left|\psi\right>\left<\psi\right|)(I - 2\left|\psi\right>\left<\psi\right|)\\
=&& I - 2\times 2\left|\psi\right>\left<\psi\right| + 4 \left|\psi\right>\left<\psi\right| = I
\end{eqnarray}

Thus, $V_f, W$ are both unitary operator, and so does their product $V_fW$ (Grover's operator) too.

### geometric interpretations

\begin{eqnarray}
G \left|\psi'\right> =&& -WV_f \left(\sin\phi \left|s\right> + \cos\phi \left|f\right>\right)\\
=&& -W (I - 2\sum_{x:f(x)=1}^{} \left|x\right>\left<x\right|) \left(\sin\phi \left|s\right> + \cos\phi \left|f\right>\right)\\
=&& -W \left(\sin\phi \left|s\right> + \cos\phi \left|f\right>\right) + 2 W \sin\phi \sum_{x:f(x)=1}^{} \left|x\right>\left<x\middle|s\right>\\
=&& W \left(\sin\phi \left|s\right> - \cos\phi \left|f\right>\right)\\
=&& (I - 2 \left|\psi\right>\left<\psi\right|) \left(\sin\phi \left|s\right> - \cos\phi \left|f\right>\right)\\
=&& \left(\sin\phi - 2\sin\phi\sin^2\theta + 2\cos\phi\sin\theta\cos\theta\right)\left|s\right> + \left(-\cos\phi - 2\sin\phi\sin\theta\cos\theta + 2\cos\phi\cos^2\theta\right)\left|f\right>\\
=&& \sin(\phi+2\theta)\left|s\right> + \cos(\phi+2\theta)\left|f\right>
\end{eqnarray}

Thus grover operator rotates the state for $2\theta$ anticlockwise as mapped on the $\left|s\right>-\left|f\right>$ plane shown below.

* In the figure shows state $\left|\psi\right>$ whose angle is $\theta$, is rotate by Grover's operator. In general, state can be any state namely $\left|\psi'\right>$ whose angle is $\phi$.

### how to construct Grover's operator on quantum computer