Hacker News new | past | comments | ask | show | jobs | submit login
New SciAm Article on Limits of Quantum Computing (scottaaronson.com)
13 points by rw on Feb 18, 2008 | hide | past | favorite | 2 comments



For the impatient, a draft version in PDF format is available at 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.


For any kind of adversary system, the opponents will both use quantum computers, so the effects will cancel out. E.g. quickly factoring large numbers means the security industry will use larger numbers.

However, this is a problem for systems that are embedded and hard to replace.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: