I had the chance to listen to Roger Penrose speak, and we asked him about Emporer's new Mind and other related topics. He didn't seem to feel that a quantum-computer violated the basic rules of computing--he said it's even been figured with an "oricle machine" and it still doesn't change what can and can't "be computed".

So, I suppose a q-computer can factor numbers a lot faster, but it wasn't "impossible" before.