I don't fully understand all the details, but even I can tell that this algorithm is beautiful.<p>Mixing together the concepts of modular sequences, periods, and Fourier transforms, plus doing this fast with computers that barely exist in order to find factors or numbers is just an amazing construction.<p>There's a video featuring Peter Shor about the invention of this algorithm: <a href="https://www.youtube.com/watch?v=6qD9XElTpCE" rel="nofollow">https://www.youtube.com/watch?v=6qD9XElTpCE</a>
> if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you)<p>But if you <i>do</i> think of it that way, why not just pick a random number using some quantum process, classically test whether or not it's a divisor of the number you're trying to factor, and kill yourself if it's not? In every universe where you survive (which, for sake of argument, are the only ones you care about) you find a factor on the first try.
If the part about the tack on the board under the clocks wasn't clear, and you're a visual learner, this video from 3Blue1Brown about the [classic] Fourier Transform might help clarify the relationship to periodicity:<p><a href="https://www.youtube.com/watch?v=spUNpyF58BY" rel="nofollow">https://www.youtube.com/watch?v=spUNpyF58BY</a>
Near the bit that describes "repeated squaring", there is this formula (note the "http"):
<a href="http://www.scottaaronson.com/cgi-bin/mimetex.cgi?x^r%20=%203^{14}%20=%203^{2^3+2^2+2^1}%20=%203^{2^3}%20\cdot%203^{2^2}%20\cdot%203^{2^1}%20=%20((3^2)^2)^2%20\cdot%20(3^2)^2%20\cdot%203^2" rel="nofollow">http://www.scottaaronson.com/cgi-bin/mimetex.cgi?x^r%20=%203...</a><p>Firefox doesn't want to load that due to mixed content (https page loading http), and also doesn't want to follow the 301 redirect to the https version. Chrome appears to follow the 301 redirect (or maybe lazy-images.js does something different) such that the page renders properly.
How does one implement the QFT? The same way as one would do FFT, but with quantum gates? I.e. taking O(n*log(n)) gates with two inputs and two outputs? I'm imagining that there's some sort of a vector of quantum (complex) amplitudes left after the exponentiation that needs to be transformed.
This was pretty good, though I would still like to know 'how' the quantum computer gets all those amplitude (and how many are needed) to interfere with each other to get the answer.
> And once we knew (p-1)(q-1), we could then use some more little tricks to recover p and q, the prime factors we wanted.<p>I am curious to know about these tricks to recover p, q. Does anyone know?
Sidebar: I absolutely adore Scott "I don't give a fuck anymore" Aaronson.<p>My personal aspirations to this kind of biting wit are futile and vain, but my admiration for it is even greater and some people can bring it off with style to spare, and ever since that uh, thing, Scott is just playing the ten minute guitar solo.<p>Into to Number Theory with periodicity and modular math might be stretching "nothing more than arithmetic" a bit, but fuck it, this is the best accessible discussion of Shor I've ever read and if there's any justice in the multiverse it will become the go-to link on the topic, which will mean that 10^500 laypeople will roll their eyes at the next 10^500 "quantum computers are the next step after digital computers" Aeon fluff pieces floating by.