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:1212.0506 · Physical Review A

Exact synthesis of multiqubit Clifford+ T circuits

Brett Gordon Giles, Peter Selinger

Published Mar 26, 2013• 197 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.87.032332

Related papers

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

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

Synthesis of unitaries with Clifford+T circuits

Vadym Kliuchnikov

We describe a new method for approximating an arbitrary $n$ qubit unitary with precision $\varepsilon$ using a Clifford and T circuit with $O(4^{n}n(\log(1/\varepsilon)+n))$ gates. The method is based on rounding off a unitary to a unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ and employing exact synthesis. We also show that any $n$ qubit unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ with entries of the form $(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}$ can be exactly synthesized using $O(4^{n}nk)$ 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(3^{2^{n}}nk)$ elementary gates.

arXiv:1306.3200•Jun 13, 2013•60 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

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

Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.

arXiv:1206.5236•Quantum Information and Computation•May 1, 2013•264 citations
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.
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%.
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 describe a new method for approximating an arbitrary nnn qubit unitary with precision ε\varepsilonε using a Clifford and T circuit with O(4nn(log⁡(1/ε)+n))O(4^{n}n(\log(1/\varepsilon)+n))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]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​] and employing exact synthesis. We also show that any nnn qubit unitary over the ring Z[i,1/2]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​] with entries of the form (a+b2+ic+id2)/2k(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}(a+b2​+ic+id2​)/2k can be exactly synthesized using O(4nnk)O(4^{n}nk)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)O(3^{2^{n}}nk)O(32nnk) elementary gates.
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​].
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 show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring Z[12,i]\mathbb{Z}[\frac{1}{\sqrt{2}},i]Z[2​1​,i], in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring Z[12,i]\mathbb{Z}[\frac{1}{\sqrt{2}},i]Z[2​1​,i] holds in the nnn-qubit case.