= 27d567bc2d48d9f40e9ccc20ea370b15)
gordon_wrigley comments on The Quantum Physics Sequence - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (23)
I don't suppose you could spend a post or two explaining in your nice easy to understand way exactly what it is a quantum computer is supposed to do and how this might impact the NP problems.
It's not exactly known.
Grover's algorithm provides a quadratic speedup over brute-force algorithms for solving NP-complete problems, but that still leaves them as exponential-time. BQP (Bounded error, quantum, polynomial-time; basically the complexity class of quantum computers) is suspected to be disjoint from NP and a superset of P, but neither is known for sure.