For the impatient, a draft version in PDF format is available at http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/

For the impatient, a draft version in PDF format is available at http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/limitsqc-draft.pdf [pdf]. I particularly enjoyed the somewhat applicable reference to Star Trek, humpback whales and plexiglass. "Contrary to the popular image, their work has revealed even a quantum computer would face significant limitations. In particular, while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there’s reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. This class includes the problems mentioned above. Limitations of quantum computers have also been found for games of strategy like chess, as well as for breaking cryptographic hash functions. All of these limitations apply to a class of algorithms known as “black-box algorithms,” which encompasses all quantum algorithms known today. Giving a complete proof that no fast quantum algorithm can solve these problems is out of the question, since we can’t even prove that no fast quantum algorithm can solve them. " Although I do not follow Mssr. Aaronson's work, I keep bumping into his blog often. Thanks for the heads up.