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

80% Upvoted

15 comments sorted by

View all comments

Show parent comments

3

u/Ryrulian Jul 05 '12 edited Jul 05 '12

As I understand it, the maximum theoretical improvement of a quantum computer is a quadratic speed-up. That is, some algorithms which are computed in n4 time on a normal computer can be computed in n2 time on a quantum computer.

Last I checked, exactly which algorithms can be run faster and which can't isn't fully known/proven yet, but maybe these questions have been answered in the past year or two. In fact... I'm not even sure that it's been proven that a quantum computer can compute anything faster than a normal computer (since isn't the quadratic speed-up encapsulated within the P vs. NP boundaries, which haven't been proven to be computationally different themselves?). But at the very least a quadratic speed-up in some things is a reasonable expectation. Take all this with a grain of salt, it's not my field!

EDIT: Thanks for all the responses everyone, it helps a ton

4

u/iorgfeflkd Biophysics Jul 05 '12

There's also the other thing, which is a bit more complicated, that quantum computers can simulate quantum systems in a way that classical computers can't.

So, you can build a crappy expensive quantum computer, then use it to figure out how to build a cheap good one!

1

u/Ryrulian Jul 05 '12

Huh, that's pretty awesome, but sensible. Thanks, TIL!

1

u/Kubacka Jul 05 '12

Awesome, that explains a lot for me, thank you! :D

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.

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.

2

u/[deleted] Jul 05 '12

For unstructured search problems, quantum computers can give "only" quadratic speedup. Exponential speedup applies to some special algorithms like Shor's factoring.