nLab Sandbox

This nLab page is for developing preliminary notes or making typographical experiments, etc. It may be edited by anybody, anytime. But you don’t necessarily need to delete other people’s ongoing notes here in order to add your own. In any case, overwritten edits may always be recovered from the page history.

If this edit page here is seemingly locked by “Anonymous”, just break the lock, as it is just caused by bot traffic. If the page is locked by an actual user, there is also the alternative Sandbox2.

---

Non-Clifford gates and magic states

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.

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]

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]