Super simplified summary: because the probabilities can interfere with each other in controlled ways.

Bits vs Qubits

Suppose you have 3 bits, but you don't know what state they are in. Could be 000, 001, 010, 011, 100, 101, 110, or 111. There is a probability of the state being each of those possibilities. However, the bits are actually in one of these states. Any operation you perform, like 'increment', will take one fixed input and give one fixed output.

Now suppose you have 3 qubits, but you don't know what state they are in. Could be 000, 001, 010, 011, 100, 101, 110, or 111. There is a probability of the state being each of those possibilities. However, the probability is derived from a "magnitude" or "amplitude" (http://en.wikipedia.org/wiki/Probability_amplitude) which sortof actually physically exists. The bits are not in exactly one of the states. They "really" have an amplitude/probability.

Ok, whatever, so the probabilities are "magnitudes" and "actually exist". How does that help? Well ... you can perform operations that 'rotate' the magnitudes in ways that make them interfere with each other in ways that give the right answer more and more magnitude as you iterate. Keep in mind these rotations are over a huge number of magnitudes (2^n) but their running times are polynomial in the number of qubits (n). This allows you to do things like Grover's algorithm (http://en.wikipedia.org/wiki/Grover%27s_algorithm), searching N unordered items in O(Sqrt(N)) time:

  // http://tph.tuwien.ac.at/~oemer/doc/quprog/node17.html#SECTION00513300000000000000
  procedure grover(int n) {
    int l=floor(log(n,2))+1;        // no. of qubits
    int m=ceil(pi/8*sqrt(2^l));     // no. of iterations
    int x;
    int i;
    qureg q[l];
    qureg f[1];

    {
      reset;
      Mix(q);             // prepare superposition
      for i= 1 to m {     // main loop
        query(q,f,n);     // calculate C(q)
        CPhase(pi,f);     // negate |n>
        !query(q,f,n);    // undo C(q)
        diffuse(q);       // diffusion operator
      }
      measure q,x;        // measurement
      print "measured",x;
    } until x==n;
  }