Re:Breaking np-complete with memcomputing. Is it real?
by adrianN on Thursday July 09, 2015 @08:23AM
(#9857408)
Quantum computers can't solve NP complete problems any better than classical computers as far as we know. You can at best hope for polynomial speedups. That is the scientific consensus, I don't know what weight of opinion you're talking about.
[ Parent
| on HN ]
Re:Breaking np-complete with memcomputing. Is it real?
by ikeboy on Thursday July 09, 2015 @09:39AM
(#9857767)
He seems to be misunderstanding Scott as claiming that no quantum computers will beat classical ones (even for factoring and the like), whereas Scott only makes the claim for NP-complete problems.
Re:Breaking np-complete with memcomputing. Is it real?
by mhurd on Thursday July 09, 2015 @06:52PM
(#9861222)
Yes. That is right. I misunderstood Scott. He makes sense. BQP covers factorisation which is different to NPC.
That said, it is unclear how far Adiabatic notions will take us but it seems there are limits there too with respect to the spectral issues.