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

Quantum Information and Computation

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

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

Published May 1, 2013• 146 citations
Publisher

Abstract

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.

DOI
10.26421/qic13.7-8-4

Related papers

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

Vadym Kliuchnikov, Maslov, Dmitri, 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 and T 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•Jun 22, 2012•57 citations

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

KliuchnikovVadym, MaslovDmitri, MoscaMichele

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[1/√2, i], in the single-qubit case...

Quantum Information and Computation•Jul 1, 2013•27 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

Multi-qubit circuit synthesis and Hermitian lattices

Vadym Kliuchnikov, Sebastian Schönnenbeck

We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.

arXiv:2405.19302•May 29, 2024•0 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 exact synthesis of two-qubit unitaries using a near-minimum number of T gates

Longcheng Li, Cheng Guo, Qian Li +1 more

This paper focuses on exact synthesis of two-qubit unitaries using Clifford and $T$ gates. We propose an ancilla-free synthesis algorithm (i) which uses $T$ gates no more than ten times the minimum possible number of $T$ gates, also known as the $T$ count, and (ii) whose time complexity is linear with the $T$ count and thus instance optimal. Our synthesis algorithm relies on a characterization of the $T$ count of two-qubit unitaries based on Lie group homomorphism, which may be interest of its own. Precisely, we show that for any two-qubit unitary generated by Clifford and $T$ gates, its $T$ count is equivalent to the least denominator exponent of its SO(6) representation up to a factor of at most 10.

Physical Review A•Apr 18, 2023•3 citations
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.
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 and T 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.
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 present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in Z[i,1/2]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​]. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.
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.
This paper focuses on exact synthesis of two-qubit unitaries using Clifford and TTT gates. We propose an ancilla-free synthesis algorithm (i) which uses TTT gates no more than ten times the minimum possible number of TTT gates, also known as the TTT count, and (ii) whose time complexity is linear with the TTT count and thus instance optimal. Our synthesis algorithm relies on a characterization of the TTT count of two-qubit unitaries based on Lie group homomorphism, which may be interest of its own. Precisely, we show that for any two-qubit unitary generated by Clifford and TTT gates, its TTT count is equivalent to the least denominator exponent of its SO(6) representation up to a factor of at most 10.