Shor's algorithm

Shor's algorithm is a quantum algorithm for factoring in polynomial time. For sources, I am using this Qiskit tutorial and Wikipedia.

I'm mostly interested in the quantum part of the algorithm, so instead I will take as a starting point the following problem. Let $N$ be some modulus, and $a \in (\mathbb{Z}/N\mathbb{Z})^\times$ (i.e. $a, N$ must be coprime). We wish to compute the (multiplicative) order of $a$ in this group, i.e. the smallest $r > 0$ such that $a^r \equiv 1 \pmod{N}$.

First, let's forget the fact that we have to use qubits and pretend we can produce an $N$-ary quantum bit, e.g. when $N = 2^n$ this is just $n$ qubits. That is, suppose we have a basis for our quantum system:

$\lvert 0 \rangle = \lvert 0^n \rangle, \; \lvert 1 \rangle = \lvert 0^{n-1} 1 \rangle, \ldots, \; \lvert N-1 \rangle = \lvert 1^n \rangle.$
Implicitly, $\lvert m \rangle$ is a representative for $m \in \mathbb{Z}/N\mathbb{Z}$. We define an operator $U_a$ on this system
$U_a\lvert m \rangle = \lvert am \rangle.$
This is a permutation matrix, so it is unitary. In practice we need to think about how to implement the set-up above, i.e. to represent $\mathbb{Z}/N\mathbb{Z}$ using qubits and the operator $U_a$ using quantum gates. This is a completely classical algorithm, and it is known that classical algorithms can be implemented using quantum gates, so we will not address this directly.

Let $r$ be the period of $a$; by construction, $U_a^r = \mathbb{I}$, so all eigenvalues are $r$th roots of unity. For convenience, let $\omega = e^{2 \pi i / r}$. Some interesting eigenvectors and eigenvalues for this operator are for various $s \in \mathbb{Z}/r\mathbb{Z}$:

$v_s := \displaystyle \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1} \omega^{-ks} \lvert a^k \rangle, \;\;\;\;\;\;\;\;\;\; \lambda_s = \omega^s.$
The renormalized sum, over $s = 0, \ldots, r-1$, of the above eigenvectors is $\lvert 1 \rangle$, i.e. we have an eigenvector decomposition
$\lvert 1 \rangle = \displaystyle \frac{1}{\sqrt{r}}(v_0 + v_1 + \cdots + v_{r-1}).$
We note in passing that the rest of the eigenvectors and eigenvalues are shifted from this one by various other elements of $\mathbb{Z}/N\mathbb{Z}$; we don't care about them.

Recall that phase estimation allowed us, given a unitary operator $U$ and an eigenvector, to extract its eigenvalue. We do not have an eigenvector. However, we do have $\lvert 1 \rangle$, which is a sum of eigenvectors with equal weights. Running phase estimation on this superposition amounts to doing so on one of the eigenvectors chosen randomly, say with eigenvalue $s/r$, and after iterating phase estimation our estimate will converge to one of these with high probability. In fact, this estimation allows us to pinpoint the precise fraction. First, we have a bound on $r$, i.e. $r \leq N-1$. Roughly, there are finitely many fractions of the form $s/r$ where $r \leq N-1$, so they should be distinguishable by intervals of some length, which turns out to be (inverse) quadratic in $N$. This is polynomial, but for computing runtime in $n$ we take the logarithm, so it is linear in $n$, which is good enough. The algorithm for computing the $s/r$ is the continued fractions algorithm.

Now, knowing one of the fractions $s/r$ only reveals $r$ when $\gcd(s, r) = 1$; otherwise it is some factor of $r$. We can keep track of the denominators appearing and take their least common multiple, and this will yield $r$ with probability exponentially approaching $1$.

Finally, it should be remarked that the algorithm works in $O(n^3)$ time. An accounting:

• We need to implement phase estimation circuit. This involves constructing the multiplication operators $U_a^{2^i}$ for $i = 0, 1, \ldots, n-1$, which is $O(n)$ operations of $O(n^2)$ and the QFT gate which is order $O(n^2)$. In total, we have $O(n^3)$.
• We need to do continued fractions, which is $O(n^3)$.