[Quantum Information] Grover Search Algorithm

 Grover Search Algorithm

Notes from RWTH Aachen University course 
“Quantum Information” Summer semester 2020
professor: Müller, Markus

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  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 does not know any of the solution, it only able to recognize 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 any 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{1}-2\hat{P}=\mathbb{1}-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{1}$
     • $ $$\begin{aligned}UO|\psi\rangle &= (2|\psi\rangle\langle\psi|-\mathbb{1})(|\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 quadratic speedup
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 optimal
• can be proved no quantum algorithm can use less than $O(\sqrt{\frac{N}{M}})$ oracle access

Reading

Nielsen and Chuang

    6.1 The quantum search algorithm