Why does superposition make quantum computers faster?

[tavi_boada]

Hello,

In my university there is a bit of a fuss about Quantum Information (QI). A few professors work in this field and there have been some conferences where they try to explain to the rest what is QI and so on. I think it is safe to say I know a bit of quantum mechanics, not at a professional level though, but I can't understand why having bits in a superposition of states makes computing more efficient and fast. Theoreticaly, you can drastically cut down in search times, and it is said that they could actually make encrypted messages unsafe. I think most encryption is based on very large prime numbers which would be factorized with this quantum computer (!?). I know all this is old news but can anyone explain the crucial point that accounts for this boost in computing power?

 

[Edgardo]

Maybe you will find something here (sorry, I personally can't explain you how quantum computation works, I think it's based on the Shor Algorithm):

http://www.qubit.org/
http://www.qubit.org/library/introductions.html

http://www.theory.caltech.edu/people/preskill/ph229/

 

[Hurkyl]

A typical function on a Quantum Computer operates on the basis states like this:

|x>|y> → |x>|y + f(x)>

So, if you have a big superposition of states, then one application of your function gets applied to every basis state in the superposition!


Of course, there is a catch: you can only get one answer out of the computer, and you can't directly control which one.

However, if you can write some other function g that can identify the desired result out of the n possible results, then Grover's algorithm let's you get the desired result with high probability. (It involves applying g and some other stuff √n times, where n is the total number of possible results)

Grover's algorithm is often described as an algorithm that can search an n-long list in √n time.