I remember writing something about this subject in a thread a month or so ago, but now I can't fint it, so I'll just write it again
A quantum computer operates with quantum bits (qbits) instead of "conventional" bits. Whereas a normal bit is either one or zero, a qbit can be either one, zero or in any position between those two, or put in another way: A qbit can be both one and zero at the same time (or more one than zero or the other way round). We can express the state of one qbit (q) as:
|q> = a|0> + b|1>
Think of |0> and |1> as orthonormal vectors (they are orthogonal on each other and they have length one). a and b are complex numbers with the property that |a|^2 + |b|^2 = 1. if a = 0, then the qbit is in state |1> hence represents the same value as the classical bit 1 for example. A theorem in linear algebra says that is we have a set of basis vectors for a vector space, we can represent any vector in that vector space as a linear combination of the basis vectors. This is exactly what we do here.
One interesting feature is that we can't measure the state of a qbit (or in general a system of several qbits) without changing the state. If we measure the state it will collaps to the result of the measurement. Notice that the numbers |a|^2 and |b|^2 represents the probability of either getting a |1> or a |0>. If we get a 1 then |a| = 1 and |b|=0 after the measurement.
Another interesting state worth mentioning is the bell state of two qbits:
|q> = (|00> / Sqrt(2)) + (|11> / Sqrt(2))
Think of this state for a moment, then think of what happens when you measure only the first qbit and leave the second one alone. You can see that the two qbits are either both 0 or both 1 (both with probability 0.5) so if you measure the first qbit and get a 0 then the second is 0 and if you get a 1, then the second qbit is a 1. Hence you determine the state of the second qbit only by looking at the first. This is the whole idea behind quantum computing as I will now show an example of:
Your friend gives you a function f that takes as input the numbers 0 .. N-1 (for some N = 2^n for some other n, but nevermind that). He/she promises you that the function is either all 0 (no matter what you give it as input it will return 0) or balanced (on half the inputs (N/2) it will return 0 on the other half 1). You task is to determine if the function is balanced or constant.
How many times do you have to evaluate the function do do this? In the classical case you need to evaluate it N/2 times in worst case before you are sure. If you feed it N/2-1 different values and you get 0 on each of them, it would still be the case that it was balanced but that you were really unlucky and just feed it the exact numbers that would produce 0. On the other hand, if you use a quantum computer you could do with just one evaluation of the functions. I could perform the calculations, but not many of you would get them anyway, so instead I'll try to explain what goes on...
You prepare a number of qbits in a state where they are both 0 and 1 with probability 0.5 (think of these qbits as representing a binary string of n bits => the string can represent any integer from 0 to N-1. Since all bits are both one and zero you are representing all these values at the same time). Now give the qbitstring (x) as input to f. Now f has in fact calculated all output values of f at once, since the result is not determined until you measure it. Do a bitwise XOR of f(x) with 1 and again put the input x in a equally weighted superposition of zero and one. Now the magic: x is now either all one with probability 1 or 0 with probability 1 (depending on whether f was balanced or constant). That is by a single evaluation of f you know the answer that in the classical case would require N/2 evaluations of f. I know this might not make much sence, but without a little more knowledge this can't be explained any better, I'm sorry.
With a quantum computer we can solve some problems a lot faster than what is possible with a conventional computer. There are problems however which we can't do any faster, and there are problems where we can prove that we can't go any faster than the squareroot of that time it would take on a conventional computer. Some problems however (such as factoring an integer and solving the discrete log problem) can be solved exponentially faster with a quantum computer.
I know there a still a lot of unanswered questions (such that how do we make a quantum computer in practice) but we'll take the questions down the road if there are any.