Fix an odd composite integer that is not the power of a prime. Shor’s algorithm is a probabilistic algorithm used to find factors of . It is the following.
1. Let . If , then is a nontrivial factor of .
2. If , then , so has finite order – finding this order is the part of the algorithm that utilizes quantum computers. If is odd or , restart.
3. Else, are nontrivial factors of .
Suppose and , with finite even order and . Define ; then is a square root of in , distinct from (else the order of would be ). We claim that are nontrivial factors of .
To see this, suppose otherwise. If , then , i.e., , which is absurd. If , then there are and such that . Because , and , we will multiply each side by , to get . Now, , so , i.e., , but this is absurd by our hypotheses!
Finding the order of an is the quantum part of Shor’s algorithm. (Side note: I guess for small , one could run through all divisors of to find the order of a fixed .) 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 be such that . Create a quantum register with the first register having enough qubits to store integers as large as , and the second register having enough qubits to store integers as large as . Let the first register have an equally weighted superposition of , and the second register be full of zeros. The state of the quantum system is then given by:
Apply the transformation for each in the first register; this gives the following formula for the state of the quantum system:
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 on a state, taking , yields the values for all , 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 from at once, because this requires a measurement of — but when this happens, the value of becomes fixed.)
The interesting part of this quantum subroutine are the following steps. Observe the second register to get some value ; this collapses the first register, and thus the quantum state, into:
Here . We now have to use something called the quantum Fourier transform, denoted , acting as follows:
This is a unitary operator (as can be easily checked, remembering that ). Applying to this quantum system gives:
Observing the first register now gives a value . Taking the modulus squared:
We therefore need to evaluate the sum :
Where . The higher the probability, the closer must be to an integer. Using continued fractions, we can find the best irreducible rational approximation to , where . If , we are done if is even (i.e., the period ); else we can use multiples of (and possibly double ) to find a candidate for . 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 , then we cannot proceed with our analysis. Sometimes the algorithm spits out and as factors of , which is not useful at all. Larger 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.