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:2110.10292 · npj Quantum Information

T-count and T-depth of any multi-qubit unitary

Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

Published Nov 30, 2022• 34 citations
arXivHTMLPDF

Abstract

Abstract We design an algorithm to determine the (minimum) T-count of any n -qubit ( n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are $$O\left({2}^{2n}\right)$$ O 2 2 n and $$O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)$$ O 2 2 n T ϵ ( W ) + 4 n , respectively. $${{{{\mathcal{T}}}}}_{\epsilon }(W)$$ T ϵ ( W ) ( ϵ -T-count) is the (minimum) T-count of an exactly implementable unitary U ( $${{{\mathcal{T}}}}(U)$$ T ( U ) ), such that d ( U , W ) ≤ ϵ and $${{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })$$ T ( U ) ≤ T ( U ′ ) where $${U}^{{\prime} }$$ U ′ is any exactly implementable unitary with $$d({U}^{{\prime} },W)\le \epsilon$$ d ( U ′ , W ) ≤ ϵ </

DOI
10.1038/s41534-022-00651-y

Related papers

An algorithm for the T-countAn algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and $T$ gates. In this context the $T$ gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an $n$-qubit unitary $U$ we are interested in computing a circuit that implements it using the minimum possible number of $T$ gates (called the $T$-count of $U$). A related task is to decide if the $T$-count of $U$ is less than or equal to $m$; we consider this problem as a function of $N=2^n$ and $m$. We provide a classical algorithm which solves it using time and space both upper bounded as $\mathcal{O}(N^m \text{poly}(m,N))$. We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 $T$ gates. This implies that the known 7 $T$ gate circuits for these gates are $T$-optimal. We also provide a simple expression for the $T$-count of single-qubit unitaries.

Quantum Information and Computation•Nov 1, 2014•65 citations

An algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.

arXiv:1308.4134•Aug 19, 2013•32 citations

CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries

Priyanka Mukhopadhyay

Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer $${\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T$$ J n CS ⊂ J n T , where $${\mathcal {J}}_n^{CS}$$ J n CS and $${\mathcal {J}}_n^T$$ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying $${\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}$$ J n Tof = J n CS , where $${\mathcal {J}}_n^{Tof}$$ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.

Scientific Reports•Jun 17, 2024•2 citations

A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits

Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, $${{\mathbb{V}}}_{n}$$ Vn , of T-depth 1 unitaries. T-depth-optimal decomposition of unitaryUis $${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$ eiϕ∏iViC , $${V}_{i}\in {{\mathbb{V}}}_{n}$$ Vi∈Vn ,Cis Clifford and $$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$ ∣Vn∣≤n⋅25.6n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity $$O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })$$ O((4n2)⌈d/c⌉) and $$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$ O((4n2)(c−1)⌈d/c⌉) respectively (dis the minimum T-depth,c ≥ 2 a constant). The previous best algorithm had complexity $$O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})$$ O((3n⋅2kn2)⌈d2⌉⋅2kn2) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or $${{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)$$ poly(nlogn,25.6n,d) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.

arXiv:2101.03142•npj Quantum Information•Sep 13, 2022•16 citations

A polynomial time and space heuristic algorithm for T-count

Michele Mosca, Priyanka Mukhopadhyay

Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.

arXiv:2006.12440•Quantum Science and Technology•Oct 7, 2021•29 citations

Clifford synthesis via generalized S and CZ gates

Vadym Kliuchnikov, Marcus P. da Silva

We show that any $n$-qubit Clifford unitary can be implemented using at most $2n$ multi-qubit joint measurements. All the multi-qubit joint measurements used for implementing the Clifford unitary can be chosen to form at most two sets of independent mutually-commuting measurements. Each of these sets is of size at most $n$. This enables very flexible space-time trade-offs when implementing Clifford unitaries. We also discuss a version of the result that relies on multi-target CNOTs and is more relevant for targeting fault-tolerant hardware based on Quantum LDPC codes.

quant-pharXiv:2603.24731•Mar 27, 2026•0 citations
Abstract We design an algorithm to determine the (minimum) T-count of any n -qubit ( n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are O(22n)O\left({2}^{2n}\right)O(22n) O 2 2 n and O(22nTϵ(W)+4n)O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)O(22nTϵ​(W)+4n) O 2 2 n T ϵ ( W ) + 4 n , respectively. Tϵ(W){{{{\mathcal{T}}}}}_{\epsilon }(W)Tϵ​(W) T ϵ ( W ) ( ϵ -T-count) is the (minimum) T-count of an exactly implementable unitary U ( T(U){{{\mathcal{T}}}}(U)T(U) T ( U ) ), such that d ( U , W ) ≤ ϵ and T(U)≤T(U′){{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })T(U)≤T(U′) T ( U ) ≤ T ( U ′ ) where U′{U}^{{\prime} }U′ U ′ is any exactly implementable unitary with d(U′,W)≤ϵd({U}^{{\prime} },W)\le \epsilond(U′,W)≤ϵ d ( U ′ , W ) ≤ ϵ </
We consider quantum circuits composed of Clifford and TTT gates. In this context the TTT gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an nnn-qubit unitary UUU we are interested in computing a circuit that implements it using the minimum possible number of TTT gates (called the TTT-count of UUU). A related task is to decide if the TTT-count of UUU is less than or equal to mmm; we consider this problem as a function of N=2nN=2^nN=2n and mmm. We provide a classical algorithm which solves it using time and space both upper bounded as O(Nmpoly(m,N))\mathcal{O}(N^m \text{poly}(m,N))O(Nmpoly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 TTT gates. This implies that the known 7 TTT gate circuits for these gates are TTT-optimal. We also provide a simple expression for the TTT-count of single-qubit unitaries.
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT{\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^TJnCS​⊂JnT​ J n CS ⊂ J n T , where JnCS{\mathcal {J}}_n^{CS}JnCS​ J n CS and JnT{\mathcal {J}}_n^TJnT​ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS{\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}JnTof​=JnCS​ J n Tof = J n CS , where JnTof{\mathcal {J}}_n^{Tof}JnTof​ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.
Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, Vn{{\mathbb{V}}}_{n}Vn​ Vn , of T-depth 1 unitaries. T-depth-optimal decomposition of unitaryUis eiϕ(∏iVi)C{e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)Ceiϕ(∏i​Vi​)C eiϕ∏iViC , Vi∈Vn{V}_{i}\in {{\mathbb{V}}}_{n}Vi​∈Vn​ Vi∈Vn ,Cis Clifford and ∣Vn∣ ≤ n⋅25.6n| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}∣Vn​∣≤n⋅25.6n ∣Vn∣≤n⋅25.6n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity O((4n2)⌈d/c⌉)O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })O((4n2)⌈d/c⌉) O((4n2)⌈d/c⌉) and O((4n2)(c−1)⌈d/c⌉)O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })O((4n2)(c−1)⌈d/c⌉) O((4n2)(c−1)⌈d/c⌉) respectively (dis the minimum T-depth,c ≥ 2 a constant). The previous best algorithm had complexity O((3n⋅2kn2)⌈d2⌉⋅2kn2)O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})O((3n⋅2kn2)⌈2d​⌉⋅2kn2) O((3n⋅2kn2)⌈d2⌉⋅2kn2) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or poly(nlog⁡n,25.6n,d){{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)poly(nlogn,25.6n,d) poly(nlogn,25.6n,d) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.
We show that any nnn-qubit Clifford unitary can be implemented using at most 2n2n2n multi-qubit joint measurements. All the multi-qubit joint measurements used for implementing the Clifford unitary can be chosen to form at most two sets of independent mutually-commuting measurements. Each of these sets is of size at most nnn. This enables very flexible space-time trade-offs when implementing Clifford unitaries. We also discuss a version of the result that relies on multi-target CNOTs and is more relevant for targeting fault-tolerant hardware based on Quantum LDPC codes.