11 Shor’s Algorithm
One of the best known quantum algorithm is Shor’s algorithm for finding the prime factors of an integer. It was developed by Peter Shor in 1994.
11.1 Reducing factoring to period finding
With the DFT, we have seen that we can use a unitary to find the period of a quantum state. Thus we hope that quantum circuits will be particularly good at problems related to periods. We now look into using period finding to factor integers. We first look at the definition of some problems:
Note that this definition of the factoring problem is a simplified version of the factoring problem, where \(N\) has only two distinct prime factors.
To start the reduction, we need a special case of the period finding problem called order finding:
Since the order finding problem is just the period finding problem for a specific \(f(x)\), we know that if we can solve the period finding problem within reasonable runtime, we can also solve the order finding problem within reasonable runtime. We now reduce the factoring problem to the order finding problem:
We have an integer \(N\) as an input for the factoring problem.
- Pick an \(a \in \{2, \dots, N-1\}\) relatively prime to \(N\).
- Compute the order of \(a\), so that \(r \coloneqq \operatorname{ord}_N a\) (Using an algorithm for the order finding problem with \(R \coloneqq N\) because \(\operatorname{ord}_N a \leq N\) always).
- If the order \(r\) is odd, restart at 1.
- Calculate \(x \coloneqq a^{\frac{r}{2}} + 1 \bmod N\) and \(y \coloneqq a^{\frac{r}{2}} - 1 \bmod N\).
- If \(\gcd(x,N) \in \{1,N\}\), we restart at 1.
- Return \(p = \gcd(x,N)\) and \(q = \frac{N}{\gcd(y,N)}\).
The output of the reduction are \(p,q\), such that \(pq = N\). This holds, since \[ xy = (a^{\frac{r}{2}}+1) (a^{\frac{r}{2}}-1) = a^r - 1 \equiv 1-1 = 0 \pmod N. \] This means that \(N \mid xy\) an therefore \(p \mid xy\) and \(q \mid xy\). From this it can be concluded that \(p \mid x\), \(q \mid y\), \(p \nmid y\) and \(q \nmid x\) which leads to \(\gcd(x,N) = p\). Or \(p\) and \(q\) swapped.
All in all this reduction shows, that if we have an oracle which can solve the period finding problem within reasonable runtime, we can also solve the factoring problem within reasonable runtime (since all other operations are classically fast to compute). Therefore, though factoring is the goal of this section, we focus on order finding now.
11.2 The quantum algorithm for period finding
We now look into an quantum algorithm that solves the period finding problem within reasonable runtime.
For the quantum circuit we need an \(f: \mathbb{Z} \rightarrow X\) which is \(r\)-periodic for some \(r\).
The quantum algorithm for period finding is shown in this figure:
Note that we evaluate \(f\) only on \(n\) bits, i.e. \(\{0, \dots, 2^n -1\} \subseteq \mathbb{Z}\). And we assume \(X \subseteq \{0, 1\}^m\) for the output.
The algorithm works as follows:
- We start with \(\ket{\psi_1} = \ket{0^n} \otimes \ket{0^m}\).
- We bring the top wire into the superposition over all entries. The quantum state is then \(\ket{\psi_2} = G \cdot \sum_{x \in \{0,\dots,2^n-1\}} \ket{x} \otimes \ket{0^m}\) with the constant \(G \coloneqq 2^\frac{-n}{2}\).
- 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 \(\ket{\psi_3} = G \cdot \sum_{x \in \{0,\dots,2^n-1\}} \ket{x,f(x)}\).
- To understand the algorithm better, we measure the bottom wire at this point. This will give us one random value \(y = 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 \(r\)-periodic, we know, that \(f(x) = f(x_0)\) iff \(x \equiv x_0 \bmod r\). This means, that the resulting quantum state on the top wire is periodic. So the complete quantum state is \(\ket{\psi_4} = C \cdot \sum_{x\equiv x_0 \bmod r} \ket{x} \otimes \ket{f(x_0)}\) with the constant \(C = \frac{\sqrt{r}}{\sqrt{2^n}}\). (Assuming \(r |2^n\))
- We apply the Discrete Fourier Transform on the top wire. This will “analyze” the top wire for the period and output a vector with non-zero entries at multiples of \(\frac{2^n}{r}\) as seen in Theorem 10.1. (Assuming \(r |2^n\))
- We measure the top wire and get one random multiple of \(\frac{2^n}{r}\), which we can denote as \(c = a \cdot \frac{2^n}{r}\) for some \(a\).
Since we get a multiple of \(\frac{2^n}{r}\) on each run, we can simply run the algorithm multiple times to get different multiples and then compute \(\frac{2^n}{r}\) by taking the gcd of those multiples. From that we compute \(r\). Unfortunately this only works because we assumed \(r \mid 2^n\). Since this does usually not hold, we only get approximate multiples of \(\frac{2^n}{r}\) (which is not even an integer) and thus we need a more complex post processing which we discuss in the following section.
11.3 Post processing
So far we have seen a quantum algorithm for finding an approximate multiple of the period \(r\) of a function. We now need a final step to find \(r\). For this, we need to add one condition to the circuit. We require \(n \geq 2 \log R\).
We start with the following theorem:
Note that \(\frac{1}{\log\log r}\) decreases very slowly. For most practical input sizes, the probability will be \(\approx \frac{1}{3}\).
We assume that the theorem holds for our outcome \(c\) of the second measurement (if that is not the case, our result will be wrong and we can just run the quantum algorithm again to get a different outcome) and \(R\) is the upper bound on \(r\):
Then there exists an integer \(d\) such that: \[ \begin{aligned} \lvert rc - d2^n \rvert &\leq \frac{r}{2} && \text{// from (*)} \\ \text{Hence:} \quad \left\lvert \frac{c}{2^n} - \frac{d}{r} \right\rvert &\leq \frac{1}{2^{n+1}} && \text{// divide by } r \cdot 2^n \end{aligned} \] The fraction \(\varphi \coloneqq \frac{c}{2^n}\) is known, but the fraction \(\frac{d}{r}\) is unknown. All we know is that it is a fraction and that its denominator is \(\leq R\). Thus the goal is to find such a fraction \(\frac{1}{2^{n+1}}\)-close to \(\varphi\).
For this we use another theorem:
This theorem uses the “convergent of a continued fraction expansion”. A continued fraction expansion of a positive number \(t\) is the number rewritten as a fraction in the form
\[ t = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \dots}}} \]
where \(a_i \geq 0\) always has to be the biggest possible integer and we stop if \(\dots\) becomes \(0\). We call \([a_0; a_1, a_2, a_3, \dots]\) the continued expansion of \(t\). The expansion is finite iff t is rational. For a given continued expansion, a prefix \([a_0; a_1, \dots, a_i]\) is called a convergent. So Theorem 11.3 means that writing this convergent as a normal fraction will give us an approximation of the number \(t\).
Using Theorem 11.3 (with \(\varphi \coloneqq \frac{c}{2^n}\) and \(L \coloneqq 2^n\)) we can find \(\frac{d}{r}\) and from this \(r\) which is the period of our function using the following steps:
For each convergent \(\gamma\) of \(\varphi\) do the following:
- Compute \(\gamma\) as fraction \(\frac{d}{r}\).
- If \(r \leq 2^n\) and this \(\frac{d}{r}\) is \(\frac{1}{2^{n+1}}\)-close to \(\frac{c}{2^n}\): Return \(r\).
- Continue from 1 with next convergent.
Note: It can happen, that the resulting fraction does not have the right \(r\) in the denominator, because \(\frac{d}{r}\) was simplified (if numerator and denominator shared a common factor). But the probability of this happening is sufficiently small and already included in the probability in Theorem 11.2.
This completes the postprocessing of Shor’s algorithm.