[HN Gopher] Shor, I'll do it (2007)
___________________________________________________________________
Shor, I'll do it (2007)
Author : monort
Score : 285 points
Date : 2022-07-31 09:38 UTC (13 hours ago)
(HTM) web link (scottaaronson.blog)
(TXT) w3m dump (scottaaronson.blog)
| Eddy_Viscosity2 wrote:
| 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.
| FartyMcFarter wrote:
| > 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
|
| 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.
| Strilanc wrote:
| 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].
|
| 1: https://quantum-journal.org/papers/q-2021-04-15-433/
| semi-extrinsic wrote:
| 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.
| [deleted]
| FartyMcFarter wrote:
| 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.
|
| There's a video featuring Peter Shor about the invention of this
| algorithm: https://www.youtube.com/watch?v=6qD9XElTpCE
| [deleted]
| H8crilA wrote:
| 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.
| Strilanc wrote:
| 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].
|
| 1:
| https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...
|
| 2: https://en.wikipedia.org/wiki/Tensor_network
|
| 3: https://en.wikipedia.org/wiki/Hadamard_transform
|
| 4:
| https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2...
|
| 5: https://algassert.com/2016/06/14/qft-by-multiply.html
| dandanua wrote:
| 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).
| Sniffnoy wrote:
| (2007)
| benreesman wrote:
| 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.
| [deleted]
| [deleted]
| carver wrote:
| Is this the "uh, thing"?
|
| https://www.theatlantic.com/politics/archive/2015/01/the-blo...
| aorth wrote:
| I think it was the doxxing against his will by NY Times.
|
| https://www.newyorker.com/culture/annals-of-inquiry/slate-
| st...
|
| Edit: users pointed out this is a different Scott. My
| mistake!
| Chinjut wrote:
| This is a different Scott.
| fossuser wrote:
| 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.
| [deleted]
| [deleted]
| ithinkso wrote:
| > "I don't give a fuck anymore"
|
| This article is from 2007
| benreesman wrote:
| Haha stop upvoting my wrong comment people!
|
| Apparently Scott never gave a fuck. :) Dope.
| mikotodomo wrote:
| Wow. That such high end technical content is hosted on Wordpress
| really shows how battle tested and reliable it is.
| jefftk wrote:
| It does? I think mostly it shows that WordPress is a popular
| blogging platform.
|
| Also note that this was published in 2007, 4 years after
| WordPress was originally released, which probably makes Scott a
| bit of an early adopter.
| Ma8ee wrote:
| It's static text. What is hard about it?
| jstanley wrote:
| > 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.
| smegsicle wrote:
| note that this is what CERN is doing to 'manipulate the
| timeline'-
|
| the entire planet is obliterated except in cases pursuant to
| their interests, with none the wiser since in those cases, they
| 'didn't do anything'
| buu700 wrote:
| Sounds like quantum bogosort:
| https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort
|
| _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._
| Strilanc wrote:
| 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.
| layer8 wrote:
| 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.
| moffkalast wrote:
| 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.
| espadrine wrote:
| > _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!
| quickthrower2 wrote:
| That is quite the prisoners dilemma!
| YetAnotherNick wrote:
| The thing is that even in that sense collapse will select a
| random universe. So you will get a universe with killed output
| or whatever you said it.
|
| Also quantum parallel universe is not what you expect parallel
| universe to be. Universes interact with each other.
| cwillu wrote:
| Then you're talking about the complexity class PostBQP, rather
| than the class BQP.
|
| Postselection is ridiculously powerful, as you've noted.
| kspinka wrote:
| 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.
| __ryan__ wrote:
| 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.
| shagie wrote:
| Quantum immortality is a neat thing ( https://en.wikipedia.or
| g/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... ) and the exceedingly long story Nangurz ol Arny
| Fgrcurafba (rot13 because it kind of is a spoiler).
| Groxx wrote:
| As a middleground, at around 42 pages long, there's Divided
| by Infinity: https://www.tor.com/2010/08/05/divided-by-
| infinity/
| JadeNB wrote:
| When discussing quantum immortality and sci-fi, one must
| also mention Greg Egan's early _Quarantine_
| (https://en.wikipedia.org/wiki/Quarantine_(Egan_novel)).
| ctoth wrote:
| Also when discussing Quantum Immortality and Sci Fi, one
| must certainly mention Divided By Infinity.
|
| https://www.tor.com/2010/08/05/divided-by-infinity/
| cwillu wrote:
| The universe likes to play with its food.
|
| (What, did you think this logic is only valid when you're
| trying to gain godlike powers?)
| einpoklum wrote:
| I believe that you would enjoy this film:
|
| https://www.imdb.com/title/tt0482571/
| walnutclosefarm wrote:
| Congratulations to Scott Aaronson for the must lucide explanation
| of Shor's algorithm for the merely mathematically literate, ever!
| georgehm wrote:
| > 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 wrote:
| 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.
| eliben wrote:
| I like how there's a comment by Peter Shor commending Scott on
| the article :-) Knowing Scott's blog, this is likely legit
| ryan-duve wrote:
| 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:
|
| https://www.youtube.com/watch?v=spUNpyF58BY
| omoikane wrote:
| Near 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...
|
| 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.
___________________________________________________________________
(page generated 2022-07-31 23:00 UTC)