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

Optimizing T gates in Clifford+T circuit as $π/4$ rotations around Paulis

Zhang, Fang, Jianxin Chen

Published Mar 29, 2019• 15 citations
arXivHTMLPDF

Abstract

In this work, we introduce a new circuit optimization technique to reduce the number of T gates in Clifford+T circuits by treating T gates conjugated by Clifford gates as $\fracπ{4}$-rotations around Pauli operators. The tested benchmarks shows up to $71.43\%$ and an average $42.67\%$ reduction in T-count, both surpass the best performance reported. The worst case complexity of our algorithm is $O(nk^2)$ where $n$ is the number of qubits and $k$ is the number of T gates in the original Clifford+T circuit.

DOI
10.48550/arxiv.1903.12456

Related papers

Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences

Vivien Vandaele, Simon Martiel, Simon Perdrix +1 more

The Clifford$+T$ gate set is commonly used to perform universal quantum computation. In such setup the $T$ gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of $T$ gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial $T$-count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of $T$ gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of $π/4$ Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last $T$ gate of the circuit.

arXiv:2302.07040•Feb 14, 2023•0 citations

Optimal Hadamard Gate Count for Clifford+ T Synthesis of Pauli Rotations Sequences

Vivien Vandaele, Simon Martiel, Simon Perdrix +1 more

The Clifford+ T gate set is commonly used to perform universal quantum computation. In such setup the T gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of T gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial T -count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of T gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of π /4 Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last T gate of the circuit.

ACM Transactions on Quantum Computing•Dec 28, 2023•11 citations

Lower T-count with faster algorithms

Vivien Vandaele

Among the cost metrics characterizing a quantum circuit, the T -count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the T -count reduction problem by proposing efficient T -count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best T -count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of T gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal T -count than the state of the art on most quantum circuits evaluated. We also prove that the number of T gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of n qubits is upper bounded by n ( n + 1 ) / 2 + 1 , which improves on the worst-case T -count of existing optimization algorithms. From this we derive an upper bound of ( n + 1 ) ( n + 2 h ) / 2 + 1 for the number of T gates in a Clifford + T circuit where h is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last T gate of the circuit.

arXiv:2407.08695•Quantum•Sep 16, 2025•4 citations

Optimal number of parametrized rotations and Hadamard gates in parametrized Clifford circuits with non-repeated parameters

Vivien Vandaele, Simon Perdrix, Christophe Vuillot

We present an efficient algorithm to reduce the number of non-Clifford gates in quantum circuits and the number of parametrized rotations in parametrized quantum circuits. The method consists in finding rotations that can be merged into a single rotation gate. This approach has already been considered before and is used as a pre-processing procedure in many optimization algorithms, notably for optimizing the number of Hadamard gates or the number of $T$ gates in Clifford$+T$ circuits. Our algorithm has a better complexity than similar methods and is particularly efficient for circuits with a low number of internal Hadamard gates. Furthermore, we show that this approach is optimal for parametrized circuits composed of Clifford gates and parametrized rotations with non-repeated parameters. For the same type of parametrized quantum circuits, we also prove that a previous procedure optimizing the number of Hadamard gates and internal Hadamard gates is optimal. This procedure is notably used in our low-complexity algorithm for optimally reducing the number of parametrized rotations.

arXiv:2407.07846•Jul 10, 2024•0 citations

An Efficient Quantum Compiler that reduces TTT count

Luke Heyfron, Earl T. Campbell

Before executing a quantum algorithm, one must first decompose the algorithm into machine-level instructions compatible with the architecture of the quantum computer, a process known as quantum compiling. There are many different quantum circuit decompositions for the same algorithm but it is desirable to compile leaner circuits. A fundamentally important cost metric is the $T$ count -- the number of $T$ gates in a circuit. For the single qubit case, optimal compiling is essentially a solved problem. However, multi-qubit compiling is a harder problem with optimal algorithms requiring classical runtime exponential in the number of qubits. Here, we present and compare several efficient quantum compilers for multi-qubit Clifford + $T$ circuits. We implemented our compilers in C++ and benchmarked them on random circuits, from which we determine that our TODD compiler yields the lowest $T$ counts on average. We also benchmarked TODD on a library of reversible logic circuits that appear in quantum algorithms and found that it reduced the $T$ count for 97\% of the circuits with an average $T$-count saving of 20\% when compared against the best of all previous circuit decompositions.

arXiv:1712.01557•Dec 5, 2017•11 citations

Optimal ancilla-free Clifford+V approximation of z-rotations

Neil J. Ross

We describe a new efficient algorithm to approximate $z$-rotations by ancilla-free Clifford+$V$ circuits, up to a given precision $\epsilon$. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+$V$ circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of $V$\!-count $m + O(\log(\log(1/\epsilon)))$, where $m$ is the $V$\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates $z$-rotations in the Pauli+$V$ gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of $z$-rotations using Clifford+$T$ gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of $z$-rotations using Clifford+$V$ gates.

Quantum Information and Computation•Sep 1, 2015•72 citations
Optimizing T gates in Clifford+T circuit as π/4π/4π/4 rotations around Paulis
In this work, we introduce a new circuit optimization technique to reduce the number of T gates in Clifford+T circuits by treating T gates conjugated by Clifford gates as π4\fracπ{4}4π​-rotations around Pauli operators. The tested benchmarks shows up to 71.43%71.43\%71.43% and an average 42.67%42.67\%42.67% reduction in T-count, both surpass the best performance reported. The worst case complexity of our algorithm is O(nk2)O(nk^2)O(nk2) where nnn is the number of qubits and kkk is the number of T gates in the original Clifford+T circuit.
Optimal Hadamard gate count for Clifford+T+T+T synthesis of Pauli rotations sequences
The Clifford+T+T+T gate set is commonly used to perform universal quantum computation. In such setup the TTT gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of TTT gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial TTT-count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of TTT gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of π/4π/4π/4 Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last TTT gate of the circuit.
The Clifford+ T gate set is commonly used to perform universal quantum computation. In such setup the T gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of T gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial T -count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of T gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of π /4 Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last T gate of the circuit.
Among the cost metrics characterizing a quantum circuit, the T -count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the T -count reduction problem by proposing efficient T -count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best T -count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of T gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal T -count than the state of the art on most quantum circuits evaluated. We also prove that the number of T gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of n qubits is upper bounded by n ( n + 1 ) / 2 + 1 , which improves on the worst-case T -count of existing optimization algorithms. From this we derive an upper bound of ( n + 1 ) ( n + 2 h ) / 2 + 1 for the number of T gates in a Clifford + T circuit where h is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last T gate of the circuit.
We present an efficient algorithm to reduce the number of non-Clifford gates in quantum circuits and the number of parametrized rotations in parametrized quantum circuits. The method consists in finding rotations that can be merged into a single rotation gate. This approach has already been considered before and is used as a pre-processing procedure in many optimization algorithms, notably for optimizing the number of Hadamard gates or the number of TTT gates in Clifford+T+T+T circuits. Our algorithm has a better complexity than similar methods and is particularly efficient for circuits with a low number of internal Hadamard gates. Furthermore, we show that this approach is optimal for parametrized circuits composed of Clifford gates and parametrized rotations with non-repeated parameters. For the same type of parametrized quantum circuits, we also prove that a previous procedure optimizing the number of Hadamard gates and internal Hadamard gates is optimal. This procedure is notably used in our low-complexity algorithm for optimally reducing the number of parametrized rotations.
Before executing a quantum algorithm, one must first decompose the algorithm into machine-level instructions compatible with the architecture of the quantum computer, a process known as quantum compiling. There are many different quantum circuit decompositions for the same algorithm but it is desirable to compile leaner circuits. A fundamentally important cost metric is the TTT count -- the number of TTT gates in a circuit. For the single qubit case, optimal compiling is essentially a solved problem. However, multi-qubit compiling is a harder problem with optimal algorithms requiring classical runtime exponential in the number of qubits. Here, we present and compare several efficient quantum compilers for multi-qubit Clifford + TTT circuits. We implemented our compilers in C++ and benchmarked them on random circuits, from which we determine that our TODD compiler yields the lowest TTT counts on average. We also benchmarked TODD on a library of reversible logic circuits that appear in quantum algorithms and found that it reduced the TTT count for 97\% of the circuits with an average TTT-count saving of 20\% when compared against the best of all previous circuit decompositions.
We describe a new efficient algorithm to approximate zzz-rotations by ancilla-free Clifford+VVV circuits, up to a given precision ϵ\epsilonϵ. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+VVV circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of VVV\!-count m+O(log⁡(log⁡(1/ϵ)))m + O(\log(\log(1/\epsilon)))m+O(log(log(1/ϵ))), where mmm is the VVV\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates zzz-rotations in the Pauli+VVV gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of zzz-rotations using Clifford+TTT gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of zzz-rotations using Clifford+VVV gates.