A Finite Presentation of CNOT-Dihedral Operators

Matthew Amy
(Institute for Quantum Computing and David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada)
Jianxin Chen
(Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, USA)
Neil J. Ross
(Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, USA)

We give a finite presentation by generators and relations of the unitary operators expressible over the {CNOT, T, X} gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form.

By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT, T} gate set as a corollary.

In Bob Coecke and Aleks Kissinger: Proceedings 14th International Conference on Quantum Physics and Logic (QPL 2017), Nijmegen, The Netherlands, 3-7 July 2017, Electronic Proceedings in Theoretical Computer Science 266, pp. 84–97.
Published: 27th February 2018.

ArXived at: http://dx.doi.org/10.4204/EPTCS.266.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org