# Grover Search Algorithm

### Complexity
- Complexity class **P**
- example: Eulerian path
- Finding the solution: polynomially with the size of the problem
- checking the solution is easy as well
- Complexity class **NP**
- example: Hamiltonian path
- finding the solution is hard (cannot be achieved in polynomial time)
- checking the solution is easy
- **NP:** solution can be found by non-deterministic (N) Turing machine in polynomial (P) time
> such machine does not exist

- Hamiltonian Cycle (HC) can be **reduced** to Traveling Salesman Problem (TSP)
- If we can solve TSP, then we can solve HC
($G$ of HC, the original edges weight $1$ and the non-existing edges weight $2$, if there is a cycle value < $(n+1)$, where $n=(\#\text{ nodes})$, it contains HC.)
- If TSP is tractable, then HC is also tractable
- If HC is hard, then TSP must also be hard

- example: $k$-coloring
- Graph $2$-coloring is **P**
- Graph $3$-coloring is in **NP-complete**
- sudoku: **NP-complete**
- $2$-SAT (satisfiability) is **P**
- $(x_1\lor \bar{x_3})\land(x_2\lor \bar{x_4})\land...$
- $3$-SAT (satisfiability) is **NP-complete**
- $(x_1\lor \bar{x_2}\lor \bar{x_4})\land(x_2\lor \bar{x_3}\lor \bar{x_5})\land...$

- **BQP:** bounded-error quantum polynomial time
- with error probability of at most $\varepsilon$
- many decision problem can be considered as **search problem**

### Grover Search Algorithm
- **Problem:**
- Search through the space of $N=2^n$ elements
- $n$ bits information of the element
- assume that the number of solutions is exatly $M, M\ll N$
- can be represented by a function $f$
- $f(x) = 1$, then $x$ is the answer
- $f(x) = 0$, then $x$ is not the answer
- **Algorithm:**
- Oracle: $O_f$
- $|x\rangle|-\rangle\xrightarrow[]{O_f}(-1)^{f(x)}|x\rangle|-\rangle$
- If measure $|x\rangle$, then $x$ is not a solution
If measure $-|x\rangle$, then $x$ is a solution
> the oracle <ins>does not know</ins> any of the solution, it only able to <ins>recognize</ins> a solution
1. Prepare the initial state
- $$|\psi\rangle=\frac{1}{\sqrt{N}}\sum_x |x\rangle$$
-
$\begin{aligned}
\frac{1}{\sqrt{N}}\sum_x |x\rangle &= \frac{1}{\sqrt{N}}(\sqrt{N-M}\frac{1}{\sqrt{N-M}}\sum_{f(x)\neq 1} |x\rangle+\sqrt{M}\frac{1}{\sqrt{M}}\sum_{f(x)= 1} |x\rangle)\\
&= \sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle \\
&= \sqrt{1-\varepsilon}|\alpha\rangle+\sqrt{\varepsilon}|\beta\rangle
\end{aligned}$
where $\varepsilon=M/N\ll1$
- probability to find <ins>any</ins> solution. projector onto the solution space:
$$\hat{P}=\sum_{f(x)=1}|x\rangle\langle x|$$
probability = $\langle\psi|\hat{P}|\psi\rangle=\varepsilon$
2. Prepare a grover step $G$ iteratively $k$ times
- applying oracle $O_{f,\pm}$
- The oracle
$$O=\mathbb{I}-2\hat{P}=\mathbb{I}-2\sum_{f(x)=1}|x\rangle\langle x|$$
then
$O|x\rangle=|x\rangle$, if $|x\rangle$ is not a solution
$O|x\rangle=-|x\rangle$, if $|x\rangle$ is a solution
-
$\begin{aligned}
\sqrt{1-\varepsilon}|\alpha\rangle+\sqrt{\varepsilon}|\beta\rangle\xrightarrow[]{O_f} &\sqrt{1-\varepsilon}|\alpha\rangle-\sqrt{\varepsilon}|\beta\rangle \\
=& (\sqrt{1-\varepsilon}|\alpha\rangle+\sqrt{\varepsilon}|\beta\rangle)-2\sqrt{\varepsilon}|\beta\rangle \\
=& |\psi\rangle - 2\sqrt{\varepsilon}|\beta\rangle\end{aligned}$
- applying **reflection operator** $U=2|\psi\rangle\langle\psi|-\mathbb{I}$
- $\begin{aligned}UO|\psi\rangle &= (2|\psi\rangle\langle\psi|-\mathbb{I})(|\psi\rangle - 2\sqrt{\varepsilon}|\beta\rangle)\\
&= (1-4\varepsilon)\sqrt{1-\varepsilon}|\alpha\rangle+(3-4\varepsilon)\sqrt{\varepsilon}|\beta\rangle
\end{aligned}
$
- now, the probability to find any solution is $\approx 9\cdot\varepsilon$
increase by a factor of $9$
- geometric visualization
- $O_f$: reflect $|\psi\rangle$ over $|\beta\rangle$
- $G$: reflect $O|\psi\rangle$ over $|\psi\rangle$
- the original angle $\theta/2$
after $GO_f$, rotated by $\theta$ to $|\beta\rangle$
- after $k$ iterations
$$
G^k|\psi\rangle=\cos{(\frac{2k+1}{2}\theta)}|\alpha\rangle+\sin{(\frac{2k+1}{2}\theta)}|\beta\rangle$$
- the optimal $k$ steps
$$k\approx \frac{\pi}{4}\sqrt{\frac{N}{M}}$$
- complexity:
$$O(\sqrt{\frac{N}{M}})$$
classical: $O(N/M)$, a <ins>quadratic speedup</ins>
3. measuring all $n$-qubits yields an outcome $x$

- **Discussion**
- Is not reaching the solution state $|\beta\rangle$ exatly?
- in generally $\tilde{k}$ is not an integer
- choose the nearest $k$ still with small error probability
- Quantum computer cannot solve the NP-complete problem efficiently.
- example: Hamiltonian Path
- complexity $O(n^n)=O(2^{n\cdot\log(n)})$
- quantum computing $O(p(n)2^{n\cdot\log(n)/2})$
- $p(n)$: polynomial overhead
- $/2$: quantum speedup
- Grover Search is <ins>optimal</ins>
- can be proved no quantum algorithm can use less than $O(\sqrt{\frac{N}{M}})$ oracle access