[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