Shor, I’ll do it (2007) | Hacker News Reader

Shor, I’ll do it (2007)

scottaaronson.blog

308 pointsmonort48 comments

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

> 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.

Then you're talking about the complexity class PostBQP, rather than the class BQP.

Postselection is ridiculously powerful, as you've noted.

  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.

Quantum immortality is a neat thing ( 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... ) and the exceedingly long story Nangurz ol Arny Fgrcurafba (rot13 because it kind of is a spoiler).

When discussing quantum immortality and sci-fi, one must also mention Greg Egan's early Quarantine (https://en.wikipedia.org/wiki/Quarantine_(Egan_novel)).

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/

As a middleground, at around 42 pages long, there's Divided by Infinity: https://www.tor.com/2010/08/05/divided-by-infinity/

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?)

That is quite the prisoners dilemma!

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.

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.

I googled that paradox, but can only see your comment. What is it about?

It's a joke, lol.

> 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!

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.

[0] https://cheapuniverses.com/

[1] https://qrng.anu.edu.au/

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'

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.

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.

I believe that you would enjoy this film:

https://www.imdb.com/title/tt0482571/

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.

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

I like how there's a comment by Peter Shor commending Scott on the article :-) Knowing Scott's blog, this is likely legit

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.

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].

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

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 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.

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].

1: https://quantum-journal.org/papers/q-2021-04-15-433/

> 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?

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.

Congratulations to Scott Aaronson for the must lucide explanation of Shor's algorithm for the merely mathematically literate, ever!

(2007)

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.

Is this the "uh, thing"?

https://www.theatlantic.com/politics/archive/2015/01/the-blo...

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!

This is a different Scott.

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.

They both list the other blog as recommended reading (although Shtetl-Optimized still links to Star-Slate-Codex rather than Astral-Codex-Ten).

> "I don't give a fuck anymore"

This article is from 2007

Haha stop upvoting my wrong comment people!

Apparently Scott never gave a fuck. :) Dope.

Wow. That such high end technical content is hosted on Wordpress really shows how battle tested and reliable it is.

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.

It's static text. What is hard about it?

Reply on news.ycombinator.com