4 ms·
Per Wikipedia isn't not actually known whether quantum computers will be able to solve NP-complete problems in polynomial time: > There is a common misconcepti
by lomnakkus 8y ago
Per Wikipedia isn't not actually known whether quantum computers will be able to solve NP-complete problems in polynomial time:
> There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.[120]
The citation is from 1997, but I seem to remember that someone came up with a proof sometime in the last decade...? Probably just my faulty memory rather than the Wikipedia being out of date.
- graycat 8y agoToo much detail for me!!! I'll assume that the cubits will be able to do total enumeration right away! Now, while we are waiting on that, if there are some problems in combinatorial optimization to solve, trot them out and we will see. Maybe for some of the problems, current techniques can make big bucks.
- abdullahkhalids 8y agoThere is no known proof of separation between BQP and NP. See https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP for the relation of BQP to other complexity classes.
- lomnakkus 8y agoAh, thanks. (I was actually looking at the BQP page,, but then realized that I know far less about the Q classes than I should and found the more general "quantum computing" page where my citation is from.)