Universal quantum computation with ideal Clifford gates and noisy ancillas

We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state $\mid 0⟩$, and qubit measurement in the 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.

Figure 1

Left: the Bloch sphere and the octahedron $O$. Right: the octahedron $O$ projected on the $x-y$ plane. The magic states correspond to the intersections of the symmetry axes of $O$ with the Bloch sphere. The empty and filled circles represent $T$-type and $H$-type magic states, respectively.

Figure 2

The final error probability ${ϵ}_{\mathrm{out}}$ and the probability $p_s$ to measure the trivial syndrome as functions of the initial error probability $ϵ$ for the $T$-type states distillation.

Figure 3

The final error probability ${ϵ}_{\mathrm{out}}\left(ϵ\right)$ for the $H$-type states distillation.