6 ms·

How Shor's Algorithm works (2007)

293 points by monort 9y ago

stablemap 9y ago
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 9y ago
  Is the date really relevant for this?
  - deleted 9y ago
    [deleted]
  - ameliaquining 9y ago
    By default, readers assume that anything linked here is recent.
- deleted 9y ago
  [deleted]
- stablemap 9y ago
  @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.
  - unkown-unknowns 9y ago
    If you click the "x minutes ago" link on any comment you can reply directly to it without having to wait for the "cooldown".
    - stablemap 9y ago
      But I think if I reply to him then he can't delete and the whole thing recurses. I am sorry for this derailing.
      - deleted 9y ago
        [deleted]
    - deleted 9y ago
      [deleted]
  - GordonS 9y ago
    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?
    - edanm 9y ago
      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.
kwaugh 9y ago
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.
jessriedel 9y ago
In the spirit of Muehlhauser's list of textbooks ( http://lesswrong.com/lw/3gu/the_best_textbooks_on_every_subject/ 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?
- nur0n 9y ago
  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.
- sampo 9y ago
  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.
TempleOS 9y ago
Did the greek oracle use quantum computing. Yer a retard nigger monkey. 37898 4:19 And Solomon made all the vessels that were for the house of God, 37899 the golden altar also, and the tables whereon the shewbread was set; 37900 4:20 Moreover the candlesticks with their lamps, that they should burn 37901 after the manner before the oracle, of pure gold; 4:21 And the 37902 flowers, and the lamps, and the tongs, made he of gold, and that 37903 perfect gold; 4:22 And the snuffers, and the basons, and the spoons, 37904 and the censers, of pure gold: and the entry of the house, the inner 37905 doors thereof for the most holy place, and the doors of the house of 37906 the temple, were of gold. 37907 37908 5:1 Thus all the work that Solomon made for the house of the LORD was 37909 finished: and Solomon brought in all the things that David his father 37910 had dedicated; and the silver, and the gold, and all the instruments, 37911 put he among the treasures of the house of God.
seycombi 9y ago
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/ http://web.de.mit.edu/public/courses/6/6.045/2015spring/ notes: http://stellar.mit.edu/S/course/6/sp15/6.045/materials.html http://stellar.mit.edu/S/course/6/sp15/6.045/materials.html
wicha 9y ago
Is there (or can be) any plan to avoid mayhem if a quantum computer emerges controlled by an evil man?
- OscarCunningham 9y ago
  There are cryptographic protocols that are thought to be safe against quantum computers, and people are gradually switching over to them.
netvarun 9y ago
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-search-algorithm 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 https://en.wikipedia.org/wiki/Grover%27s_algorithm [2] https://blogs.scientificamerican.com/cross-check/scott-aaronson-answers-every-ridiculously-big-question-i-throw-at-him/ https://blogs.scientificamerican.com/cross-check/scott-aaron... [This is a great interview, btw!] [3] https://en.wikipedia.org/wiki/Lov_Grover https://en.wikipedia.org/wiki/Lov_Grover
hossbeast 9y ago
Appreciated the comment on the blog by Peter Shor :)

293 points by monort 9y ago

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 9y ago
Is the date really relevant for this?
- deleted 9y ago
  [deleted]
- ameliaquining 9y ago
  By default, readers assume that anything linked here is recent.
deleted 9y ago
[deleted]
stablemap 9y ago
@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.
- unkown-unknowns 9y ago
  If you click the "x minutes ago" link on any comment you can reply directly to it without having to wait for the "cooldown".
  - stablemap 9y ago
    But I think if I reply to him then he can't delete and the whole thing recurses. I am sorry for this derailing.
    - deleted 9y ago
      [deleted]
  - deleted 9y ago
    [deleted]
- GordonS 9y ago
  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?
  - edanm 9y ago
    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.

kwaugh 9y ago

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.

jessriedel 9y ago

In the spirit of Muehlhauser's list of textbooks ( http://lesswrong.com/lw/3gu/the_best_textbooks_on_every_subject/ 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?

nur0n 9y ago
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.
sampo 9y ago
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.

TempleOS 9y ago

Did the greek oracle use quantum computing. Yer a retard nigger monkey. 37898 4:19 And Solomon made all the vessels that were for the house of God, 37899 the golden altar also, and the tables whereon the shewbread was set; 37900 4:20 Moreover the candlesticks with their lamps, that they should burn 37901 after the manner before the oracle, of pure gold; 4:21 And the 37902 flowers, and the lamps, and the tongs, made he of gold, and that 37903 perfect gold; 4:22 And the snuffers, and the basons, and the spoons, 37904 and the censers, of pure gold: and the entry of the house, the inner 37905 doors thereof for the most holy place, and the doors of the house of 37906 the temple, were of gold. 37907 37908 5:1 Thus all the work that Solomon made for the house of the LORD was 37909 finished: and Solomon brought in all the things that David his father 37910 had dedicated; and the silver, and the gold, and all the instruments, 37911 put he among the treasures of the house of God.

seycombi 9y ago

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/ http://web.de.mit.edu/public/courses/6/6.045/2015spring/ notes: http://stellar.mit.edu/S/course/6/sp15/6.045/materials.html http://stellar.mit.edu/S/course/6/sp15/6.045/materials.html

wicha 9y ago

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

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

netvarun 9y ago

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-search-algorithm 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 https://en.wikipedia.org/wiki/Grover%27s_algorithm [2] https://blogs.scientificamerican.com/cross-check/scott-aaronson-answers-every-ridiculously-big-question-i-throw-at-him/ https://blogs.scientificamerican.com/cross-check/scott-aaron... [This is a great interview, btw!] [3] https://en.wikipedia.org/wiki/Lov_Grover https://en.wikipedia.org/wiki/Lov_Grover

hossbeast 9y ago

Appreciated the comment on the blog by Peter Shor :)