8 ms·
Shor, I’ll do it (2007)
- FartyMcFarter 4y agoI 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. There's a video featuring Peter Shor about the invention of this algorithm: https://www.youtube.com/watch?v=6qD9XElTpCE https://www.youtube.com/watch?v=6qD9XElTpCE
- H8crilA 4y agoHow 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.
- dandanua 4y agoNo, 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).
- Strilanc 4y agoThe 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]. 1: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor... 2: https://en.wikipedia.org/wiki/Tensor_network https://en.wikipedia.org/wiki/Tensor_network 3: https://en.wikipedia.org/wiki/Hadamard_transform https://en.wikipedia.org/wiki/Hadamard_transform 4: https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22Counting8%22%5D%2C%5B%22Chance8%22%5D%2C%5B%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%5D%2C%5B%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22H%22%5D%2C%5B%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22H%22%5D%2C%5B%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%82%E2%82%88%22%2C%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%5D%7D https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2... 5: https://algassert.com/2016/06/14/qft-by-multiply.html https://algassert.com/2016/06/14/qft-by-multiply.html
- jstanley 4y ago> 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.
- cwillu 4y agoThen you're talking about the complexity class PostBQP, rather than the class BQP. Postselection is ridiculously powerful, as you've noted.
- __ryan__ 4y agoIn 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.
- shagie 4y agoQuantum immortality is a neat thing ( https://en.wikipedia.org/wiki/Quantum_suicide_and_immortality https://en.wikipedia.org/wiki/Quantum_suicide_and_immortalit... ). I'd suggest the short story All the Myriad Ways by Larry Niven ( https://erenow.net/common/the-best-alternate-history-stories-of-the-20th-century/6.php https://erenow.net/common/the-best-alternate-history-stories... ) and the exceedingly long story Nangurz ol Arny Fgrcurafba (rot13 because it kind of is a spoiler).
- JadeNB 4y agoWhen discussing quantum immortality and sci-fi, one must also mention Greg Egan's early Quarantine (https://en.wikipedia.org/wiki/Quarantine_(Egan_novel) https://en.wikipedia.org/wiki/Quarantine_(Egan_novel)).
- eliben 4y agoI like how there's a comment by Peter Shor commending Scott on the article :-) Knowing Scott's blog, this is likely legit
- ryan-duve 4y agoIf 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: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY
- Eddy_Viscosity2 4y agoThis 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.
- FartyMcFarter 4y ago> and how many are needed According to this paper, one can use 2n+3 qubits to factor an integer with n bits: https://arxiv.org/abs/quant-ph/0205095 https://arxiv.org/abs/quant-ph/0205095 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.
- semi-extrinsic 4y agoIf 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.
- Strilanc 4y agoCounting 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]. 1: https://quantum-journal.org/papers/q-2021-04-15-433/ https://quantum-journal.org/papers/q-2021-04-15-433/
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- benreesman 4y agoSidebar: 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.
- carver 4y agoIs this the "uh, thing"? https://www.theatlantic.com/politics/archive/2015/01/the-blog-comment-that-achieved-an-internet-miracle/384539/ https://www.theatlantic.com/politics/archive/2015/01/the-blo...
- aorth 4y agoI think it was the doxxing against his will by NY Times. https://www.newyorker.com/culture/annals-of-inquiry/slate-star-codex-and-silicon-valleys-war-against-the-media https://www.newyorker.com/culture/annals-of-inquiry/slate-st... Edit: users pointed out this is a different Scott. My mistake!
- deleted 4y ago[deleted]
- Chinjut 4y agoThis is a different Scott.
- gonehome 4y agoYeah, 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.
- walnutclosefarm 4y agoCongratulations to Scott Aaronson for the must lucide explanation of Shor's algorithm for the merely mathematically literate, ever!
- omoikane 4y agoNear the bit that describes "repeated squaring", there is this formula (note the "http"): 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 http://www.scottaaronson.com/cgi-bin/mimetex.cgi?x^r%20=%203... 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.
- Sniffnoy 4y ago(2007)
- mikotodomo 4y agoWow. That such high end technical content is hosted on Wordpress really shows how battle tested and reliable it is.
- georgehm 4y ago> 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. I am curious to know about these tricks to recover p, q. Does anyone know?
- YetAnotherNick 4y agoYou 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.