Shor's algorithm

Shor’s algorithm

1. Quantum

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(log² N) time.

That is, given a “superposition” $|\boldsymbol\alpha\rangle = \sum_{j=0}^{N-1}\alpha_j |j\rangle$ , in O(log²N) steps the quantum fourier-magic-thing produces the superposition $|\boldsymbol\beta\rangle = \sum_{j=0}^{N-1} \beta_j |j\rangle$ with $\beta_j = \frac{1}{\sqrt{N}} \sum_{l=0}^{N-1} \omega^{jl}\alpha_l$ . 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 $N$ states, specifically $|j\rangle$ with probability $|\beta_j|^2$ .

(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 $k$ is some factor of $N$ . It can be proved with some straightforward calculation that if $|\boldsymbol\alpha\rangle$ (viewed as a vector/sequence) is periodic with period $k$ , with the only nonzero coefficients being $\alpha_l, \alpha_{l+k}, \alpha_{l+2k}, \dots$ , then its Fourier transform is also periodic with period $N/k$ — the only nonzero coefficients are $\beta_0, \beta_{N/k}, \beta_{2N/k}, \dots$ .

The point is that if we “measure” this, then we get one of the multiples of $N/k$ at random, so by taking a few measurements, we can figure out $N/k$ and therefore $k$ .

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 $x^r = 1 \mod N$ ) such that $x^{r/2}$ is a nontrivial square root of 1 mod N. So if we can find the order $r$ , then we have $y$ such that $y^2 = 1\mod N$ so $(y-1)(y+1) = 0\mod N$ with neither factor being 0, so we get a factor of $N$ . So all we need to be able to do is find the order.

Modulo $N$ , pick any $x$ and consider the function $f(k) = x^k \bmod N$ . If $r$ is the order of $x$ mod $N$ then the function is periodic with period $r$ . The algorithm runs as follows:

First, make a superposition $\sum_{j=0}^{N-1} |j, 0\rangle$ normalised. (Think of the $|\cdot,\cdot\rangle$ as two quantum “registers”.) (This is made by starting with just $|0,0\rangle$ and taking its Fourier transform!)
Now “compute” $f$ (for some random $x$ ) on it. This gives the superposition $\sum_{j=0}^{N-1} |j, f(j)\rangle$ .
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 $r$ .
Now do the Fourier transform on the first and measure it, so we get a random multiple of $N/r$ .

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.

About these ads

Written by S

Thu, 2010-07-08 at 04:22:52 +05:30

Posted in mathematics

S	M	T	W	T	F	S
« Jun				Aug »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

The Lumber Room

Shor’s algorithm

1. Quantum

2. Fourier transform of periodic vectors

3. Factoring reduces to order-finding

Leave a Reply Cancel reply

Pages

Archives

Tags

Meta

Blog Stats

Follow “The Lumber Room”