nLab magic state (Rev #2)

Context

Quantum systems

Computation

\tableofcontents

Idea

In quantum computing and quantum information theory, magic states are a kind of quantum states that are (envisioned to be) used as a quantum resource in order to retain viability of quantum error correction by surface codes or similar means.

The Clifford group of quantum gates on $n$ qbits (the normalizer of the Pauli group in $U(2^n)$ , generated by the Hadamard gate $H$ , the phase gate $S = diag(1,\mathrm{i})$ and the CNOT gate) is computationally weak: By the Gottesman-Knill theorem, Clifford quantum circuits acting on stabilizer states and followed by Pauli quantum measurements are efficiently simulable on a classical computer. But adjoining any one non-Clifford gate yields a universal gate set.

The prominent choice of that extra non-Clifford gate is the T-gate $T = \mathrm{diag}(1, e^{\pi \mathrm{i}/4})$ (but there are other reasonable choices, like the CCZ gate): The set Clifford+ $T$ generates, up to global phase, a dense subgroup of $SU(2^n)$, so that every quantum circuit is efficiently approximated by Clifford+ $T$ circuits (by the Solovay-Kitaev theorem).

The catch is that:

The prominent topological quantum error-correcting codes like the surface code (lattice quantum simulations of topological order) protect only Clifford gates. And this is a problem of principle (Eastin & Knill 2009, Bravyi & König 2013).
Also actual topological quantum computation as long as its anyons are only of Ising type (such as expected, but not established, for the $\nu = 5/2$ FQH states) yields exactly only the Clifford gates (Bravyi 2006, Nayak et al. 2008, §IV.A).

The now standard strategy to work around this problem, trades the missing gate for a resource state: $T$ -gates are enacted by gate teleportation, consuming magic states $\vert A \rangle = T \vert + \rangle$ via a CNOT, a $Z$-measurement and a classically controlled $S$ -correction (which are all Clifford operations).

These magic states, in turn, are encoded without protection (“state injection”) and then purified by magic state distillation (Bravyi & Kitaev 2005), a protocol which uses only Clifford operations and measurements to turn many noisy copies into fewer, better ones.

The resulting architecture — the surface code as a protected “Clifford substrate”, fed with non-Clifford resources by dedicated “magic state factories” — is expensive: A $T$ -gate costs a few hundred times a Clifford gate in space-time overhead (Campbell, Terhal & Vuillot 2017, §II.5), and in the estimate of Fowler et al. 2012 for factoring, magic state production occupies over 94% of the physical qubits.

Accordingly, the “ $T$ -count” (number of T-gates in a quantum circuit) has become a standard cost measure of quantum algorithms, and much current work aims to reduce this overhead by various proposed methods:

by more efficient distillation (Litinski 2019);
by magic state cultivation, which grows a $T$ -state inside a single surface-code patch at roughly the cost of a lattice-surgery CNOT and may make distillation unnecessary in practice (Gidney, Shutty & Jones 2024);
by circumventing the 2-dimensional no-go theorem, either via 3-dimensional codes with transversal $T$ (Bombín 2015) or via non-constant-depth protocols on the surface code itself (Brown 2020). For review see Terhal 2015, §II.7, Campbell, Terhal & Vuillot 2017.

Although efficiency of magic state architectures is improving consistently [7, 8] approaching believed fundamental limits [9], large resource demands remain a serious obstacle for near-future architectures.

Related concepts

Bell state

References

Review:

Barbara Terhal: Quantum error correction for quantum memories, Rev. Mod. Phys. 87 (2015) 307 [[doi:10.1103/RevModPhys.87.307](https://doi.org/10.1103/RevModPhys.87.307), arXiv:1302.3428]
Earl T. Campbell, Barbara M. Terhal, Christophe Vuillot: Roads towards fault-tolerant universal quantum computation, Nature 549 (2017) 172–179 [doi:10.1038/nature23460, arXiv:1612.07330]