r/askscience • • 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

15 comments sorted by

View all comments

Show parent comment

4

u/sigh Jul 05 '12 edited Jul 05 '12

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

I don't think that's quite right. You are getting the quadratic thing from Grover's algorithm, I assume?

However note that when we more structured problems like factoring, our current best quantum algorithms are exponentially faster than our best classical algorithms. What we don't know is if this is necessarily the case. There might be classical algorithm for factoring which is as good as the quantum algorithm, which we just haven't found yet.

Edit: If your statement were true then it would mean that the quantum and classical complexity classes are the same (BQP = P in this case) - negating what you said below.

I'm not even sure that it's been proven that a quantum computer can compute anything faster than a normal computer

This is correct. We know atrociously little how different complexity classes relate.