Limited indeed. If nothing else, I'd suggest reading <http://www.scottaaronson.com/democritus/> http://www.scottaaronson.com/democritus/>. In short: > there ar

Limited indeed. If nothing else, I'd suggest reading <http://www.scottaaronson.com/democritus/> http://www.scottaaronson.com/democritus/>. In short: > there are some apparently NP-complete problems that are P for a quantum process The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired). > it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers. 'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be. > Or it may be that quantum computers can really solve some NP-complete problems in P time. This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)