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 $\mathbb{Z}[1/2,\zeta_k]$, where $k$ is a positive integer that depends on the gate set and $\zeta_k$ is a primitive $2^k$-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 $3^k$ by extending the classical qutrit gates $X$, $CX$, and $CCX$ with the Hadamard gate $H$ and the $T_k$ gate $T_k=\mathrm{diag}(1,\omega_k, \omega_k^2)$, where $\omega_k$ is a primitive $3^k$-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when $k=1$, and to the qutrit Clifford+$T_k$ gate set when $k>1$. We then prove that a $3^n\times 3^n$ unitary matrix $U$ can be represented by an $n$-qutrit circuit over the Clifford-cyclotomic gate set of degree $3^k$ if and only if the entries of $U$ lie in the ring $\mathbb{Z}[1/3,\omega_k]$.
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].
In this paper we study single qutrit circuits consisting of words over the Clifford+D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc), ξ is a primitive 9-th root of unity and a,b,c are integers. We characterize classes of qutrit unit vectors z with entries in Z[ξ,χ1] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1−ξ, by acting an appropriate gate in Clifford+D. We do this by studying the notion of `derivatives mod 3' of an arbitrary element of Z[ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D. In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford+D gates naturally arise as gates with sde 0 and 3 in the group U(3,Z[ξ,χ1]) of 3×3 unitaries with entries in Z[ξ,χ1]. We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford+R and recover the previous exact synthesis algorithm in \cite{kmm}. The framework developed to formulate qutrit gate synthesis for Clifford+D extends to qudits of arbitrary prime power.
In this paper we study single qutrit circuits consisting of words over the Clifford +D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc) , ξ is a primitive 9 -th root of unity and a,b,c are integers. We characterize classes of qutrit unit vectors z with entries in Z[ξ,1χ] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1–ξ, by acting an appropriate gate in Clifford +D . We do this by studying the notion of `derivatives mod 3 ' of an arbitrary element of Z[ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D . In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford +D gates naturally arise as gates with sde 0 and 3 in the group U(3,Z[ξ,1χ]) of 3×3 unitaries with entries in Z[ξ,1χ] . We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford +R and recover the previously known exact synthesis algorithm of Kliuchnikov, Maslov, Mosca (2012). The framework developed to formulate qutrit gate synthesis for Clifford +D extends to qudits of arbitrary prime power.
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.
Circuit design is an important aspect of quantum computation theory, and the question of constructing a circuit that exactly represents a given operator is prominent in the research area. Let n be a positive integer divisible by 8. The Clifford-cyclotomic gate set \mathcal{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 \mathcal{G}_n represents a unitary matrix U, then the entries of U must lie in \mathcal{R}_n, the smallest subring of \mathbb{C} containing 1/2 and \mathrm{exp}(2\pi i/n). The converse implication, that every unitary U with entries in \mathcal{R}_n can be represented by a circuit over \mathcal{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 thesis, 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\geq 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\cdot 2^k with k\geq 3.
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.
We present an exact synthesis algorithm for qutrit unitaries in U3n(Z[1/3,e2πi/3]) over the Clifford+T gate set with at most one ancilla. This extends the already known result of qutrit metaplectic gates being a subset of Clifford+T gate set with one ancilla. As an intermediary step, we construct an algorithm to convert 3-level unitaries into multiply-controlled gates, analogous to Gray codes converting 2-level unitaries into multiply-controlled gates. Finally, using catalytic embeddings, we present an algorithm to exactly synthesize unitaries U3n(Z[1/3,e2πi/9]) over the Clifford+T gate set with at most 2 ancillas. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford+D over the multi-qutrit Clifford+T gate set with at most two ancillas.