---

Categories: Algorithms, Cryptography, Quantum information.

Shor’s algorithm

Shor’s algorithm was the first truly useful quantum algorithm. It can solve important problems, most notably integer factorization, much more efficiently than any classical algorithm. It weakens widely-used cryptographic schemes, such as RSA and Diffie-Hellman.

In essence, Shor’s algorithm’s revolutionary achievement is that it can efficiently find the periods $s_1, ..., s_A$ of a function $f(x_1, ..., x_A)$ on a discrete finite field, where:

$$\begin{aligned} f(x_1, ..., x_A) = f(x_1 + s_1, ..., x_A + s_A) \end{aligned}$$

This is a so-called hidden subgroup problem for a finite Abelian group. With minimal modifications, Shor’s algorithm can solve practically every such problem.

Originally, Shor’s algorithm was designed to factorize an integer $N$. For reasons explained later, this means our goal is to find the period $s$ of the modular exponentiation function $f$:

$$\begin{aligned} f(x) \equiv a^x \bmod N \end{aligned}$$

For a given $a$ and $N$. The period $s$ is the smallest integer satisfying $f(x) = f(x+s)$. To do this, the following $2q$-qubit quantum circuit is used, with $q$ chosen so that $N^2 \le 2^q < 2 N^2$:

Here, $\mathrm{QFT}_q$ refers to the $q$-qubit quantum Fourier transform, and the oracle $U_f$ calculates $f(x)$ for predetermined values of $a$ and $N$. It is an XOR oracle, working as follows:

$$\begin{aligned} \Ket{x} \Ket{y} \quad \to \boxed{U_f(a, N)} \to \quad \Ket{x} \Ket{y \oplus f(x)} \end{aligned}$$

Execution starts by applying the Hadamard gate $H$ to the first $q$ qubits, yielding:

$$\begin{aligned} \Ket{0}^{\otimes q} \Ket{0}^{\otimes q} \quad \to \boxed{H^{\otimes q}} \to \quad \Ket{+}^{\otimes q} \Ket{0}^{\otimes q} = \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{0}^{\otimes q} \end{aligned}$$

Where $Q \equiv 2^q$, and $\Ket{x}$ is the computational basis state $\Ket{x_1} \cdots \Ket{x_q}$. Moving on to $U_f$:

$$\begin{aligned} \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{0}^{\otimes q} \quad \to \boxed{U_f(a, N)} \to \quad \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \Ket{x} \Ket{f(x)} \end{aligned}$$

Then we measure $f(x)$, causing it collapse for an unknown arbitrary value of $x_0$. Let $L$ be number of periods that fit in the available qubits, then we know that:

$$\begin{aligned} f(x_0) = f(x_0 + s) = \cdots = f(x_0 + \ell s) = \cdots = f(x_0 + (L-1) s) \end{aligned}$$

Due to entanglement, the unmeasured (top $q$) qubits change state, so we now have:

$$\begin{aligned} \frac{1}{\sqrt{L}} \sum_{\ell = 0}^{L - 1} \Ket{x_0 + \ell s} \Ket{f(x_0)} \end{aligned}$$

Clearly, there is a periodic structure here, but we cannot measure it directly, since we do not know the value of $x_0$, which, to make matters worse, changes every time we run the algorithm! But now we apply the QFT, which outputs the state below, where $\omega_Q$ is a $Q$th root of unity. From now on, we no longer write the measured qubits $\Ket{f(x_0)}$, leaving:

$$\begin{aligned} \frac{1}{\sqrt{QL}} \sum_{k = 0}^{Q - 1} \bigg( \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg) \Ket{k} \end{aligned}$$

Measuring this state causes a collapse into some $\Ket{k}$ with a probability $P(k)$:

$$\begin{aligned} P(k) = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg|^2 = \frac{1}{QL} \bigg| \omega_Q^{x_0 k} \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 \end{aligned}$$

The last step holds because $|\omega_Q| = 1$. Surprisingly, $x_0$ has disappeared, implying that we did not need to perform the measurement of $f(x)$ earlier! This makes some sense: the period $s$ does not depend on $x_0$, so why would we need an implicit $x_0$ to determine $s$?

So, what does the above probability $P(k)$ work out to? There are two cases:

$$\begin{alignedat}{2} &\mathrm{if} \: \omega_Q^{sk} = 1: \qquad &&P(k) = \frac{1}{QL} |L|^2 = \frac{L}{Q} \\ &\mathrm{if} \: \omega_Q^{sk} \neq 1: \qquad &&P(k) = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 \end{alignedat}$$

Where the latter case was evaluated as a geometric series. The condition $\omega_Q^{sk}\!=\!1$ is equivalent to asking if $sk$ is a multiple of $Q$. i.e. if $sk = cQ$, for an integer $c$.

Recall that $L$ is the number of times that $s$ fits in $Q$, so $L\!=\!\lfloor Q / s \rfloor$. For now, let us assume that $Q/s$ is an integer, then $L\!=\!Q/s$ and $Q\!=\!s L$, which tells us that $\omega_Q^{sk}\!=\!\omega_{s L}^{s k}\!=\!\omega_L^k$. This implies that if $k$ is a multiple of $L$ (i.e. $k\!=\!c L$), then $\omega_L^k\!=\!1$, so $P(k) = L / Q$, which is exactly what we got earlier!

In other words, the condition $\omega_Q^{sk}\!=\!1$ is equivalent to $Q/s$ being an integer. In that case, we have that $Q\!=\!sL$, which we substitute into $P(k)$ from earlier:

$$\begin{aligned} \mathrm{if} \: (Q/s) \in \mathbb{N}: \qquad P(k) = \frac{L}{Q} = \frac{1}{s} \end{aligned}$$

And because $k$ is a multiple of $L$, and $L$ fits $s$ times in $Q$, there must be exactly $s$ values of $k$ that satisfy $P(k) = 1/s$. Therefore the probability of all other $k$-values is zero! This becomes clearer when you look at the sum used to calculate $P(k)$: if $Q\!=\!sL$, then it sums $\omega_L^{\ell k}$ over $\ell$, leading to perfect destructive interference for the “bad” $k$-values, leaving only the “good” ones.

So, to summarize: if $Q/s$ is an integer, then measuring only yields $k$-values that are multiples of $L\!=\!Q/s$. Running Shor’s algorithm several times then gives several $k$-values separated by $L$. That tells us what $L$ is, and we already know $Q$, so we finally find the period $s = Q/L$.

That begs the question: what if $Q/s$ is not an integer? We cannot check this, since $s$ is unknown! Instead, we rewrite the probability $P(k)$ as follows:

$$\begin{aligned} \mathrm{if} \: (Q/s) \not\in \mathbb{N}: \qquad P(k) = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 = \frac{1}{QL} \Bigg| \frac{\sin(\pi s k L / Q)}{\sin(\pi s k / Q)} \Bigg|^2 \end{aligned}$$

This function peaks if $s k$ is close to a multiple of $Q$, i.e. $s k \approx c Q$, which we rearrange:

$$\begin{aligned} \frac{k}{Q} \approx \frac{c}{s} \end{aligned}$$

We know the left-hand side, and, from the definition of $f(x)$, clearly $s \le N$. We chose $Q \sim N^2$, so $s$ is quite small, and consequently $c$ is too, since $k < Q$.

In other words, $c/s$ is a “simple” fraction, so our goal is to find a “simple” fraction that is close to the “complicated” fraction $k/Q$. For example, if $k/Q\!=\!0.332$, then probably $c/s\!=\!1/3$.

This can be done rigorously using the continued fractions algorithm: write $k/Q$ as a continued fraction, until the non-integer part of the denominator becomes small enough. This part is then neglected, and we calculate whatever is left, to get an estimate of $c/s$.

Of course, $P(k)$ is a probability distribution, so even though the odds are in our favour, we might occasionally measure a misleading $k$-value. Running Shor’s algorithm several times “fixes” this.

So, to summarize: if $Q/s$ is not an integer, the measured $k$-values are generally close to $c Q / s$ for an integer $c$. By approximating $k/Q$ using the continued fraction algorithm, we estimate $c/s$. Repeating this procedure gives several values of $c/s$, such that $s$ is easy to deduce by taking the least common multiple of the denominators.

In any case, once we think we have $s$, we can easily verify that $f(x)\!=\!f(x\!+\!s)$. Whether $s$ is the smallest such integer depends on how lucky we are, but fortunately, for most applications of this algorithm, that does not actually matter, and usually we find the smallest $s$ anyway.

You typically need to repeat the algorithm $\mathcal{O}(\log{q})$ times, and the QFT is $\mathcal{O}(q^2)$. The bottleneck is modular exponentiation $f$, which is $\mathcal{O}(q^2 (\log{q}) \log{\log{q}})$ and therefore worse than the QFT, yielding a total complexity of $\mathcal{O}(q^2 (\log{q})^2 \log{\log{q}})$.

OK, but what does $s$ have to do with factorizing integers? Well, recall that $f$ is given by:

$$\begin{aligned} f(x) = a^x \bmod N \end{aligned}$$

$N$ is the number to factorize, and $a$ is an integer that we can choose. For this to work, we should pick an $a$ that is coprime to $N$, meaning $\gcd(a, N) = 1$. Then the fact that $s$ is the period of $f$ for a certain $a$-value implies that:

$$\begin{aligned} a^x = a^{x + s} \bmod N \quad \implies \quad 1 = a^s \bmod N \end{aligned}$$

For now, suppose that $s$ is even. In that case, we can rewrite the above equation as follows:

$$\begin{aligned} (a^{s/2})^2 - 1 = 0 \bmod N \end{aligned}$$

In other words, $(a^{s/2})^2 \!-\! 1$ is a multiple of $N$. We then use that $(a\!-\!b) (a\!+\!b) = a^2\!-\!b^2$:

$$\begin{aligned} \big( a^{s/2} - 1 \big) \big( a^{s/2} + 1 \big) = 0 \bmod N \end{aligned}$$

Because $s$ is even by assumption (for now), the two factors on the left are integers, and as just mentioned, their product is a multiple of $N$. Then we only need to calculate:

$$\begin{aligned} \gcd\!\big( a^{s/2}\!-\!1, N \big) > 1 \quad\:\: \mathrm{and} \quad\:\: \gcd\!\big( a^{s/2}\!+\!1, N \big) > 1 \end{aligned}$$

And there we have the factors of $N$! The $\gcd$ can be calculated efficiently in $\mathcal{O}(q^2)$ time.

But what if $s$ is odd? No problem, then we just choose a new $a$ coprime to $N$, and keep repeating Shor’s algorithm until we do find an even $s$. We do the same if $a^{s/2}\!\pm\!1$ is itself a multiple of $N$.

References

1. J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
2. S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.

---