nLab magic state

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})$: 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:

1. by more efficient distillation (Litinski 2019);

2. 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);

3. 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.

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, 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]

See also:

• Wikipedia: Magic (quantum information)

• Wikipedia: Magic state distillation

No-go theorems for transversal and topologically protected gates:

• Bryan Eastin, Emanuel Knill: Restrictions on transversal encoded quantum gate sets, Phys. Rev. Lett. 102 (2009) 110502 [doi:10.1103/PhysRevLett.102.110502, arXiv:0811.4262]

• Sergey Bravyi, Robert König: Classification of topologically protected gates for local stabilizer codes, Phys. Rev. Lett. 110 (2013) 170503 [doi:10.1103/PhysRevLett.110.170503, arXiv:1206.1609]

The analogous situation for anyons:

• Michael Freedman, Michael Larsen, Zhenghan Wang: A modular functor which is universal for quantum computation, Commun. Math. Phys. 227 (2002) 605–622 [doi:10.1007/s002200200645, arXiv:quant-ph/0001108]

• Sergey Bravyi: Universal quantum computation with the $\nu=5/2$ fractional quantum Hall state, Phys. Rev. A 73 (2006) 042313 [doi:10.1103/PhysRevA.73.042313, arXiv:quant-ph/0511178]

• Chetan Nayak, Steven H. Simon, Ady Stern, Michael Freedman, Sankar Das Sarma: Non-Abelian anyons and topological quantum computation, Rev. Mod. Phys. 80 (2008) 1083 [doi:10.1103/RevModPhys.80.1083, arXiv:0707.1889]

On magic states and their distillation for the surface code:

• Sergey Bravyi, Alexei Kitaev: Universal quantum computation with ideal Clifford gates and noisy ancillas, Phys. Rev. A 71 (2005) 022316 [doi:10.1103/PhysRevA.71.022316, arXiv:quant-ph/0403025]

• Robert Raussendorf, Jim Harrington, Kovid Goyal: Topological fault-tolerance in cluster state quantum computation, New J. Phys. 9 (2007) 199 [doi:10.1088/1367-2630/9/6/199, arXiv:quant-ph/0703143]

• Austin G. Fowler, Ashley M. Stephens, Peter Groszkowski: High threshold universal quantum computation on the surface code, Phys. Rev. A 80 (2009) 052312 [doi:10.1103/PhysRevA.80.052312, arXiv:0803.0272]

• Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland: Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86 (2012) 032324 [doi:10.1103/PhysRevA.86.032324, arXiv:1208.0928]

• Daniel Litinski: Magic state distillation: Not as costly as you think, Quantum 3 (2019) 205 [doi:10.22331/q-2019-12-02-205, arXiv:1905.06903]

• Craig Gidney, Noah Shutty, Cody Jones: Magic state cultivation: growing T states as cheap as CNOT gates [arXiv:2409.17595]

Circumventing the 2-dimensional no-go theorem:

• Héctor Bombín: Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New J. Phys. 17 (2015) 083002 [doi:10.1088/1367-2630/17/8/083002, arXiv:1311.0879]

• Benjamin J. Brown: A fault-tolerant non-Clifford gate for the surface code in two dimensions, Science Advances 6 (2020) eaay4929 [doi:10.1126/sciadv.aay4929, arXiv:1903.11634]