10 Grover’s algorithm
Another well known quantum algorithm is Grover’s algorithm for searching. It was developed by Lov Grover in 1996.
Grover’s algorithm takes a function \(f: \{0,1\}^n \rightarrow \{0,1\}\), where exactly one \(x_0\) exists, such that \(f(x_0) = 1\). The goal is to find \(x_0\).
There are a number of interesting problems, which can be reduced to this general definition. One of these problems is the breaking of a (symmetric) encryption. The function \(f\) would take a key as an input and output a \(1\), if the decryption is successful.
Classically, finding this \(x_0\) takes approximately \(2^n\) steps (when simply bruteforcing the function). Using Grover’s algorithm, we can reduce this runtime to approximately \(2^{\frac{n}{2}}\) steps. As an example, a \(128\)-bit encryption would only take about \(2^{64}\) steps to break it, instead of about \(2^{128}\) steps for the classical bruteforce.
10.1 Preparations
To construct Grover’s algorithm, we first need to introduce two new gates \(V_f\) and \(\operatorname{FLIP}_*\).
10.1.1 Constructing the oracle \(V_f\)
In the previous algorithms, we have learned that we can implement a function \(f\) as a unitary \(U_f\) with \(U_f\ket{x,y} = \ket{x, y \oplus f(x)}\). We construct a different unitary called \(V_f\) from this, which has the following behavior:
\[ V_f \ket{x} = \begin{cases} -\ket{x} & \text{if } f(x) = 1\\ \ket{x} & \text{else} \end{cases} \]
We can construct \(V_f\) from \(U_f\) using the following circuit:
The bottom wire can be discarded, since it always contains a \(\ket{-}\) and thus is not entangled with the upper wire.
10.1.2 Constructing \(\operatorname{FLIP}_*\)
As a second ingredient for Grover’s algorithm, we define a unitary called \(\operatorname{FLIP}_*\). This unitary does nothing, if it is applied on the uniform superposition \(\ket{*}\). For any other quantum state \(\psi\) with \(\psi\) orthogonal to \(\ket{*}\) it maps \(\psi\) to \(-\psi\). The uniform superposition \(\ket{*}\) simply denotes the superposition over all classical possibilities \(2^{-\frac{n}{2}}\sum_x \ket{x}\). We can construct this \(\operatorname{FLIP}_*\) by the following quantum circuit:
\(\operatorname{FLIP}_0\) is here definied by the unitary \[ \operatorname{FLIP}_0 \ket{x} = \begin{cases} \ket{0} & \text{if } x = 0\\ -\ket{x} & \text{else} \end{cases} \]
10.2 The algorithm for searching
The actual algorithm takes a function \(f: \{0,1\}^n \rightarrow \{0,1\}\) and outputs an \(x_0\) with \(f(x_0)=1\). For simplicity, we assume that there is only one \(x_0\) for which \(f(x_0) = 1\) holds and for each other \(x \neq x_0\) it holds that \(f(x)=0\).
With the two new unitaries \(V_f\) and \(\operatorname{FLIP}_*\) defined, we can construct the circuit for Grover’s algorithm, which is shown in the following figure:
The algorithm works as follows:
- We start with a \(\ket{0}\) entry on every qubit.
- We bring the system into the superposition over all entries by applying \(H^{\otimes n}\). The quantum state is then \(2^\frac{-n}{2}\sum_x \ket{x}\) which we also call \(\ket{*}\).
- We apply the unitary \(V_f\).
- We apply the unitary \(\operatorname{FLIP}_*\).
- We repeat steps 3 and 4 \(t\) times, and then do a measurement.
The measurement in step 5 will then give us \(x_0\) with high probability.
10.2.1 Understanding the algorithm for searching
When looking at the quantum circuit, it is not completely intuitive why the algorithm gives the correct result. We therefore now look into what is happening in each step.
The desired quantum state after the algorithm finishes is \(\ket{x_0}\). At the beginning of the algorithm, we bring the system into the uniform superposition \(\ket{*} = 2^\frac{-n}{2}\sum_x \ket{x}\). We know that \(\ket{x_0}\) is part of this superposition, therefore we can rewrite \(\ket{*}\) as follows \[ \ket{*} = 2^{-\frac{n}{2}}\sum_x \ket{x} = \frac{1}{\sqrt{2^n}} \underbrace{\ket{x_0}}_{\textit{good}} + \sqrt{\frac{2^n-1}{2^n}} \underbrace{\sum_{x\neq x_0} \frac{1}{\sqrt{2^n-1}}\ket{x}}_{\textit{bad}} \]
So the current state can be seen as a superposition of a “good” state good and a “bad” state bad.
The geometric interpretation of this superposition can be drawn as follows:
The angel \(\theta\) denotes, how “good” the resulting outcome will be. If \(\theta = 0\), the state is completely bad, if \(\theta = \frac{\pi}{2}\), the state is completely good.
We can calculate \(\cos \theta = \lvert\braket{*|bad}\rvert = \frac{\sqrt{2^n-1}}{\sqrt{2^n}}\). From this we can derivate that the angle \(\theta\) is \(\cos^{-1} \sqrt{\frac{2^n-1}{2^n}}\) at the beginning, which is approximately \(\sqrt{\frac{1}{2^n}}\).
We now apply \(V_f\) on this quantum state. This will negate the amplitude off our desired \(\ket{x_0}\) and not change the amplitude to the rest of the state.
\[ V_f\ket{*}= -\frac{1}{\sqrt{2^n}} \underbrace{\ket{x_0}}_{\text{good}} + \sqrt{\frac{2^n-1}{2^n}} \underbrace{\sum_{x\neq x_0} \ket{x}}_{\text{bad}} \]
This looks like this in the geometric interpretation:
We can see that by applying \(V_f\), we mirror the vector across the bad axis.
After \(V_f\), we apply the \(\operatorname{FLIP}_*\) operation on the quantum state. Since \(\operatorname{FLIP}_*\) does nothing on the \(\ket{*}\) entries and negates the amplitude of any vector orthogonal to it, \(\operatorname{FLIP}_*\) mirrors the vector across \(\ket{*}\). This can be seen in the following figure:
All in all, we have seen that by applying \(V_f\) and \(\operatorname{FLIP}_*\), we can increase the angle of the quantum state in relation to the “good” and “bad” states by \(2\theta\). Therefore two reflection give rotation. By repeating this step often enough, we can get the amplitude of \(\ket{x_0}\) close to 1.
To be more precise: Since we know \(\theta\) and we know that we will increase the good-ness of our quantum state by \(2\theta\) each time, we can calculate that only \(t\) iterations are necessary with \[ t \approx \frac{\frac{\pi / 2}{\theta} - 1}{2} \approx \frac{\pi}{4 \theta} \approx \frac{\pi}{4} \cdot \sqrt{2^n} \] Grover’s algorithm therefore takes \(O(\sqrt{2^n})\) steps, where an evaluation of the circuit counts as one step.