The man on the street that Shor has seen

Scott Aaronson explains Shor’s algorithm here in an article that Shor himself describes as “the best job of explaining quantum computing to the man on the street that I’ve seen”. Word. Also, see the previous post in which Aaronson summarizes a recent breakthrough in quantum algorithms that will potentially allow a single ant to evaluate a NAND tree in O(√N) time.

Update: In the interest of fair and balanced reporting, we note that Geordie D. Wave provides an alternative yet equally valid explanation of Shor’s algorithm here. “The premise of Shor’s algorithm is this: take one (large) QC, one large product of prime numbers, shake well, out comes the factors of the large product of primes”. Now, is this really the kind of algorithm that Shor had in mind? Room 408 is willing to bet yes.