  We consider a model of quantum computation in which the set of elementary
operations is limited to Clifford unitaries, the creation of the state
$|0\rangle$ computational basis. In addition, we allow the creation of a
one-qubit ancilla in a mixed state $\rho$, which should be regarded as a
parameter of the model. Our goal is to determine for which $\rho$ universal
quantum computation (UQC) can be efficiently simulated. To answer this
question, we construct purification protocols that consume several copies of
$\rho$ and produce a single output qubit with higher polarization. The
protocols allow one to increase the polarization only along certain "magic"
directions. If the polarization of $\rho$ along a magic direction exceeds a
threshold value (about 65%), the purification asymptotically yields a pure
state, which we call a magic state. We show that the Clifford group operations
combined with magic states preparation are sufficient for UQC. The connection
of our results with the Gottesman-Knill theorem is discussed.
