# The Classification of Clifford Gates over Qubits

Daniel Grier1 and Luke Schaeffer2

1University of Waterloo, Cheriton School of Computer Science
2University of Waterloo, Department of Combinatorics and Optimization

### Abstract

We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets.
The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.

### ► References

[1] Scott Aaronson, Daniel Grier, and Luke Schaeffer. The classification of reversible bit operations''. In 8th Innovations in Theoretical Computer Science Conference. Volume 67 of Leibniz International Proceedings in Informatics, pages 23:1–23:34. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2017).
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2017.23

[2] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation''. Physical Review A 52, 3457–3467 (1995).
https:/​/​doi.org/​10.1103/​PhysRevA.52.3457

[3] Yaoyun Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computing''. Quantum Information & Computation 3, 84–92 (2003).
https:/​/​doi.org/​10.26421/​QIC3.1-7

[4] Adam Bouland, Laura Mančinska, and Xue Zhang. Complexity classification of two-qubit commuting Hamiltonians''. In 31st Conference on Computational Complexity. Volume 50 of Leibniz International Proceedings in Informatics, pages 28:1–28:33. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2016).
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2016.28

[5] Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols. Characterization of universal two-qubit Hamiltonian''. Quantum Information & Computation 11, 19–39 (2011).
https:/​/​doi.org/​10.26421/​QIC11.1-2-3

[6] Adam Bouland and Scott Aaronson. Generation of universal linear optics by any beam splitter''. Physical Review A 89, 062316 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.89.062316

[7] Matthew Amy, Andrew N Glaudell, and Neil J Ross. Number-theoretic characterizations of some restricted Clifford+$T$ circuits''. Quantum 4, 252 (2020).
https:/​/​doi.org/​10.22331/​q-2020-04-06-252

[8] Daniel Gottesman. The Heisenberg representation of quantum computers'' (1998). arXiv:quant-ph/​9807006.
arXiv:quant-ph/9807006

[9] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits''. Physical Review A 70, 052328 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[10] Daniel Gottesman. Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997).
https:/​/​doi.org/​10.7907/​rzr7-dt72

[11] Peter W. Shor. Fault-tolerant quantum computation''. In Proceedings of 37th Conference on Foundations of Computer Science. Pages 56–65. (1996).
https:/​/​doi.org/​10.1109/​SFCS.1996.548464

[12] Andrew Steane. Multiple-particle interference and quantum error correction''. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551–2577 (1996).
https:/​/​doi.org/​10.1098/​rspa.1996.0136

[13] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.71.022316

[14] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. Measurement-based quantum computation on cluster states''. Physical Review A 68, 022312 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.68.022312

[15] Jonas T. Anderson. On the power of reusable magic states'' (2012). arXiv:1205.0289.
arXiv:1205.0289

[16] Panos Aliferis. Level reduction and the quantum threshold theorem''. PhD thesis. California Institute of Technology. (2007).
https:/​/​doi.org/​10.7907/​3ZM6-HE29

[17] N. Cody Jones, Rodney Van Meter, Austin G. Fowler, Peter L. McMahon, Jungsang Kim, Thaddeus D. Ladd, and Yoshihisa Yamamoto. Layered architecture for quantum computing''. Physical Review X 2, 031007 (2012).
https:/​/​doi.org/​10.1103/​PhysRevX.2.031007

[18] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the Clifford group''. IEEE Transactions on Information Theory 67, 4546–4563 (2021).
https:/​/​doi.org/​10.1109/​TIT.2021.3081415

[19] Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations''. IEEE Transactions on Information Theory 64, 4729–4738 (2018).
https:/​/​doi.org/​10.1109/​TIT.2018.2825602

[20] Peter Selinger. Generators and relations for n-qubit Clifford operators''. Logical Methods in Computer Science 11 (2015).
https:/​/​doi.org/​10.2168/​LMCS-11(2:10)2015

[21] Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2)''. Physical Review A 68, 042318 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.68.042318

[22] Maarten Van den Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond''. Quantum Information & Computation 10, 258–271 (2010).
https:/​/​doi.org/​10.26421/​QIC10.3-4-6

[23] Andrew N Glaudell, Neil J Ross, and Jacob M Taylor. Optimal two-qubit circuits for universal fault-tolerant quantum computation''. npj Quantum Information 7, 1–11 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00424-z

[24] Wikipedia. Hyperoctahedral group''. http:/​/​en.wikipedia.org/​w/​index.php?title=Hyperoctahedral%20group&oldid=1079812980 (2022). [Online; accessed 22-April-2022].
http:/​/​en.wikipedia.org/​w/​index.php?title=Hyperoctahedral%20group&oldid=1079812980

[25] Daniel Gottesman. Theory of fault-tolerant quantum computation''. Physical Review A 57, 127 (1998).
https:/​/​doi.org/​10.1103/​PhysRevA.57.127

[26] Peter Selinger. Dagger compact closed categories and completely positive maps''. Electronic Notes in Theoretical Computer Science 170, 139–163 (2007).
https:/​/​doi.org/​10.1016/​j.entcs.2006.12.018

[27] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. Lower bounds on the non-Clifford resources for quantum computations''. Quantum Science and Technology 5, 035009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8963

[28] Daniel Jonathan and Martin B Plenio. Entanglement-assisted local manipulation of pure quantum states''. Physical Review Letters 83, 3566–3569 (1999).
https:/​/​doi.org/​10.1103/​PhysRevLett.83.3566

[29] Emil L. Post. The two-valued iterative systems of mathematical logic''. Number 5 in Annals of Mathematics Studies. Princeton University Press. (1941).
https:/​/​doi.org/​10.1515/​9781400882366

[30] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and $T$ gates''. Quantum Information & Computation 13, 607–630 (2013).
https:/​/​doi.org/​10.26421/​QIC13.7-8-4

[31] Brett Giles and Peter Selinger. Exact synthesis of multiqubit Clifford+$T$ circuits''. Physical Review A 87, 032332 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.032332

[32] G. E. Wall. On the conjugacy classes in the unitary, symplectic and orthogonal groups''. Journal of the Australian Mathematical Society 3, 1–62 (1963).
https:/​/​doi.org/​10.1017/​S1446788700027622

### Cited by

[1] David Gross, Sepehr Nezami, and Michael Walter, "Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations", Communications in Mathematical Physics 385 3, 1325 (2021).

[2] Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh, "Complexity Classification of Conjugated Clifford Circuits", arXiv:1709.01805, (2017).

[3] Matthew Amy, Andrew N. Glaudell, and Neil J. Ross, "Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits", Quantum 4, 252 (2020).

[4] Joel Klassen and Barbara M. Terhal, "Two-local qubit Hamiltonians: when are they stoquastic?", Quantum 3, 139 (2019).

[5] Patrick Rall, "Signed quantum weight enumerators characterize qubit magic state distillation", arXiv:1702.06990, (2017).

[6] Thomas Hebdige and David Jennings, "On the classification of two-qubit group orbits and the use of coarse-grained 'shape' as a superselection property", Quantum 3, 119 (2019).

The above citations are from SAO/NASA ADS (last updated successfully 2023-02-04 12:46:17). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-04 12:46:15).