Magic state distillation

The Clifford group consists of a set of ${\displaystyle n}$-qubit operations generated by the gates {H, S, CNOT} (where H is Hadamard and S is ${\displaystyle {\begin{bmatrix}1&0\\0&i\end{bmatrix}}}$) called Clifford gates. The Clifford group generates stabilizer states which can be efficiently simulated classically, as shown by the Gottesman–Knill theorem. This set of gates with a non-Clifford operation is universal for quantum computation.[5]

Magic states are purified from ${\displaystyle n}$ copies of a mixed state ${\displaystyle \rho }$.[6] These states are typically provided via an ancilla to the circuit. A magic state for the ${\displaystyle T}$ gate is ${\displaystyle |M\rangle =\cos(\beta /2)|0\rangle +e^{i{\frac {\pi }{4}}}\sin(\beta /2)|1\rangle }$ where ${\displaystyle \beta =\arccos \left({\frac {1}{\sqrt {3}}}\right)}$. By combining (copies of) magic states with Clifford gates, can be used to make a non-Clifford gate.[5] Since Clifford gates combined with a non-Clifford gate are universal for quantum computation, magic states combined with Clifford gates are also universal.

The first magic state distillation algorithm, invented by Sergey Bravyi and Alexei Kitaev, is a follows.[5]

Input: Prepare 5 imperfect states.

Output: An almost pure state having a small error probability.

repeat

Apply the decoding operation of the five-qubit error correcting code and measure the syndrome.

If the measured syndrome is ${\displaystyle |0000\rangle }$, the distillation attempt is successful.

else Get rid of the resulting state and restart the algorithm.

until The states have been distilled to the desired purity.