I had a business trip to Boston this past week, which means I got a lot of good reading hours in on the plane ride across the country.  As a result, expect to see some intellectually inspired posts this week.

Tonight, I’m going to start off with an easy one – the most recent issue of Scientific American.  It is a great issue.

Actually, three of the articles were blog worthy.  Tonight, I’m going to highlight the great piece by Scott Aaronson called “The Limits of Quantum Computers“.

Here is a synopsis, from the top of the article:

• Quantum computers would exploit the strange rules of quantum mechanics to process information in ways that are impossible on a standard computer.
• They would solve certain specific problems, such as factoring integers, dramatically faster than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly.
• Exotic alterations to the known laws of physics would allow construction of computers that could solve large classes of hard problems efficiently. But those alterations seem implausible. In the real world, perhaps the impossibility of efficiently solving these problems should be taken as a basic physical principle.

Nah, I don’t think that does it justice.

I’ve been following Quantum Computing off-and-on since the mid-1990s.  I took my first Automata & Complexity course at Stanford (CS 154, from Rajeev Motwani) back in 1995.  One of the truly mind-opening courses in the Computer Science undergrad.  Recognizing that there are mathematical frameworks to not just solve problems, but to describe their complexity is fascinating.

Quantum Computing is fascinating because it takes advantage of the truly strange physics of entanglement, a state in Quantum Mechanics where particles can share a matching, but unknown, fate.  A separate branch of algorithmic mathematics has sprung up around analyzing what types of problems, if any, would be simpler to solve on the basis of a computer that leveraged these “Quantum Bits” or QuBits, for short.  At the same time, molecular scientists have struggled to make progress building very small quantum computers.

To date, there are a small number of algorithms that Quantum Computers have been proven to be able to solve significantly more efficiently than traditional computers.  Interestingly, most of them revolve around factoring, which happens to be the one area that we base most of our security algorithms around.  It turns out that factoring a very large number into two primes is very difficult for normal computers, but very easy for quantum computers.

I don’t think I can summarize an 8-page detailed article here, but let’s just say that in this short article, Aaronson manages to:

• Give a high level overview of basic complexity theory
• Give a background on what Quantum Computing is, generally
• Give a background on what makes Quantum Computing different, algorithmically
• Give examples of the types of problems that QC will significantly improve
• Give examples of the types of problems that QC will not significantly improve
• Give interesting mathematical & physics implications of QC algorithmic theory
• Intersperse the above with incredibly useful diagrams and drawings

Here is my favorite chart in the article – a simple one that maps the changes that quantum computing introduce in the world of algorithmic complexity:

And that’s just one of the sidebars!  🙂  It’s interesting to note that, after scanning this, I discover from Scott’s blog that he had to fight to get that diagram included!

The complexity class inclusion diagram on page 67 was a key concession I did win. (Apparently some editors felt a Venn diagram with P, NP, BQP, and PSPACE would be way too complicated, even for readers who regularly gobble down heaping helpings of M-theory.) As you can imagine, exposing people to this stuff seemed pretty important to me: this is apparently the first time P, NP, and NP-completeness have been explained at any length in Scientific American since articles by Knuth and by Lewis and Papadimitriou in the 1970’s.

Much appreciated, Scott.

Scott Aaronson has his own blog:
http://www.scottaaronson.com/blog

and he also runs an online encyclopedia for complexity classes:
http://www.complexityzoo.com

And to think, I was just at MIT and missed the chance to meet him. 🙂

The article is not yet fully online, but if you have a chance, I highly recommend picking up a copy of the issue.  Scott has posted an early draft of his article, in PDF, here.  Or better yet, subscribe.  It really is the one scientific magazine to subscribe to if you want to keep up-to-date on a broad range of scientific discovery.