How Shor's Algorithm works (2007) | Hacker News Reader

How Shor's Algorithm works (2007)

scottaaronson.com

293 pointsmonort17 comments

Aarsonson has been one of my favorite professors. His undergrad quantum information sciences class was great. Super smart guy, approachable, good lecturer, good person. A+ dude. I recommend following his blog if you don't already.

Video + Notes for his lectures MIT 6.045 Automata, Comput, & Complexity can be found here:

video lectures: http://web.de.mit.edu/public/courses/6/6.045/2015spring/

notes: http://stellar.mit.edu/S/course/6/sp15/6.045/materials.html

After Shor's algorithm a good follow up would be to learn about Grover's Algorithm[1]

Here is a fantastic explanation of it: http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s... [More technically involved explanation]

Interesting factoid: Scott Aaronson[2] interned with Lov Grover[3] at Bell Labs as a teenager!

[1] https://en.wikipedia.org/wiki/Grover%27s_algorithm

[2] https://blogs.scientificamerican.com/cross-check/scott-aaron... [This is a great interview, btw!]

[3] https://en.wikipedia.org/wiki/Lov_Grover

In the spirit of Muehlhauser's list of textbooks ( http://lesswrong.com/lw/3gu/the_best_textbooks_on_every_subj... ) can anyone recommend a more technical introductions to Shor's algorithm -- kets allowed -- who's read at least two other such introductions?

I can't recommend in the spirit that you mention, but the description in Nakahara's book Quantum Computing is surely technical and detailed enough. It so happens that googling for the book, I happened to find a whole text pdf in the results.

Hmm, I disagree with some of the recommendations on this list. Even if people could agree on the overall quality of books, it is not the only factor which should be considered when choosing a book. For example, one might choose a book which is lower quality(however that might be defined) in order to use a book whose goals more closely align with those of the reader.

From 2007 (now fixed).

These are some of the hardest papers to write and make visible; I was disabused of a few beliefs and the treatment of number theory didn't upset me so this was great, particularly the Fourier bit at the end.

@GordonS It's an HN convention for the title. If you would delete your comment then I think I would be allowed delete mine and would gladly do so now that the submission has been "fixed".

Of course an algorithm like this is evergreen.

If you click the "x minutes ago" link on any comment you can reply directly to it without having to wait for the "cooldown".

But I think if I reply to him then he can't delete and the whole thing recurses.

I am sorry for this derailing.

I know there is a convention to put the year in the title, but I thought it was only used if the date was actually relevant to the article?

No, it's also a handy way to show readers that this isn't something new. E.g. some readers will love to read anything new that Scott Aaronson writes, but wouldn't necessarily want to read something old or that they read in the past.

Is the date really relevant for this?

By default, readers assume that anything linked here is recent.

Is there (or can be) any plan to avoid mayhem if a quantum computer emerges controlled by an evil man?

There are cryptographic protocols that are thought to be safe against quantum computers, and people are gradually switching over to them.

Appreciated the comment on the blog by Peter Shor :)

Reply on news.ycombinator.com