Quantum Computers are able to solve problems of complexity BQP in polynomial time. BQP is suspected to cover all problems in P, some in NP (but not NP-complete), and some outside of NP but in PSPACE. (http://en.wikipedia.org/wiki/BQP)
Ah! That clears things up quite a bit. I'm surprised they're not able to work at the NP-C set. Is it because the probability of a right answer is so small?