4 ms·
No variant of quantum computing is expected to solve NP problems in polynomial time. That's just a common misconception.
by dangirsh 9y ago
No variant of quantum computing is expected to solve NP problems in polynomial time. That's just a common misconception.
- adamnemecek 9y agohttps://en.m.wikipedia.org/wiki/Real_computation https://en.m.wikipedia.org/wiki/Real_computation Real computation can.
- IntronExon 9y agoIn principle. Not in the actual universe we inhabit, with its Beckenstein Bound.
- adamnemecek 9y agoArbitrary precision (not infinite) is good enough for me.
- IntronExon 9y agoSort of like coming arbitrarily close to the speed of light, in that it will require energy on the same asymptotic scale you’re hoping to achieve precision in. Degenerate matter computers?
- openasocket 9y ago"Real computation," which allows you to solve NP and #P problems in polynomial time, require infinite precision. With just arbitrary precision it isn't any more powerful than classical computation.
- krastanov 9y ago"Real computation" is a flawed model because it does not permit scalable error correction mechcanisms. Check out Aaronson's lecture notes if you are interested in the rigorous argument.
- adamnemecek 9y agoI disagree with Aaronson but am not quite there to have a serious discussion about it.
- kirrent 9y agoIf you think real computation is in any way feasible why don't you build one and make a silly amount of money?