I don't fully understand all the details, but even I can tell that this algorithm is beautiful.
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.
> if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you)
But if you do 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.
This is thought provoking, but suffers from a fundamental flaw. Let’s play this out…now you’re alive and have Satoshi’s keys, but all of the would-be bidders and pumpers in your universe have killed themselves, value goes to zero.
I think you may have accidentally discovered the Quantum Bag Holder Paradox.
The algorithm generates a random permutation of its input using a quantum source of entropy, checks if the list is sorted, and, if it is not, destroys the universe. Assuming that the many-worlds interpretation holds, the use of this algorithm will result in at least one surviving universe where the input was successfully sorted in O(n) time.
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.
What’s more likely, randomly guessing a prime factor of a giant number, or miraculously surviving and being permanently incapacitated? Or being interrupted, saved by modern medicine, bitten by a black widow immediately after getting it right…
You have to think that the odds really aren’t in your favor there.
For the winner (survivor) it doesn’t matter whether their “clones” in the other branches kill themselves, so why plan that in the first place? Also, the losers will probably prefer to not kill themselves, despite not getting lucky with their random number. So, the end result is the same as for any regular random guess.
Besides, infinite universes doesn't mean they'll collectively give you a mutually exclusive and exhaustive set like everyone is for some reason assuming. You could just as well get the same wrong number in all of them and kill yourself off permanently in the entire multiverse.
That's the nature of true randomness, if you set up a dice throw a million times they could just as well all come up as six. Incredibly unlikely, but possible.
Uhm, no. If you use quantum events, like radioactive decay, or the usual quantum particle experiments, or (supposedly) an app like Universe Splitter [0], you are guaranteed that the two different possible outcomes will both occur, according to quantum mechanics (if you believe in many-worlds, which is out premise). And then you can build up a binary number of arbitrary size from a sequence of such experiments. When you perform the experiment N times, there will be branches for all N-bit numbers. Or just use a QRNG service like [1] which does it for you.
What would happen (most likely) is that the wave function collapses and you find yourself in a universe where the random number you chose is not in fact a divisor and so, according to your algorithm, you now have to kill yourself. Probably, you don’t feel like doing it and so this algorithm does not work.
Isn't the multiverse where one version of you solves the problem and the other versions don't die strictly better than the version where they commit suicide? It's not like their experiences and memories get merged into the surviving copy. They're just gone, instead of not gone.
> 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?
All universes affect the probability of something occurring in each universe. That is how each universe contributes a bit of the Fourier offset which gives off the period in pretty much all universes.
Because finding the right divisor is so unlikely, you run a high risk of killing yourself in all universes. As Scott emphasizes, quantum computers don’t run possibilities in parallel!
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:
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.
No, QFT requires only O(log(n)^2) gates. It can be described by using a recursion. That is, QFT on 2^n values (n qubits) can be computed using QFT on 2^(n-1) values (n-1 qubits).
The QFT is the Cooley-Tukey FFT algorithm [1] expressed as a tensor network [2].
Cooley-Tukey has two main steps that are repeated recursively: bulk replacing a,b with a+b,a-b along bit boundaries, and applying twiddle factors. The bit-boundary a,b->a+b,a-b part becomes a Hadamard gate and the bit twiddling becomes a set of phase gates. Also there's some re-ordering but that's not the meat.
The actual quantum circuit: [4].
The quantum circuit is simple enough that it's a really solid mnemonic for remembering Cooley-Tukey, if you know how to translate it. There are also various ways to optimize the gate count or gate depth of this circuit, and these optimizations translate into changes to the classical FFT (though they are not always optimizations after translation) [5].
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.
If I understand your question on "how" correctly: all objects are interfering with each other at the quantum level all the time. But this effect is vanishingly tiny compared to e.g. thermal noise, we don't notice it at all. So the quantum computer isn't making the qubits interfere, that always happens, but it is working very hard to remove all other sources of noise such that only the quantum interactions remain.
Counting the number of amplitudes isn't really the right way to approach it. Individual amplitudes are basically irrelevant to a large quantum computation. It's all about large scale patterns in the amplitudes. Little exceptions to these patterns don't matter much.
Suppose I gave you the power to negate a billion amplitudes of your choosing in the middle of a 2000 bit quantum factoring computation. You might think this could destroy the computation, but a billion is way way way less than 2^2000 so the computation would for all intents and purposes be completely unaffected.
The things the quantum computers operate on are the qubits, not the amplitudes. Noise processes also operate on qubits, not amplitudes. It's the quantity and quality of the qubits that matter.
You can factor 2048 bit RSA integers if you have 20 million qubits each having a 0.1% gate error rate [1].
Those would be perfect qubits, if you use noisy qubits you'd need many more (maybe a factor of 1000x more), since quantum error correction imposes a lot of overhead.
You have pq(original number) and (p-1)(q-1). You could get (p + q) = pq+1-(p-1)(q-1). Then we know p and q satisfies x^2-(p+q)x+pq=0. You could solve this quadratic equation using quadratic formula to get p and q.
Sidebar: I absolutely adore Scott "I don't give a fuck anymore" Aaronson.
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.
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.
Yeah, though I wonder if Aaronson’s writing tone is somewhat influenced by Alexander’s. At least he reminded me of him by the end.
I’m pretty sure they all know/read each other - related communities/ideas.
PBS also has a (now discontinued) YouTube show called infinite series that did a decent overview of the algorithm and showed examples of a lot of the stuff described here.
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.
There's a video featuring Peter Shor about the invention of this algorithm: https://www.youtube.com/watch?v=6qD9XElTpCE