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

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

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

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

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

[6] Alfredo Guevara and Yangrui Hu, "Celestial Quantum Error Correction I: Qubits from Noncommutative Klein Space", arXiv:2312.16298, (2023).

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

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

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

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

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

[12] 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 Crossref's cited-by service (last updated successfully 2024-05-19 16:19:26) and SAO/NASA ADS (last updated successfully 2024-05-19 16:19:27). 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.