Comment Re:Actually... (Score 1) 77
Actually one way to define NP is that the solutions can be verified in polynomial time; although the complexity class is usually defined in terms of a universal turing machine.
I think you might be confusing NP with NP-hard. An NP-hard problem is at least as hard as NP (in other words, if you can solve NP-hard then you can solve any NP), but having a solution doesn't necessarily mean you can verify in polynomial time.
AFAIK, no general solutions for NP-complete or NP-hard complexity classes have been shown for quantum computers, only a few instances like factoring have been shown to be faster in quantum computers.