3  Grover and Shor

We looked at two algorithms: Grover and Shor.

3.1 Shor’s Algorithm

In order to look at Shor, we need to understand the discrete Fourier transform, or DFT. The matrix for DFT is defined as follows.

Definition 3.1 (Discrete Fourier Transformation (DFT)) The discrete Fourier transform (DFT) is a linear transformation on \(\mathbb{C}^M\) represented by the matrix \[ \operatorname{DFT}_M = \frac{1}{\sqrt{M}} (\omega^{kl})_{kl} \in \mathbb{C}^{M\times M} \] with \(\omega = e^{2i\pi/M}\), which is the \(M\)-th root of unity. This means that \(\omega\) taken to the power of \(2^n\) equals 1.

We use the DFT to map a t-periodic vector to a vector with non-zero entries at multiples of \(\frac{2^n}{t}\). The DFT can be implemented as a unitary operation on \(n\) qubits using \(O(n^2)\) gates.

Shor’s algorithm is used for period finding. Given a function \(f(x) = f(x+t)\), we are looking for t.

The circuit for Shor’s algorithm

The algorithm works as follows:

  1. We start with a \(\ket{0}\) entry on every wire.
  2. We bring the top wire into the superposition over all entries. The quantum state is then \(2^\frac{-n}{2}\sum_x \ket{x} \otimes \ket{0^m}\).
  3. We apply \(U_f\), which is the unitary of \(f:\{0,1\}^n\rightarrow\{0,1\}^m\). This calculates the superposition over all possible values \(f(x)\) on the bottom wire. The resulting quantum state is \(2^\frac{-n}{2}\sum_x \ket{x,f(x)}\).
  4. To understand the algorithm better, we measure the bottom wire at this point. This will give us one random value \(f(x_0)\) for some \(x_0\). The top wire will then contain a superposition over all values \(x\) where \(f(x) = f(x_0)\). Since \(f\) is known to be \(t\)-periodic, we know, that \(f(x) = f(x_0)\) iff \(x \equiv x_0 \bmod t\). This means, that the resulting quantum state on the top wire is periodic and can be written as \(\frac{\sqrt{t}}{\sqrt{2^n}} \sum_{x\equiv x_0 \bmod t} \ket{x} \otimes \ket{f(x_0)}\). For simplicity we assume, that \(t \mid 2^n\) holds.
  5. We apply the Discrete Fourier Transform on the top wire. This will “analyze” the top wire for the period and output a vector with entries at multiples of \(\frac{2^n}{t}\). For simplicity we still assume, that \(t \mid 2^n\) holds.
  6. We measure the top wire and get one random multiple of \(\frac{2^n}{t}\), which we can denote as \(a\cdot\frac{2^n}{t}\)

After some post-processing, this gives us \(t\).

3.1.1 Factoring Integers

If we want to factor \(M\), we would pick a random \(a\) relatively prime to \(M\). We then use Shor to compute \(r :=\) ord \(a \mod M\). This means it is the smallest \(r > 0\) such that \(a^r \equiv 1 \mod M\). We can do this by computing the period of the function that maps \(x\) to \(a^x \mod M\). For an even \(r\), we can now say that \((a^{\frac{r}{2}+1})(a^{\frac{r}{2}-1})\equiv a^r -1 \equiv 0 (\mod M)\). It follows, that this product is a multiple of \(M\). Every prime factor of \(M\) is in one of the terms. If we are lucky, and not all factors are in the same term, \(gcd(a^{\frac{r}{2}+1},M)\) is a nontrivial factor of \(M\). In a typical crypto case, where \(M\) has only two factors, we are done.

Shor thus factors integers in \(O(\lvert M\rvert^3)\). This is fast enough to practically break RSA.

3.2 Grover’s algorithm

Assume we are given a function \(f: \{0,1\}^n\rightarrow\{0,1\}\), which maps \(f(x_0)\) to 1 and everything else to 0. Our goal here is to find \(x_0\). For this we need two unitaries, \(V_f\) and \(\operatorname{FLIP_*}\). \(V_f\) is defined as follows: \[ V_f \ket{x} = \begin{cases} -\ket{x} & \text{if } f(x) = 1\\ \ket{x} & \text{else} \end{cases} \] \(\operatorname{FLIP_*}\) leaves the uniform superposition untouched, and flips the sign of everything that is orthogonal to it.

The circuit for Grover’s algorithm

The algorithm works as follows:

  1. We start with a \(\ket{0}\) entry on every qubit.
  2. 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{*}\).
  3. We apply the unitary \(V_f\).
  4. We apply the unitary \(\operatorname{FLIP}_*\).
  5. We repeat steps 3 and 4 \(t\) times, and then do a measurement.

Visualization of Grover

We are searching for \(\ket{x_0}\), here called the good state. The state orthogonal to it we call the bad state.Our original state when starting the computation is close to the bad state. Every application of Grover rotates our state \(2\theta\) towards the goal state. After \(t\approx \frac{\pi}{4}\sqrt{2^n}\) iterations we have rotated by \(t*2\theta\approx\frac{\pi}{2}\approx\ket{x_0}\). Therefore the final measurement gives us \(x_0\).

Grover runs in \(O(\sqrt{2^n})\) evaluations of f, while the classically best algorithm takes \(O(2^n)\) time.

With some tweaks, we can make our algorithm work even if there are multiple \(x_0\). Generally, if our number of \(x_0\)s is \(T\) our runtime is \(\approx\sqrt{\frac{2^n}{T}}\). This is again the root of the classical runtime. This algorithm is useful for attacking cryptographic systems, making the search for a 128-bit key take \(\approx 2^64\) instead of the classical \(\approx 2^128\).