Scott Aaronson spoke at Google Cambridge a month ago on the topic of quantum computers, the limits imposed by physics, and search. His position is that there are probably fundamental physical limits to the problem of search, much like the limits to cpu speed or hard drive density. In fact, the latter provide a really nice illustration:
In particular, one of the few things physicists think they know about quantum gravity — one of the few things both the string theorists and their critics largely agree on — is that, at the so-called “Planck scale” of about 10-33 centimeters or 10-43 seconds, our usual notions of space and time are going to break down. As one manifestation of this, if you tried to build a clock that ticked more than about 1043 times per second, that clock would use so much energy that it would collapse to a black hole. Ditto for a computer that performed more than about 1043 operations per second, or for a hard disk that stored more than about 1069 bits per square meter of surface area. (Together with the finiteness of the speed of light and the exponential expansion of the universe, this implies that, contrary to what you might have thought, there is a fundamental physical limit on how much disk space Gmail will ever be able to offer its subscribers…)
--more after the break--
It seems like every time you hear about quantum computers in the press, this incredible machine is described that can simultaneously compute all of the exponentially possible input values for any problem and then pull the unique solution out of an infinity of results.
Thankfully (for my sanity at least) this isn't exactly true at all. There are a few specific types of problems that can be aided with the use of a quantum computer, and the distinction is that instead of finding a needle in an infinite number of haystacks, these problems involve drawing out statistical probabilities that are common across all potential inputs.
Now, the idea of quantum computing is to set up a massive double-slit experiment with exponentially many paths — and to try to arrange things so that the paths leading to wrong answers interfere destructively and cancel each other out, while the paths leading to right answers interfere constructively and are therefore observed with high probability.
...
On the other hand — and this is the most common misconception about quantum computing I’ve encountered — we do not, repeat do not, know a quantum algorithm to solve NP-complete problems in polynomial time. For “generic” problems of finding a needle in a haystack, most of us believe that quantum computers will give at most a polynomial advantage over classical ones.
He goes on to describe a conjecture which he calls the "No Supersearch Principle," which states that "There is no physical means to solve NP-complete problems in polynomial time — not with classical computers, not with quantum computers, not with anything else." And get this, if this conjecture is incorrect and a way were to be discovered, you could find the proof for every other major problem in mathematics (assuming it existed) by just having your magical computer test all possible proofs containing less than a billion symbols.
Basically, there may be a universe or two where the proverbial traveling salesman takes an optimum route through the city, but it's not the majority of universes, and we can't solve the problem without it becoming exponentially difficult the larger the city is.
What Google Won't Find - Link
