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:2405.08147

Multi-qutrit exact synthesis

Amolak Ratan Kalra, Manimugdha Saikia, Dinesh Valluri, Sam Winnick, Jon Yard

Published May 13, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2405.08147

Related papers

Qutrit Metaplectic Gates Are a Subset of Clifford+T

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

A popular universal gate set for quantum computing with qubits is Clifford+T, as this can be readily implemented on many fault-tolerant architectures. For qutrits, there is an equivalent T gate, that, like its qubit analogue, makes Clifford+T approximately universal, is injectable by a magic state, and supports magic state distillation. However, it was claimed that a better gate set for qutrits might be Clifford+R, where R=diag(1,1,-1) is the metaplectic gate, as certain protocols and gates could more easily be implemented using the R gate than the T gate. In this paper we show that when we have at least two qutrits, the qutrit Clifford+R unitaries form a strict subset of the Clifford+T unitaries, by finding a direct decomposition of $R \otimes \mathbb{I}$ as a Clifford+T circuit and proving that the T gate cannot be exactly synthesized in Clifford+R. This shows that in fact the T gate is at least as powerful as the R gate, up to a constant factor. Moreover, we additionally show that it is impossible to find a single-qutrit Clifford+T decomposition of the R gate, making our result tight.

arXiv:2202.09235•Leibniz international proceedings in informatics•Jan 1, 2022•13 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 multiqubit Clifford+ T circuits

Brett Gordon Giles, Peter Selinger

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 $\mathbb{Z}[\frac{1}{\sqrt{2}},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.

arXiv:1212.0506•Physical Review A•Mar 26, 2013•162 citations

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=\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.

arXiv:2311.08696•Nov 15, 2023•1 citation

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

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
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.
A popular universal gate set for quantum computing with qubits is Clifford+T, as this can be readily implemented on many fault-tolerant architectures. For qutrits, there is an equivalent T gate, that, like its qubit analogue, makes Clifford+T approximately universal, is injectable by a magic state, and supports magic state distillation. However, it was claimed that a better gate set for qutrits might be Clifford+R, where R=diag(1,1,-1) is the metaplectic gate, as certain protocols and gates could more easily be implemented using the R gate than the T gate. In this paper we show that when we have at least two qutrits, the qutrit Clifford+R unitaries form a strict subset of the Clifford+T unitaries, by finding a direct decomposition of R⊗IR \otimes \mathbb{I}R⊗I as a Clifford+T circuit and proving that the T gate cannot be exactly synthesized in Clifford+R. This shows that in fact the T gate is at least as powerful as the R gate, up to a constant factor. Moreover, we additionally show that it is impossible to find a single-qutrit Clifford+T decomposition of the R gate, making our result tight.
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 prove that a unitary matrix has an exact representation over the Clifford+TTT gate set with local ancillas if and only if its entries are in the ring Z[12,i]\mathbb{Z}[\frac{1}{\sqrt{2}},i]Z[2​1​,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+TTT circuit from any such nnn-qubit operator. We also characterize the Clifford+TTT operators that can be represented without ancillas.
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.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
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.