Magic state distillation
Magic state distillation is a process that takes in multiple noisy quantum states and outputs a smaller number of more reliable quantum states. It is considered by many experts to be one of the leading proposals for achieving fault tolerant quantum computation. Magic state distillation has also been used to argue that quantum contextuality may be the "magic ingredient" responsible for the power of quantum computers. Magic state distillation was first proposed by Emanuel Knill in 2004. A related proposal with detailed analysis was given by Sergey Bravyi and Alexei Kitaev in 2004. Thanks to the Gottesman –Knill theorem, it is known that some quantum operations (operations in the Clifford algebra) can be perfectly simulated in polynomial time on a probabilistic classical computer. In order to achieve universal quantum computation, a quantum computer must be able to perform operations outside this set. Magic state distillation achieves this, in principle, by concentrating the usefulness of imperfect resources, represented by mixed states, into states that are conducive for performing operations that are difficult to simulate classically. A variety of qubit magic state distillation routines and distillation routines for qubits with various advantages have been proposed. Stabilizer formalism. The Clifford  group consists of a set of formula_1-qubit operations generated by the gates (where "H" is Hadamard and "S" is formula_2) 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. Magic states. Magic states are purified from formula_1 copies of a mixed state formula_4. These states are typically provided via an ancilla to the circuit. A magic state for the formula_5 gate is formula_6 where formula_7. By combining (copies of) magic states with  Clifford gates, can be used to make a non-Clifford gate. Since Clifford gates combined with a non-Clifford gate are universal for quantum computation, magic states combined with Clifford gates are also universal. Purification algorithm for distilling |"M"〉. The first magic state distillation algorithm, invented by Sergey Bravyi and Alexei Kitaev, is a follows.