[cathrithbo]

>some problems in mathematics will remain beyond the limits of quantum computing

I don't think it's surprising that quantum computers, by themselves, will not be able to solve mathematical problems. Problem solving is not a feature of hardware per se, it is done by humans. Perhaps one day by AIs, too, if we can discover how to program them.

Two tantalising potential benefits of Quantum Computers:

(1) the ability to model all kinds of matter efficiently at the molecular level which will spur the development of nanotech

(2) people will ask 'Where are these humongous computations being performed?' and then embrace the 'many worlds interpretation' of quantum mechanics, which will in turn create further scientific and philosophical progress

[icegreentea]

Well, they're speaking in rigourous terms. Quantum computing will allow us to attack an enlarged set of problems in polynomial time. For example, integer factorization. However, there are still going to be other problems that quantum computers cannot solve in polynomial time (ie, much better than classical computers). For example, it's generally believed that they will not be able to solve NP-Complete (traveling salesman) problems in polynomial time.

For a nice description and diagram, take a look at the wiki page. http://en.wikipedia.org/wiki/Quantum_computing#Relation_to_c...

[swordswinger12]

Shameless piggybacking: Also look into the work that complexity theorists have done with quantum complexity classes like BQP.