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:2508.14674 · Electronic Proceedings in Theoretical Computer Science

Contributions to the Theory of Clifford-Cyclotomic Circuits

Linh Dinh, Neil J. Ross

Published Aug 19, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.4204/eptcs.426.9

Related papers

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

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•57 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•197 citations

Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

Matthew Amy, Andrew N. Glaudell, Neil J. Ross

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.

arXiv:1908.06076•Quantum•Apr 6, 2020•39 citations

Generators and Relations for Un(Z[1/2,i])

Xiaoning Bian, Peter Selinger

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

arXiv:2105.14047•Electronic Proceedings in Theoretical Computer Science•Sep 9, 2021•8 citations
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.
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%.
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.
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.
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].