Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

Abstract

Kliuchnikov, Maslov, and Mosca proved in 2012 that a $2\times 2$ unitary matrix $V$ can be exactly represented by a single-qubit Clifford+$T$ circuit if and only if the entries of $V$ belong to the ring $\mathbb{Z}[1/\sqrt{2},i]$. Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+$T$ circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+$T$ circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+$T$ circuits by considering unitary matrices over subrings of $\mathbb{Z}[1/\sqrt{2},i]$. We focus on the subrings $\mathbb{Z}[1/2]$, $\mathbb{Z}[1/\sqrt{2}]$, $\mathbb{Z}[1/i\sqrt{2}]$, and $\mathbb{Z}[1/2,i]$, and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates $\{X,CX,CCX\}$ with an analogue of the Hadamard gate and an optional phase gate.

References in corpus (23)

• Elementary gates for quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Exact synthesis of multiqubit Clifford+T circuits
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Asymptotically Optimal Topological Quantum Compiling
• Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
• Efficient synthesis of probabilistic quantum circuits with fallback
• Real Randomized Benchmarking
• T-count optimization and Reed-Muller codes
• Generators and relations for n-qubit Clifford operators
• Generation of Universal Linear Optics by Any Beamsplitter
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• A 2 rebit gate universal for quantum computing
• Super-Golden-Gates for PU(2)
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
• A Finite Presentation of CNOT-Dihedral Operators
• A ZX-Calculus with Triangles for Toffoli-Hadamard, Clifford+T, and Beyond
• Y-Calculus: A Language for Real Matrices Derived from the ZX-Calculus
• Complexity of the XY antiferromagnet at fixed magnetization
• Generators and relations for the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$

Cited by in corpus (13)

• The Classification of Clifford Gates over Qubits
• The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality
• Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes
• Completeness of the ZH-calculus
• Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits
• With a Few Square Roots, Quantum Computing is as Easy as Π
• Generators and Relations for Un(Z[1/2,i])
• Generators and Relations for Real Stabilizer Operators
• Generators and Relations for the Group On(Z[1/2])
• Generators and Relations for 3-Qubit Clifford+CS Operators
• Contributions to the Theory of Clifford-Cyclotomic Circuits
• A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits
• Free Quantum Computing