What are magic states?

Question

I wonder what are magic states, and a magic state gadget. While I'm reading a paper, these terms frequently appear.

Answer 1

Magic states are certain states that have very nice properties with respect to fault-tolerant quantum computation.

In the vast landscape of quantum gates, there is a crude but useful distinction to be made between Clifford gates and all other gates (also referred to as the inspired non-Clifford gates). The set of Clifford gates is in technical terms the normalizer of the Pauli group, which basically means that it's the set of operations that map the set of Pauli eigenstates to the set of Pauli eigenstates - as the Pauli operators and its eigenstates are very important in quantum computation, we also care deeply about the Clifford gates.

There is another reason why we care about Clifford gates. In the scope of Quantum Error correction (specifically stabilizer codes and Fault-tolerance), all Clifford operations on stabilizer codes can be implemented transversally. This is a certain way of implementing (logical) operations on codes that are more or less 'the most easy way' of fault-tolerant - making them highly desirable.

Unfortunately it's impossible (as shown here) to have a complete universal gateset of operations with only transversal implementations, which means that at least one operation in the universal gateset needs to be implemented differently. As is often (but not necessarily) the choice, the set of Clifford operations (or rather, a generating set) is chosen as the transversal gates, and one other (non-Clifford) gate is implemented differently.

Implementing these non-clifford gates in a fault-tolerant manner is very tough and costly - there exist some methods that are on paper fault-tolerant, but lack implementability in one way or another. Magic states are a way of circumventing the need for non-Clifford gates by preparing certain states that kind of 'encode' the non-Clifford action into the state. Intuitively, you can think of this as applying all the necessary non-Clifford gates in a computation in advance, resulting in the magic states; the rest of the computation can then be performed by using only Clifford gates, making the fault-tolerant implementation containable.

Without a reference I cannot be completely sure what is meant by a 'magic state gadget', but I think the authors are referring to a gadget that would perform magic state distillation. Such a procedure produces pure magic states from noisy magic states - it was shown that this can be performed in a reasonably scalable fashion, and moreover in a fault-tolerant fashion. This gives a blue print of a fault-tolerant quantum computer with only Clifford gates (and the magic state distillation gadget).

Note that one needs a lot of magic states to perform computations - designs of quantum computers with magic states will most likely have the vast majority of its usable qubits be used for the distillation of magic states - the actual computation will almost be 'an afterthought'.

As a closing note, it may very well be that at some point all we care about in quantum computing resources is the distillation of magic states. This is of course an oversimplification, but I use it to emphasize the possible importance of these states.

Answer 2

In addition to the accepted answer and @user1271772's examples, here is a circuit primitive referred to explicitly as a "T-gate gadget" in [1] (originally appearing in [2]):

where application of the $S$ gate is conditioned on measuring a "1" on the ancilla. The way this works is, for $|A\rangle = \frac{1}{\sqrt{2}} (|0\rangle + e^{i\pi/4} |1\rangle)$, an input state $| \psi \rangle = a|0\rangle + b|1\rangle$ coming in from the left is transformed like:

$$ (a|0\rangle + b|1\rangle)(|0\rangle + e^{i\pi/4} |1\rangle) \rightarrow a|00 \rangle + a e^{i\pi/4} |01 \rangle + b|11\rangle + b e^{i\pi/4}|10 \rangle \\ = (a|0 \rangle + b e^{i\pi/4} |1\rangle )|0\rangle + (a e^{i\pi/4} |0\rangle + b|1\rangle)|1\rangle $$

If the ancilla is measured as "0", the input state is projected onto $(a|0 \rangle + b e^{i\pi/4} |1\rangle ) = T|\psi\rangle$ and the gate succeeds. If the ancilla is measured as "1" you apply an $S$ gate on the input register to get

$$ S(a e^{i\pi/4} |0\rangle + b|1\rangle) = (a e^{i\pi/4} |0\rangle + e^{i\pi/2} b|1\rangle) = e^{i\pi/4} (a |0\rangle + e^{i\pi/4} b|1\rangle) = e^{i\pi/4} T |\psi \rangle $$

which recovers the desired $T$ gate up to a global phase.

This process falls under the umbrella of gate teleportation (based on normal quantum teleportation) and basically lets you apply non-clifford gates if you have access to states that contain the essential information about the gate you want to apply - for instance, $|A\rangle = T\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ contains the effects of the $T$ gate that we want to apply.

---

[1] Bravyi, S., & Gosset, D. (2016). Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116(25), 250501.

[2] Zhou, X., Leung, D. W., & Chuang, I. L. (2000). Methodology for quantum logic gate construction. Physical Review A, 62(5), 052316.

Answer 3

Consider a quantum computer that can:

• Prepare qubits in state $|0\rangle$
• Apply unitary gates from the Clifford group
• Measure qubits in the $X$, $Y$, and $Z$ bases

This seems ideal because:

• We know how to implement all three functionalities quite easily (compared to more complicated gates or measurements)
• We can design algorithms for such a quantum computer quite easily, since all gates and measurements are quite fundamental operations that everyone working in quantum information knows and understands.

But, the above quantum computer is not universal!

You just need one more functionality to make the above quantum computer universal though:

• Be able to prepare a magic state

Examples of magic states are (here I give $H$-type and $T$-type magic states):

\begin{align} |H\rangle &\equiv \cos(\frac{\pi}{8})|0\rangle + \sin(\frac{\pi}{8})|1\rangle,\tag{1} \\ |T\rangle &\equiv\cos(\beta)|0\rangle + e^{i\pi/4}\sin(\beta)|1\rangle, \beta\equiv\frac{1}{2}\arccos(\frac{1}{\sqrt{3}}).\tag{2} \end{align}

The above example is not unique. In fact to make any universal quantum computer, you need to be able to prepare at least one magic state.

The term "magic state" was introduced in 2004 by Bravyi and Kitaev.