A Finite Presentation of CNOT-Dihedral Operators

Abstract

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 Proceedings QPL 2017, arXiv:1802.09737

References in corpus (5)

• Exact synthesis of multiqubit Clifford+T circuits
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
• Extracting verified decision procedures: DPLL and Resolution
• Rewriting modulo symmetric monoidal structure

Cited by in corpus (11)

• Phase Gadget Synthesis for Shallow Circuits
• On the CNOT-complexity of CNOT-PHASE circuits
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• A Complete Equational Theory for Quantum Circuits
• Formal Methods for Quantum Programs: A Survey
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Symbolic Synthesis of Clifford Circuits and Beyond
• Generators and Relations for Real Stabilizer Operators
• Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)
• Scalable Spider Nests (...Or How to Graphically Grok Transversal Non-Clifford Gates)
• A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits