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 10⁴³ 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 10⁴³ operations per second, or for a hard disk that stored more than about 10⁶⁹ 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--