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

$$\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}$$ (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.

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

In 3.5.1.1 we have shown how such a state can be prepared by a $n$-qubit Hadamard transform

$$H:{\vert i \rangle}\to 2^{-\frac{n}{2}} \sum_{j\in\mathbf{B}^n} (-1)^{(i,j)}{\vert j \rangle}$$ (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.
   

   $$Q: {\vert i \rangle}\to \left\{ \begin{array}{cl} -{\vert... ...vert i \rangle} & \mathrm{if}\;\neg C(i) \end{array}\right.$$ (4.4)

   
   

2. Apply a diffusion operator
   

   $$D=\sum_{ij} {\vert i \rangle}d_{ij}{\langle j\vert} \quad\... ... \\ \frac{2}{N} & \mathrm{if}\;i\neq j \end{array}\right.$$ (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

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

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

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

so one iteration on a state of the form

$${\vert\Psi(k,l) \rangle}=k{\vert i_0 \rangle}+\sum_{i\neq i_0} l{\vert i \rangle}$$ (4.8)

amounts to

$${\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}$$ (4.9)

Number of Iterations

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

$${\vert\Psi \rangle}={\vert\Psi(\frac{1}{\sqrt{N}},\frac{1}{... ...\rangle}= \frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}{\vert i \rangle}$$ (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]

$$k_{j+1} = \frac{N-2}{N}k_j+\frac{2(N-1)}{N}l_j$$ (4.11)

$$l_{j+1} = \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.

$$k_{j} = \sin((2j+1)\theta)$$ (4.13)

$$l_{j} = \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

$$Q= {\mathtt{query}}^\dagger (\mathbf{x},\mathbf{f}) V(\pi)(\mathbf{f}) \mathtt{query}(\mathbf{x},\mathbf{f})$$ (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

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

can also be written as $D=HRH$ since

$$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$$ (4.17)

$$\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$$ (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