Quantum computing, NP complexity Hi I have a very limited knowledge of quantum physics and its bothering me trying to understand quantum computing. 
I want understand how a qubit can return usable data faster then a regular bit, how is the NP complexity not an obstacle?  
 A: The best way to understand this is to work through an example.  Here is how you factor the number 15 using Shor's algorithm.  (If you prefer, view the problem not as factoring 15 but as solving $2^r=1 \hbox(mod 15)$, and skip Step Seven).  As you work through this, imagine replacing 15 with a much larger composite number, and you'll see the advantage of having the quantum algorithm.
 Step One.  Prepare a register in
the state
$$|1>+|2>+|3>+|4>+|5>+|6>+|7>+|8>
+|9>+|10>+|11>+|12>+|13>+|14>+|15>$$
 Step Two.  Apply the function
$x\mapsto 2^x$ (mod 15) to the above
register and put the result in a
second register.  The second register
now contains:
$$|2>+|4>+|8>+|1>+
|2>+|4>+|8>+|1>+
|2>+|4>+|8>+|1>+
|2>+|4>+|8>+|1>$$
which is the same as
$$|2>+|4>+|8>+|1>$$
Step Three. Observe the second
register.  With equal probabilities,
we might observe $2$, $4$, $8$, or
$1$.  For illustration, let's suppose
we observe $2$.  (The other cases are
similar.)
Step Four.  Now the first register
contains
$$1>+|5>+|9>+|13>$$
These differ by 4, but we don't know
this because we haven't done the
computations necessary to carry this
out (actually we {\it have/} done
them in this example with $N=15$, but
they'd be prohibitively costly if $N$
were huge.)  If we knew that the
difference was 4, we could skip to
Step 7.  As it is, let's call the
difference $r$ because it's still
unknown to us.
Step Five.  Apply the function
$$x\mapsto \sum_ye^{2\pi i x
y/15}|y>$$
to the first register and put the
result in the second register.
The second register now contains
$$\sum_y \Big(e^{2\pi i  y/15}
          +e^{2\pi i 5 y/15}
          +e^{2\pi i 9 y/15}
          +e^{2\pi i 15 y /15}\Big)|y>$$
Numerically, the norms of the
coefficients are given approximately
by the following table:
$$\matrix{
|y>&\hbox{ Norm of Coefficient}\cr
1&.9\cr
2&1.7\cr
3&2.6\cr
4&2.5\cr
5&1\cr
6&.4\cr
7&2\cr
8&2\cr
9&.4\cr
10&1\cr
11&2.5\cr
12&2.6\cr
13&1.7\cr
14&.9\cr
15&4\cr}$$
which peaks (this is no accident) near
$y=3,4,7,8,11,12,15$---the values
where $4y/15$ is close to an integer.
Step Six.  Observe the second
register.  If you get $y=15$, you
learn
nothing.  Otherwise, you probably get
$y=3,4,7,8,11$ or $12$---which allows
you to
guess---after a couple of trials---
that $r=4$, based on the knowledge
that $yr/15$ is probably close to an
integer.
Step Seven.  Now we know that $r=4$,
which tells us that $2^4=1$ (mod
$15$).  So 15 divides $2^4-1=(2^2-
1)(2^2+1)=3\times 5$.  Choose either
factor (say 3) and compute its
greatest common divisor with 15 using
euclid's algorithm.  This gives 3.
Therefore 3 is a factor of 15.
