After the MARCI meeting on 030401:
----------------------------------

1) Quantum entanglement

Take the following superposition of states of a 2-qubit system:

    |0>|0>  +  |1>|1>
    -----------------                   (1)
        sqrt(2)

Suppose we measure the first qubit of this system and we get |a>. Then
we automatically know that the second qubit must also be |a>. Thus,
in a system in state (1) the qubits are correlated. There are (physical)
ways to create such a system and then physically separate the qubits.
Suppose they are 1 million light years apart. Before measurement
we ignore the contents of each of the qubits. After measuring the first
qubit we know instantaneously that the second qubit also has the same
values. Sometimes this effect is explained by saying that "observing
the first qubit makes the second qubit collapse onto a definite state,
thus the velocity of propagation of information exceeds the velocity
of light". This interpretation gives rise to a semi-magical explanation
of quantum mechanics.

2) Shor's algorithm - the magical parts

The first magical part is that in one step we go from state

   \sum_x  |x> |0>

to 

   \sum_x  |x> |f(x)>

There is nothing magical here: what we mean is that we are able to 
produce a physical implementation of the application of f() to a
quantum system so that if the system is in an unknown state, any measurement
on the first subsystem will make the second subsystem (correlated by
quantum entanglement) collapse to the corresponding value. One possible
non-magical interpretation is that the application of f() is having 
an effect at the moment of measurement, not before.

The second magical part is that observing a value u on the second
subsystem will make the first subsystem collapse to a superposition
of all values |x> such that f(x)=u. In fact the observed effect is
magical but the mechanism can be explained a little more clearly. 
I am not able to give this explanation, as I hardly understand it
myself. In short, it is something to do with summation of phases.
By applying an inverse discrete Fourier transform to the superposition

  \sum_x |x> |f(x)> 

we basically "group together" clusters of the first register that
correspond to the same value f(x) in the second register. When the
second register is measured, the effect on the clusters is that the
coefficients of those clusters corresponding to non-measured values
of the second register go to zero because of opposite phases, whereas
the coefficients of the cluster corresponding to the measured
value of the second register sum up to 1.