1. Find a property that is shared by all of possible answers which can be compared.
For Shor's algorithm it is the period of Prime factors.
x mod N, x2 mod N, x3 mod N, x4 mod N, … (discovered by Euler in 1760)
we could create an enormous quantum superposition over all the numbers in our sequence: x mod N, x2 mod N, x3 mod N, etc. Then maybe there’s some quantum operation we could perform on that superposition that would reveal the period.
we’re no longer trying to find a needle in an exponentially-large haystack, something we know is hard even for a quantum computer. Instead, we’re now trying to find the period of a sequence, which is a global property of all the numbers in the sequence taken together.
3. if we want to get this period-finding idea to work, we’ll have to answer two questions:
A. Using a quantum computer, can we quickly create a superposition over x mod N, x2 mod N, x3 mod N, and so on?
We can certainly create a superposition over all integers r, from 1 up to N or so. The trouble is, given an r, how do we quickly compute xr mod N?
Use repeated squaring
B. Supposing we did create such a superposition, how would we figure out the period?
To get the period out, Shor uses something called the quantum Fourier transform, or QFT.
The QFT converts the property to linear amounts (vectors, lines with length and direction) which can be compared. In a quantum computer the amounts interfere destructively and cancel each other out, which leaves the right answer if the property does differentiate the right answer.
Geordie Rose talks about his take on Shor's Algorithm and why he think it is not the most important
A tutorial on Fourier Transforms
A guide to online tutorials on Fourier transforms with star ratings