3 ms·
Remember quantum computing ? a lot of NP problems will become P
by rrodriguez89 11y ago
Remember quantum computing ? a lot of NP problems will become P
- Ar-Curunir 11y agoNo, they'll become a part of BQP (or rather are already). P is defined as the class of problems decidable in polynomial time on a classical Turing machine. P doesn't change with the advent of quantum computers. Also it is suspected that BQP \not \subset NP, i.e. there are problems in BQP that might not be in NP.
- eru 11y agoAnd almost certainly, NP \not \subset BQP. In fact, there are only a few problems found so far where quantum computing gives a speedup compared to classical computers.