Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.08696

Synthesis and Arithmetic of Single Qutrit Circuits

Amolak Ratan Kalra, Michele Mosca, Dinesh Valluri

Published Nov 15, 2023• 1 citation
arXivHTMLPDF

Abstract

In this paper we study single qutrit circuits consisting of words over the Clifford$+D$ cyclotomic gate set, where $D=\text{diag}(\pmξ^{a},\pmξ^{b},\pmξ^{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 $\mathbb{Z}[ξ, \frac{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 $\mathbb{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,\mathbb{Z}[ξ, \frac{1}χ])$ of $3 \times 3$ unitaries with entries in $\mathbb{Z}[ξ, \frac{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.

DOI
10.48550/arxiv.2311.08696

Related papers

Synthesis and Arithmetic of Single Qutrit Circuits

Amolak Ratan Kalra, Michele Mosca, Dinesh Valluri

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.

Quantum•Feb 26, 2025•4 citations

Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits

Andrew N. Glaudell, Neil J. Ross, John van de Wetering +1 more

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]$.

arXiv:2405.08136•Electronic Proceedings in Theoretical Computer Science•Aug 9, 2024•6 citations

Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Simon Forest, David Gosset, Vadym Kliuchnikov +1 more

We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.

arXiv:1501.04944•Journal of Mathematical Physics•Aug 1, 2015•44 citations

Clifford-cyclotomic Circuits

Linh Dinh

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.

•Aug 5, 2025•0 citations

Contributions to the Theory of Clifford-Cyclotomic Circuits

Linh Dinh, Neil J. Ross

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.

arXiv:2508.14674•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•0 citations

Multi-qutrit exact synthesis

Amolak Ratan Kalra, Manimugdha Saikia, Dinesh Valluri +2 more

We present an exact synthesis algorithm for qutrit unitaries in $\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2π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 $\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2π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$+\mathcal{D}$ over the multi-qutrit Clifford$+T$ gate set with at most two ancillas.

arXiv:2405.08147•May 13, 2024•1 citation
In this paper we study single qutrit circuits consisting of words over the Clifford+D+D+D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc)D=\text{diag}(\pmξ^{a},\pmξ^{b},\pmξ^{c})D=diag(±ξa,±ξb,±ξc), ξξξ is a primitive 999-th root of unity and a,b,ca,b,ca,b,c are integers. We characterize classes of qutrit unit vectors zzz with entries in Z[ξ,1χ]\mathbb{Z}[ξ, \frac{1}χ]Z[ξ,χ1​] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1−ξ,χ:= 1 - ξ,χ:=1−ξ, by acting an appropriate gate in Clifford+D+D+D. We do this by studying the notion of `derivatives mod 333' of an arbitrary element of Z[ξ]\mathbb{Z}[ξ]Z[ξ] and using it to study the smallest denominator exponent of HDzHDzHDz where HHH is the qutrit Hadamard gate and DDD. 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+D+D gates naturally arise as gates with sde 000 and 333 in the group U(3,Z[ξ,1χ])U(3,\mathbb{Z}[ξ, \frac{1}χ])U(3,Z[ξ,χ1​]) of 3×33 \times 33×3 unitaries with entries in Z[ξ,1χ]\mathbb{Z}[ξ, \frac{1}χ]Z[ξ,χ1​]. We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford+R+R+R and recover the previous exact synthesis algorithm in \cite{kmm}. The framework developed to formulate qutrit gate synthesis for Clifford+D+D+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.
It is known that the matrices that can be exactly represented by a multiqubit circuit over the Toffoli+Hadamard, Clifford+TTT, or, more generally, Clifford-cyclotomic gate set are precisely the unitary matrices with entries in the ring Z[1/2,ζk]\mathbb{Z}[1/2,\zeta_k]Z[1/2,ζk​], where kkk is a positive integer that depends on the gate set and ζk\zeta_kζk​ is a primitive 2k2^k2k-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 3k3^k3k by extending the classical qutrit gates XXX, CXCXCX, and CCXCCXCCX with the Hadamard gate HHH and the TkT_kTk​ gate Tk=diag(1,ωk,ωk2)T_k=\mathrm{diag}(1,\omega_k, \omega_k^2)Tk​=diag(1,ωk​,ωk2​), where ωk\omega_kωk​ is a primitive 3k3^k3k-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when k=1k=1k=1, and to the qutrit Clifford+TkT_kTk​ gate set when k>1k>1k>1. We then prove that a 3n×3n3^n\times 3^n3n×3n unitary matrix UUU can be represented by an nnn-qutrit circuit over the Clifford-cyclotomic gate set of degree 3k3^k3k if and only if the entries of UUU lie in the ring Z[1/3,ωk]\mathbb{Z}[1/3,\omega_k]Z[1/3,ωk​].
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.
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.
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.
We present an exact synthesis algorithm for qutrit unitaries in U3n(Z[1/3,e2πi/3])\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2πi/3}])U3n​(Z[1/3,e2πi/3]) over the Clifford+T+T+T gate set with at most one ancilla. This extends the already known result of qutrit metaplectic gates being a subset of Clifford+T+T+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])\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2πi/9}])U3n​(Z[1/3,e2πi/9]) over the Clifford+T+T+T gate set with at most 2 ancillas. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford+D+\mathcal{D}+D over the multi-qutrit Clifford+T+T+T gate set with at most two ancillas.