Archive for July 8th, 2010
I’d learnt Shor’s algorithm in a course a few years ago, but (as usual) forgot all about it.
Yesterday I reread it from the Algorithms textbook of Dasgupta, Papadimitriou, and Vazirani, only because someone claimed that their Chapter 10 on Quantum algorithms was incomprehensible, so here is a very vague sketch of it before I forget it again. (For a popular account, which Peter Shor called “the best job of explaining quantum computing to the man on the street that I’ve seen”, see Scott Aaronson’s post.)
The quantum magic in Shor’s algorithm, the part that uses something unique to quantum computation, is simply the following fact: a quantum computer can perform the quantum Fourier transform in O(log2 N) time.
That is, given a “superposition” , in O(log2N) steps the quantum fourier-magic-thing produces the superposition with . Of course, it just produces this superposition and does not output it; if we try to measure this we’d get only one of the states, specifically with probability .
(I will not write here how this QFT works. It uses the Hadamard gate etc., and roughly, what would be two recursive calls in the usual FFT can be done with just one operation here.)
All the other ideas are classical (i.e. non-quantum).
2. Fourier transform of periodic vectors
Suppose is some factor of . It can be proved with some straightforward calculation that if (viewed as a vector/sequence) is periodic with period , with the only nonzero coefficients being , then its Fourier transform is also periodic with period — the only nonzero coefficients are .
The point is that if we “measure” this, then we get one of the multiples of at random, so by taking a few measurements, we can figure out and therefore .
3. Factoring reduces to order-finding
We can see from number theory (use the Chinese remainder theorem) that if N is composite (etc.), then with probability at least 1/2, a random x modulo N has an even order r (i.e. the smallest positive integer such that ) such that is a nontrivial square root of 1 mod N. So if we can find the order , then we have such that so with neither factor being 0, so we get a factor of . So all we need to be able to do is find the order.
Modulo , pick any and consider the function . If is the order of mod then the function is periodic with period . The algorithm runs as follows:
- First, make a superposition normalised. (Think of the as two quantum “registers”.) (This is made by starting with just and taking its Fourier transform!)
- Now “compute” (for some random ) on it. This gives the superposition .
- Then measure the second register. This gives a random value from the second register, but more importantly, it make the first register be a superposition of only those values that are compatible with this value — therefore, periodic with period .
- Now do the Fourier transform on the first and measure it, so we get a random multiple of .
Doing all this the right number of times with the right constants does it. I’ve cheated in all this, because obviously the N we’re trying to factor is not a power of 2, but that can be taken care of.
I think Shor’s big idea (over Simon’s algorithm for period-finding) was in coming up with this function f whose period would give the factors of N. But I may be wrong.