---

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.

Integer factorization

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) = 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 = 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 as follows for an unknown arbitrary value of $x_0$:

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

Due to entanglement, the unmeasured (top $q$) qubits change state into a superposition:

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

Clearly, there is a periodic structure here, but we cannot measure it directly, because we do not know the value of $x_0$, which, to make matters worse, changes every time we run the algorithm. This is where the QFT comes in, which outputs the following state:

$$\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}$$

Where $\omega_Q$ is a $Q$th root of unity. Measuring this state yields a $\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, this implies that we did not need to perform the measurement of $f(x)$ earlier! This makes 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$. Assuming $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 a random integer coprime to $N$, meaning $\gcd(a, N) = 1$. 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}$$

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, 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.

---