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)
2.
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
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.