Comment A quick overview (Score 5, Interesting) 224
Quantum effects are not hard to understand, they're just counter-intuitive to everyday experience. This site has a good explanation of QM, and how it differs from normal experience.
The universe doesn't work in specifics until something is measured. It doesn't choose parameters for particles (spin, position, &c) at the outset and let things evolve like little billiard balls.
Instead, it uses probabilities which flow and interact with one another. These probabilities have both amplitude and phase, so that the interactions are wave-like as well as probability-like. For example, because of this wave-like interaction it's possible for two non-zero probability flows to completely cancel to zero.
The universe appears to calculate probabilities for all possible outcomes and only choose one when the measurement is made. When particles are entangled, you increase the number of possible outcomes. For each new particle that becomes entangled you increase the number of possible outcomes by a factor of two. Ten particles will have 2^10 = 1024 possible outcomes, and so on.
So to do math at the quantum level, you take a set of entangled particles and set up the measurement so that division with no remainder has probability one while division with any other remainder has probability zero. Then load your register with all the integers, let the probabilities interact, and take the measurement.
You have just performed division using all the integers at once.
If you can do this with a reasonably large register you can check all the factors of a composite number in linear time - the time it takes you to load sqrt(P) divisors into the register.
Easy peasy!
An interesting side-note is the idea of the universe keeping track of all possible outcomes until a measurement is made. If this works as predicted, the universe will have to keep track of 2^3000 possible outcomes, depending on the key length (3000 is the recommended RSA key length to be secure until 2030).
There are only ~10^80 = 2^240 atoms in the universe. If a quantum computer works as predicted, one wonders how and where the universe keeps track of all these states. At the very least, quantum computing is interesting because it will allow us to probe the limits of the universe in an entirely new domain.
Here's hoping we don't encounter a buffer overflow.
(Note: Some facts were harmed in the making of this explanation.)