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. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.266.5 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |