Categories: Algorithms, Cryptography, Quantum information.

# Shor’s algorithm

Shor’s algorithms 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$$, in which case the goal is to find the period $$s$$ of the modular exponentiation function $$f$$ (for reasons explained later):

\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} \: \omega_Q^{sk} = \omega_L^k = 1: \qquad \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} %\mathrm{if} \: (Q/s) \not\in \mathbb{N}: \qquad \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$$.

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