The Classification of Clifford Gates over Qubits

Daniel Grier; Luke Schaeffer

doi:10.22331/q-2022-06-13-734

The Classification of Clifford Gates over Qubits

Daniel Grier¹ and Luke Schaeffer²

¹University of Waterloo, Cheriton School of Computer Science
²University of Waterloo, Department of Combinatorics and Optimization

Published:	2022-06-13, volume 6, page 734
Eprint:	arXiv:1603.03999v4
Doi:	https://doi.org/10.22331/q-2022-06-13-734
Citation:	Quantum 6, 734 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

Featured image: Classification of multi-qubit Clifford classes.

► BibTeX data

@article{Grier2022classificationof,
  doi = {10.22331/q-2022-06-13-734},
  url = {https://doi.org/10.22331/q-2022-06-13-734},
  title = {The {C}lassification of {C}lifford {G}ates over {Q}ubits},
  author = {Grier, Daniel and Schaeffer, Luke},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {734},
  month = jun,
  year = {2022}
}

► 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] Senrui Chen, Zhihan Zhang, Liang Jiang, and Steven T. Flammia, "Efficient Self-Consistent Learning of Gate Set Pauli Noise", PRX Quantum 7 1, 010305 (2026).

[2] Ning Bao and Gavin S. Hartnett, "Twisty-puzzle-inspired approach to Clifford synthesis", Physical Review A 109 3, 032409 (2024).

[3] Chin-Yen Lee, Wei-Hsuan Yu, Yung-Ning Peng, and Ching-Jui Lai, "On character table of Clifford groups", Journal of Mathematical Physics 66 2, 022201 (2025).

[4] Marc Serra-Peralta, Mackenzie H. Shaw, and Barbara M. Terhal, "Decoding across Transversal Clifford Gates in the Surface Code", PRX Quantum 7 1, 010335 (2026).

[5] Halima Giovanna Ahmad, Caleb Jordan, Roald van den Boogaart, Daan Waardenburg, Christos Zachariadis, Pasquale Mastrovito, Asen Lyubenov Georgiev, Domenico Montemurro, Giovanni Piero Pepe, Marten Arthers, Alessandro Bruno, Francesco Tafuri, Oleg Mukhanov, Marco Arzeo, and Davide Massarotti, "Investigating the Individual Performances of Coupled Superconducting Transmon Qubits", Condensed Matter 8 1, 29 (2023).

[6] Vincent G. Harris and Parisa Andalib, "Modern quantum materials", Frontiers in Materials 11, 1343005 (2024).

[7] Jakub Czartowski and Karol Życzkowski, "Quantum pushforward designs", Physical Review A 111 3, 032433 (2025).

[8] Alfredo Guevara and Yangrui Hu, "Celestial quantum error correction: I. Qubits from noncommutative Klein space", Classical and Quantum Gravity 42 16, 165006 (2025).

[9] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig, "Single-qubit gate teleportation provides a quantum advantage", Quantum 8, 1548 (2024).

[10] Yiming Zhang, Shuai Xu, Jing Liu, Wei Jin, Georgios Lefkidis, Wolfgang Hübner, and Chun Li, "Optically Driven Both Classical and Quantum Unary, Binary, and Ternary Logic Gates on Co-Decorated Graphene Nanoflakes", The Journal of Physical Chemistry Letters 14 36, 8107 (2023).

[11] Sandeep Suresh Cranganore, Vincenzo De Maio, Ivona Brandic, and Ewa Deelman, "Paving the way to hybrid quantum–classical scientific workflows", Future Generation Computer Systems 158, 346 (2024).

[12] Lucy Byles, Ewan Forbes, and Jiannis K Pachos, "Demonstration of magic state power of D ( S 3 ) anyons with two qudits", New Journal of Physics 28 4, 044501 (2026).

[13] Cristian Márquez, Daniel Sierra-Sosa, and Kelly Garcés, "A Teleportation Protocol Variant for Single-QPU Benchmarking", IEEE Access 13, 209266 (2025).

[14] Marcell D. Kovács, Christopher J. Turner, Lluis Masanes, and Arijeet Pal, "Operator space fragmentation in perturbed Floquet-Clifford circuits", Quantum 10, 2107 (2026).

[15] Zhaohui Yang, Dawei Ding, Chenghong Zhu, Jianxin Chen, and Yuan Xie, 2025 62nd ACM/IEEE Design Automation Conference (DAC) 1 (2025) ISBN:979-8-3315-0304-8.

[16] K. A. Vidya and K. Venugopal, "Efficient domination problem: a quantum computing approach", The Journal of Supercomputing 81 15, 1461 (2025).

[17] 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).

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

[19] Nyirahafashimana Valentine, Nurisya Mohd Shah, Umair Abdul Halim, Sharifah Kartini Said Husain, and Ahmed Jellal, "Transforming qubits via quasi-geometric approaches", arXiv:2407.07562, (2024).

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

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

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

[23] M. Amy, M. Crawford, A. N. Glaudell, M. L. Macasieb, S. S. Mendelson, and N. J. Ross, "Catalytic Embeddings of Quantum Circuits", arXiv:2305.07720, (2023).

[24] 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).

[25] Sandeep Suresh Cranganore, Vincenzo De Maio, Ivona Brandic, and Ewa Deelman, "Paving the Way to Hybrid Quantum-Classical Scientific Workflows", arXiv:2404.10389, (2024).

[26] David Winderl, Qunsheng Huang, Arianne Meijer-van de Griend, and Richie Yeung, "Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus", arXiv:2309.08972, (2023).

[27] Kyle Gulshen and Tali Kaufman, "Symmetric Self-Dual Quantum Codes on High Dimensional Expanders", arXiv:2510.07864, (2025).

[28] Mulundano Machiya, Matt Menickelly, Paul Hovland, and Ji Liu, "MonteQ: A Monte Carlo Tree Search Based Quantum Circuit Synthesis Framework", arXiv:2604.19029, (2026).

[29] Muhammad Erew and Moshe Goldstein, "Extremizing Measures of Magic on Pure States by Clifford-stabilizer States", arXiv:2512.19657, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 20:41:50) and SAO/NASA ADS (last updated successfully 2026-08-12 20:41:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.