28 ms·
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)
by vmind 16y ago
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 http://en.wikipedia.org/wiki/BQP)
- sukuriant 16y agoAh! 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?