A really important thing to keep in mind is that different possible states have
amplitudes, which are
complex numbers. These are the real, fundamental description of the system, rather than the
probabilities, which are
real numbers.
The state of the system could be, for example:
State Amplitude Probability
+/+ 1/2 1/4
+/- -1/2 1/4
-/+ -i/2 1/4
-/- i/2 1/4
In the right-hand column, I've included the probability of measuring each state (notice that it's the square of the modulus of the amplitude), but that's not the fundamental quantity that you deal with in quantum mechanics.
All the dynamics of a quantum system are expressed in terms of how the amplitudes change over time. In fact, if this means anything to you, the most succinct way to state how quantum mechanics works is that a quantum system with N possible states is represented by an N-dimensional complex vector, and that in an infinitesimal time step dt, the system goes from v to (1+iHdt)v, where H is a matrix with complex entries (and 1 stands for the identity matrix). If you measure the quantum system, you have to first pick a set of basis vectors in which to measure it. The result you get is one of the basis vectors. The probability of getting any basis vector as result is the square of the coefficient (technically, the square modulus of the coefficient) on that basis vector. The coefficient is what we call the "amplitude."
In a quantum computer, you first prepare the system in a desired state (a complex vector). Then, you get to choose what linear operations you will apply to the state. Then, you observe the state in some basis (in the complex vector space), and get a random basis vector (proportional to the modulus squared of the coefficients in the final state). That's basically it. The trick is whether or not you can actually figure out a way to compute anything useful with such a system with lower complexity than you can with a classical computer. Your fundamental operations are different (linear transformations of a complex vector) than they are in a classical computer, and you have the added wrinkle that you can't read off the final state of the computer - the final result is a random draw from a probability distribution that is based on the state of the computer. Peter Shor figured out that with this setup, you can factor large numbers in a way that uses fewer operations than a classical computer (asymptotically). It also turns out that you can simulate quantum systems really effectively with this sort of system. That's not so surprising. As Feynman said,
> "Nature isn't classical, dammit, and if you want to make a simulation of Nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy."