So I've been following along the EdX Quantum Computation course that's going on right now, and enjoying it a lot. I'm impressed how much Shor's algorithm actually consists of a number of distinct twists and turns. What you really want to do is factor a number n; and so you hunt around for a nontrivial square root s of 1 mod n, because knowing s2 = 1 mod n means (s+1)(s-1) = 0 mod n and you're a gcd away from factoring n. Ok, so maybe think of a number k less than n and do a bunch of iterated powers of k hoping to find an even number 2p such that k2p = 1 mod n, meaning that kp is the nontrivial square root of 1 that you wanted. And hey! We have a lemma that tells us that picking k at random actually gives us a substantial (≥ 1/2) chance of succeeding! Amazing. But doing all those iterated powers of k is still expensive, i.e. exponential in the number of bits of the the number we're factoring. But quantum computers (and only now does anything quantum come into play) we can do a fourier transform of the sequence of iterated powers without actually having to compute the whole sequence, uh, sequentially. And we can stochastically read off information about its period by sampling the wavefunction in frequency space. And, voila, we have factored a number in polynomial time.
Tags:
• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic