next up previous contents
Next: Shor's Algorithm for Quantum Up: Quantum Algorithms Previous: Quantum Algorithms   Contents

Subsections


Grover's Database Search

Many problems in classical computer science can be reformulated as searching a list for a unique element which matches some predefined condition. If no additional knowledge about the search-condition $C$ is available, the best classical algorithm is a brute-force search i.e. the elements are sequentially tested against $C$ and as soon as an element matches the condition, the algorithm terminates. For a list of $N$ elements, this requires an average of $\frac{N}{2}$ comparisons.

By taking advantage of quantum parallelism and interference, Grover found a quantum algorithm which can find the matching element in only $O(\sqrt{N})$ steps. [20]


Formulating a Query

The most straightforward way, albeit not the most convenient for the algorithm, to implement the search condition is as a quantum function

\begin{displaymath}
\mathtt{query}:{\vert x,0 \rangle}\to{\vert x,C(x) \rangle}...
...\mathbf{B}^n\quad\mathrm{and}\quad C:\mathbf{B}^n\to\mathbf{B}
\end{displaymath} (4.1)

as this allows us to formulate the problem within the realms of classical boolean logic.

Grover's algorithm can then be used to solve the equation $C(x)=1$ while besides the fact that a solution exists and that it is unique, no additional knowledge about $C(x)$ is required.

Usually, the implementation of $\mathtt{query}$ will be complicated enough as not to allow an efficient algebraic solution, but since the inner structure of $C(x)$ doesn't matter for the algorithm, we can easily implement a test query with the solution $n$ as

qufunct query(qureg x,quvoid f,int n) {
  int i;

  for i=0 to #x-1 {     // x -> NOT (x XOR n)
    if not bit(n,i) { Not(x[i]); }
  }
  CNot(f,x);            // flip f if x=1111..
  for i=0 to #x-1 {     // x <- NOT (x XOR n)
    if not bit(n,i) { !Not(x[i]); }
  }
}

A more realistic application would be the search for an encryption key in a known-plaintext attack. With $p$ being the known plaintext to the ciphertext $c$, a QCL implementation could look like this:

qufunct encrypt(int p,quconst key,quvoid c) { ... }

qufunct query(int c,int p,quconst key,quvoid f) {
  int i;
  quscratch s[blocklength];

  encrypt(p,key,s);
  for i=0 to #s-1 {     // s -> NOT (s XOR p)
    if not bit(p,i) { Not(x[i]); }
  }
  CNot(f,x);            // flip f if s=1111..
}
Note that, unlike the example above, this query function uses a local scratch register, so it isn't necessary to explicitely uncompute $\mathbf{s}$, as this will be taken care of by QCL's internal scratch space management (see 3.3.1.5).


The Algorithm

Setting up the Search Space

The solution space of a $n$ bit query condition $C$ is $\mathbf{B}^n$. On a quantum computer, this search space can be implemented as a superposition of all eigenstates of an $n$ qubit register, i.e.

\begin{displaymath}
{\vert\Psi \rangle}=\frac{1}{\sqrt{N}} \sum_{i=0}^N {\vert i \rangle}
\quad\mathrm{with}\quad N=2^n
\end{displaymath} (4.2)

In 3.5.1.1 we have shown how such a state can be prepared by a $n$-qubit Hadamard transform
\begin{displaymath}
H:{\vert i \rangle}\to 2^{-\frac{n}{2}}
\sum_{j\in\mathbf{B}^n} (-1)^{(i,j)}{\vert j \rangle}
\end{displaymath} (4.3)

(see 3.4.4.3) of the initial machine state ${\vert \rangle}$.

The Main Loop

The main loop of the algorithm consists of two steps

  1. Perform a conditional phase shift which rotates the phase of all eigenvectors which match the condition $C$ by $\pi$ radians.
    \begin{displaymath}
Q: {\vert i \rangle}\to
\left\{ \begin{array}{cl}
-{\vert...
...vert i \rangle} & \mathrm{if}\;\neg C(i)
\end{array}\right.\end{displaymath} (4.4)

  2. Apply a diffusion operator
    \begin{displaymath}
D=\sum_{ij} {\vert i \rangle}d_{ij}{\langle j\vert}
\quad\...
... \\
\frac{2}{N} & \mathrm{if}\;i\neq j
\end{array}\right.\end{displaymath} (4.5)

Since only one eigenvector ${\vert i_0 \rangle}$ is supposed to match the search condition $C$, the conditional phase shift will turn the initial even superposition into

\begin{displaymath}
{\vert\Psi' \rangle}=
-\frac{1}{\sqrt{N}} {\vert i_0 \rangle}+
\frac{1}{\sqrt{N}} \sum_{i\neq i_0} {\vert i \rangle}
\end{displaymath} (4.6)

The effect of the diffusion operator on an arbitrary eigenvector ${\vert i \rangle}$ is

\begin{displaymath}
D {\vert i \rangle}=-{\vert i \rangle}+\frac{2}{N} \sum_{j=0}^{N-1} {\vert j \rangle}
\end{displaymath} (4.7)

so one iteration on a state of the form
\begin{displaymath}
{\vert\Psi(k,l) \rangle}=k{\vert i_0 \rangle}+\sum_{i\neq i_0} l{\vert i \rangle}
\end{displaymath} (4.8)

amounts to
\begin{displaymath}
{\vert\Psi(k,l) \rangle}\stackrel{Q}{\longrightarrow}{\vert...
...{N}k+\frac{2(N-1)}{N}l,
\frac{N-2}{N}l-\frac{2}{N}k) \rangle}
\end{displaymath} (4.9)

Number of Iterations

If the above loop operator $DQ$ is repeatedly applied to the initial superposition

\begin{displaymath}
{\vert\Psi \rangle}={\vert\Psi(\frac{1}{\sqrt{N}},\frac{1}{...
...\rangle}=
\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}{\vert i \rangle}
\end{displaymath} (4.10)

then the resulting states is still of the form ${\vert\Psi(k,l) \rangle}$ and the complex amplitudes $k$ and $l$ are described by the following system of recursions: [21]
$\displaystyle k_{j+1}$ $\textstyle =$ $\displaystyle \frac{N-2}{N}k_j+\frac{2(N-1)}{N}l_j$ (4.11)
$\displaystyle l_{j+1}$ $\textstyle =$ $\displaystyle \frac{N-2}{N}l_j-\frac{2}{N}k_j$ (4.12)

Using the substitution $\sin^2\theta=\frac{1}{N}$ the solution of the above system can be written in closed form.

$\displaystyle k_{j}$ $\textstyle =$ $\displaystyle \sin((2j+1)\theta)$ (4.13)
$\displaystyle l_{j}$ $\textstyle =$ $\displaystyle \frac{1}{\sqrt{N-1}} \cos((2j+1)\theta)$ (4.14)

The probability $p$ to measure $i_0$ is given as $p=k^2$ and has a maximum at $\theta=\frac{\pi}{2(2j+1)}$. Since for large lists, $\frac{1}{\sqrt{N}}\ll 1$ we can assume that $\sin\theta\approx\theta$ and $\pi\gg 2\theta$ and the number of iterations $m$ for a maximum $p$ is about $m=\lfloor \frac{\pi}{4}\sqrt{N} \rfloor$ with $p>\frac{N-1}{N}$ (due to rounding errors). Alternatively, if we are content with $p>\frac{1}{2}$, then $m=\lceil \frac{\pi}{8}\sqrt{N} \rceil$ iterations will do.

Implementation

The Query Operator

If we choose to formulate the query as quantum function with a flag qubit $\mathbf{f}$ to allow for a strictly classical implementation, as suggested in 4.1.1, then the operator $Q$ can be constructed as

\begin{displaymath}
Q=
{\mathtt{query}}^\dagger (\mathbf{x},\mathbf{f}) 
V(\pi)(\mathbf{f}) 
\mathtt{query}(\mathbf{x},\mathbf{f})
\end{displaymath} (4.15)

by using the conditional phase gate $V(\phi)$ (see 3.4.4.4) and considering the flag register $\mathbf{f}$ as temporary scratch space.

The Diffusion Operator

Using the Hadamard Transform $H$ (see 3.4.4.3) and a conditional phase rotation $R:{\vert i \rangle}=-(-1)^{\delta{i0}}{\vert i \rangle}$, the diffusion operator

\begin{displaymath}
D=\sum_{i,j}{\vert i \rangle}\left(\frac{2}{N}-\delta_{ij}\right){\langle j\vert}
\end{displaymath} (4.16)

can also be written as $D=HRH$ since
\begin{displaymath}
HRH=-\frac{1}{N}\sum_{i,k,j} {\vert i \rangle} (-1)^{(i,k)...
...a_{k0}}(-1)^{(k,j)}  {\langle j\vert} \quad\mathrm{and}\quad
\end{displaymath} (4.17)


\begin{displaymath}
\sum_{k=0}^{N-1}
(-1)^{(i,k)}(-1)^{\delta_{k0}}(-1)^{(k,j)}=
-2+\sum_{k=0}^{N-1} (-1)^{(i,k)(k,j)}=N\delta_{ij}-2
\end{displaymath} (4.18)

Using the $\mathtt{not}$ operator from 3.4.7.4 and a conditional phase gate $V(\phi)$ we can implement the diffusion operator as

operator diffuse(qureg q) {
  Mix(q);               // Hadamard Transform
  Not(q);               // Invert q
  CPhase(pi,q);         // Rotate if q=1111..
  !Not(q);              // undo inversion
  !Mix(q);              // undo Hadamard Transform
}

In fact, the above operator implements $-D$, but since overall phases make no physical difference, this doesn't matter.

The Procedure grover

By using the above, we can now give a QCL implementation of the complete algorithm:

procedure grover(int n) {
  int l=floor(log(n,2))+1;        // no. of qubits
  int m=ceil(pi/8*sqrt(2^l));     // no. of iterations
  int x;
  int i;
  qureg q[l];
  qureg f[1];

  {
    reset;
    Mix(q);             // prepare superposition
    for i= 1 to m {     // main loop
      query(q,f,n);     // calculate C(q)
      CPhase(pi,f);     // negate |n>
      !query(q,f,n);    // undo C(q)
      diffuse(q);       // diffusion operator
    }
    measure q,x;        // measurement
    print "measured",x;
  } until x==n;
}
The procedure argument $n$ is the number to be found; the size of the quantum registers as well as the numbers of iterations are set accordingly:
qcl> grover(500);
: 9 qubits, using 9 iterations 
: measured 500 
qcl> grover(123);
: 7 qubits, using 5 iterations 
: measured 74 
: measured 123 
qcl> grover(1234);
: 11 qubits, using 18 iterations 
: measured 1234


next up previous contents
Next: Shor's Algorithm for Quantum Up: Quantum Algorithms Previous: Quantum Algorithms   Contents

(c) Bernhard Ömer - oemer@tph.tuwien.ac.at - http://tph.tuwien.ac.at/~oemer/