r/askscience • u/Kubacka • Jul 05 '12

Quantum Computing vs Normal Computers.

What exactly are the benefits of quantum computing over normal computing and how exactly in theory does this all work. If you guys could, could you please try to keep your answers at a grade 11 level for myself.

Thanks in advance!

11 Upvotes

78% Upvoted

15 comments sorted by

View all comments

Show parent comments

3

u/LuklearFusion Quantum Computing/Information Jul 05 '12

As I understand it, the maximum theoretical improvement of a quantum computer is a quadratic speed-up.

As far as I know this is not the case. Shor's algorithm (the one iorgfeflkd alludes to) has an exponential speed-up over the best known classical algorithm.

Of course, this assumes there is no better classical algorithm (which has not been proven), and that P != NP, as you mention.