I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?
I have found that Sipser's "Introduction to the Theory of Computation" is a good primer for all of this, for those that are curious. Now to work on a provably EXPTIME-hard encryption method. I think I can bang one out this weekend. ;)