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.
 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).
 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).
 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).
 Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols. ``Characterization of universal two-qubit Hamiltonian''. Quantum Information & Computation 11, 19–39 (2011).
 Matthew Amy, Andrew N Glaudell, and Neil J Ross. ``Number-theoretic characterizations of some restricted Clifford+$T$ circuits''. Quantum 4, 252 (2020).
 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).
 Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal Clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005).
 Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. ``Measurement-based quantum computation on cluster states''. Physical Review A 68, 022312 (2003).
 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).
 Sergey Bravyi and Dmitri Maslov. ``Hadamard-free circuits expose the structure of the Clifford group''. IEEE Transactions on Information Theory 67, 4546–4563 (2021).
 Dmitri Maslov and Martin Roetteler. ``Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations''. IEEE Transactions on Information Theory 64, 4729–4738 (2018).
 Jeroen Dehaene and Bart De Moor. ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2)''. Physical Review A 68, 042318 (2003).
 Maarten Van den Nest. ``Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond''. Quantum Information & Computation 10, 258–271 (2010).
 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).
 Wikipedia. ``Hyperoctahedral group''. http://en.wikipedia.org/w/index.php?title=Hyperoctahedral%20group&oldid=1079812980 (2022). [Online; accessed 22-April-2022].
 Peter Selinger. ``Dagger compact closed categories and completely positive maps''. Electronic Notes in Theoretical Computer Science 170, 139–163 (2007).
 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).
 Daniel Jonathan and Martin B Plenio. ``Entanglement-assisted local manipulation of pure quantum states''. Physical Review Letters 83, 3566–3569 (1999).
 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).
 G. E. Wall. ``On the conjugacy classes in the unitary, symplectic and orthogonal groups''. Journal of the Australian Mathematical Society 3, 1–62 (1963).
 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).
 Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh, "Complexity Classification of Conjugated Clifford Circuits", arXiv:1709.01805.
 Matthew Amy, Andrew N. Glaudell, and Neil J. Ross, "Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits", arXiv:1908.06076.
 Joel Klassen and Barbara M. Terhal, "Two-local qubit Hamiltonians: when are they stoquastic?", arXiv:1806.05405.
 Patrick Rall, "Signed quantum weight enumerators characterize qubit magic state distillation", arXiv:1702.06990.
 Thomas Hebdige and David Jennings, "On the classification of two-qubit group orbits and the use of coarse-grained 'shape' as a superselection property", arXiv:1804.09967.
The above citations are from SAO/NASA ADS (last updated successfully 2022-10-05 02:37:35). 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 2022-10-05 02:37:34).
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.