Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2×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 Z[1/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 Z[1/2,i] . We focus on the subrings Z[1/2] , Z[1/2] , Z[1/i2] , and 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.
Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2×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 Z[1/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 Z[1/2,i] . We focus on the subrings Z[1/2] , Z[1/2] , Z[1/i2] , and 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.
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and 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. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.
We prove that a unitary matrix has an exact representation over the Clifford+T gate set with local ancillas if and only if its entries are in the ring Z[21,i]. Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+T circuit from any such n-qubit operator. We also characterize the Clifford+T operators that can be represented without ancillas.
It is known that the matrices that can be exactly represented by a multiqubit circuit over the Toffoli+Hadamard, Clifford+T, or, more generally, Clifford-cyclotomic gate set are precisely the unitary matrices with entries in the ring Z[1/2,ζk], where k is a positive integer that depends on the gate set and ζk is a primitive 2k-th root of unity. In the present paper, we establish an analogous correspondence for qutrits. We define the multiqutrit Clifford-cyclotomic gate set of degree 3k by extending the classical qutrit gates X, CX, and CCX with the Hadamard gate H and the Tk gate Tk=diag(1,ωk,ωk2), where ωk is a primitive 3k-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when k=1, and to the qutrit Clifford+Tk gate set when k>1. We then prove that a 3n×3n unitary matrix U can be represented by an n-qutrit circuit over the Clifford-cyclotomic gate set of degree 3k if and only if the entries of U lie in the ring Z[1/3,ωk].
Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, omega^dagger H, and S. All of these gates have matrix entries in the ring Z[1/2,i], the smallest subring of the complex numbers containing 1/2 and i. Amy, Glaudell, and Ross proved the converse, i.e., any unitary matrix with entries in Z[1/2,i] can be realized by a quantum circuit over the above gate set using at most one ancilla. In this paper, we give a finite presentation by generators and relations of U_n(Z[1/2,i]), the group of unitary nxn-matrices with entries in Z[1/2,i].
We describe a new method for approximating an arbitrary n qubit unitary with precision ε using a Clifford and T circuit with O(4nn(log(1/ε)+n)) gates. The method is based on rounding off a unitary to a unitary over the ring Z[i,1/2] and employing exact synthesis. We also show that any n qubit unitary over the ring Z[i,1/2] with entries of the form (a+b2+ic+id2)/2k can be exactly synthesized using O(4nnk) Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring O(32nnk) elementary gates.
Let n be a positive integer divisible by 8.The Clifford-cyclotomic gate set G n consists of the Clifford gates, together with a z-rotation of order n.It is easy to show that, if a circuit over G n represents a unitary matrix U, then the entries of U must lie in R n , the smallest subring of C containing 1/2 and exp(2πi/n).The converse implication, that every unitary U with entries in R n can be represented by a circuit over G n , is harder to show, but it was recently proved to be true when n = 2 k .In that case, k -2 ancillas suffice to synthesize a circuit for U, which is known to be minimal for k = 3, but not for larger values of k.In the present paper, we make two contributions to the theory of Clifford-cyclotomic circuits.Firstly, we improve the existing synthesis algorithm by showing that, when n = 2 k and k ≥ 4, only k -3 ancillas are needed to synthesize a circuit for U, which is minimal for k = 4. Secondly, we extend the existing synthesis algorithm to the case of n = 3 • 2 k with k ≥ 3.