Shor’s algorithm

Fix an odd composite integer N that is not the power of a prime. Shor’s algorithm is a probabilistic algorithm used to find factors of N. It is the following.

1. Let a<N. If \gcd(a,N)\neq 1, then \gcd(a,N) is a nontrivial factor of N.

2. If \gcd(a,N)=1, then a\in(\mathbf{Z}/N\mathbf{Z})^\times, so a has finite order r|\phi(N) – finding this order is the part of the algorithm that utilizes quantum computers. If r is odd or a^{r/2}\equiv -1\bmod N, restart.

3. Else, \gcd(a^{r/2}\pm 1,N) are nontrivial factors of N.

Suppose a<N and \gcd(a,N) = 1, with finite even order r|\phi(N) and a^{r/2}\equiv -1\bmod N. Define b = a^{r/2}\bmod N; then b is a square root of 1 in (\mathbf{Z}/N\mathbf{Z})^\times, distinct from 1 (else the order of a would be r/2). We claim that \gcd(b-1,N) = \gcd(a^{r/2}\pm 1,N) are nontrivial factors of N.

To see this, suppose otherwise. If \gcd(b-1,N) = N, then N|(b-1), i.e., b\equiv 1\bmod N, which is absurd. If \gcd(b-1,N) = 1, then there are x and y such that x(b-1) + yN = 1. Because b^2 - 1 = a^r - 1\equiv 0\bmod N, and b^2-1 = (b+1)(b-1), we will multiply each side by b+1, to get (b^2 - 1)x + yN(b+1) = b+1. Now, N|(b^2-1), so N|(b+1), i.e., b\equiv -1\bmod N, but this is absurd by our hypotheses!

Finding the order of an a\in(\mathbf{Z}/N\mathbf{Z})^\times is the quantum part of Shor’s algorithm. (Side note: I guess for small N, one could run through all divisors of \phi(\phi(N)) to find the order of a fixed a\in(\mathbf{Z}/N\mathbf{Z})^\times.) I’m going to assume a knowledge of a bras and kets, unitary operators, and qubits (a quantum register is then just a collection of qubits).

Let q be such that N^2\leq q< 2N^2. Create a quantum register with the first register having enough qubits to store integers as large as q-1, and the second register having enough qubits to store integers as large as N-1. Let the first register have an equally weighted superposition of 0,\cdots,q-1, and the second register be full of zeros. The state of the quantum system is then given by:


Apply the transformation f(x) = a^x\bmod N for each x in the first register; this gives the following formula for the state of the quantum system:

\displaystyle\frac{1}{\sqrt{q}}\sum^{q-1}_{x=0}|x,a^x\bmod N\rangle.

The advantage of using quantum computers in this part of the algorithm becomes spectacularly apparent here: because we are using a quantum computer, the action of a function f(x) on a state, taking \sum_x|x,0\rangle\mapsto\sum_x|x,f(x)\rangle, yields the values f(x) for all x, in a single step! This incredible advantage will be used multiple times in this (and other) algorithm(s). (The problem in doing this, though, is that we cannot obtain all f(x) from \sum_x|x,f(x)\rangle at once, because this requires a measurement of x — but when this happens, the value of f(x) becomes fixed.)

The interesting part of this quantum subroutine are the following steps. Observe the second register to get some value k; this collapses the first register, and thus the quantum state, into:

\displaystyle\frac{1}{\sqrt{|G_k|}}\sum_{x\in G_k}|x,k\rangle.

Here G_k = \{x\in\mathbf{Z}/(q-1)\mathbf{Z}|a^x\bmod N = k\}. We now have to use something called the quantum Fourier transform, denoted \mathbf{U}_{FT}, acting as follows:

\displaystyle\mathbf{U}_{FT} |x\rangle = \frac{1}{\sqrt{q}}\sum_{n=0}^{q-1}|n\rangle e^{2\pi inx/q}

This is a unitary operator (as can be easily checked, remembering that \sum_n|n\rangle\langle n| = 1). Applying \mathbf{U}_{FT} to this quantum system gives:

\displaystyle\frac{1}{\sqrt{|G_k|}}\sum_{x\in G_k}\frac{1}{\sqrt{q}}\sum^{q-1}_{n=0}|n,k\rangle e^{2\pi i xn/q}.

Observing the first register now gives a value m. Taking the modulus squared:

\displaystyle\left|\frac{1}{\sqrt{|G_k|q}}\sum_{x\in G_k}e^{2\pi i xm/q}\right|^2 = \frac{1}{q|G_k|}\left|\sum_{x\in G_k}e^{2\pi i xm/q}\right|^2

We therefore need to evaluate the sum \sum_{x\in G_k}e^{2\pi i xm/q}:

\displaystyle\left|\sum_{x\in G_k}e^{2\pi i xm/q}\right|^2 = \left|\sum_{b}e^{2\pi i (x_0+rb)m/q}\right|^2 = \left|\sum_{b}e^{2\pi i rbm/q}\right|^2

Where x_0 = \min G_k. The higher the probability, the closer rm/q must be to an integer. Using continued fractions, we can find the best irreducible rational approximation p/s to m/q, where s<q. If a^x\bmod N = a^{x+s}\bmod N, we are done if s is even (i.e., the period r=s); else we can use multiples of s (and possibly double s) to find a candidate for r. Otherwise, we restart the quantum subroutine.

There are some possible problems with this algorithm, though, mainly because it is probabilistic, not deterministic. If the quantum Fourier transform gives 0, then we cannot proceed with our analysis. Sometimes the algorithm spits out 1 and N as factors of N, which is not useful at all. Larger q means a higher probability of finding the correct period. Regardless, though, this is a beautiful piece of knowledge, which also has implications for the “real world” (if quantum computers with a large enough number of qubits can be made). RSA, the public-key cryptography algorithm protecting our credit card information, is based off of the assumption that it is basically (computationally) impossible to factor large numbers. With a strong enough quantum computer, because of the efficiency of quantum computing, using Shor’s algorithm, one could defeat RSA!

As Peter Shor confirmed for me, this algorithm can be used to find the order of any element in a finite group (see here). There is also an important question called the “hidden subgroup problem” which uses an adaptation of Shor’s algorithm, that I might post about later.



One thought on “Shor’s algorithm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s