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• 44 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•4 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•15 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•25 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•6 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.

arXiv:1409.4355•Quantum Information and Computation•Sep 1, 2015•102 citations

Reducing 2-QuBit Gate Count for ZX-Calculus based Quantum Circuit Optimization

Korbinian Staudacher, Tobias Guggemos, Sophia Grundner-Culemann +1 more

In the near term, programming quantum computers will remain severely limited by low quantum volumes.Therefore, it is desirable to implement quantum circuits with the fewest resources possible.For the common Clifford+T circuits, most research is focused on reducing the number of T gates, since they are an order of magnitude more expensive than Clifford gates in quantum error corrected encoding schemes.However, this optimization sometimes leads to more 2-qubit gates, which, even though they are less expensive in terms of fault-tolerance, contribute significantly to the overall circuit cost.Approaches based on the ZX-calculus have recently gained some popularity in the field, but reduction of 2-qubit gates is not their focus.In this work, we present an alternative for improving 2-qubit gate count of a quantum circuit with the ZX-calculus by using heuristics in ZX-diagram simplification.Our approach maintains the good reduction of the T gate count provided by other strategies based on ZX-calculus, thus serving as an extension for other optimization algorithms.Our results show that combining the available ZX-calculus-based optimizations with our algorithms can reduce the number of 2-qubit gates by as much as 40 % compared to current approaches using ZXcalculus.Additionally, we improve the results of the best currently available optimization technique of Nam et.al [22] for some circuits by up to 15 %.

arXiv:2311.08881•Electronic Proceedings in Theoretical Computer Science•Nov 14, 2023•31 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.
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.
In the near term, programming quantum computers will remain severely limited by low quantum volumes.Therefore, it is desirable to implement quantum circuits with the fewest resources possible.For the common Clifford+T circuits, most research is focused on reducing the number of T gates, since they are an order of magnitude more expensive than Clifford gates in quantum error corrected encoding schemes.However, this optimization sometimes leads to more 2-qubit gates, which, even though they are less expensive in terms of fault-tolerance, contribute significantly to the overall circuit cost.Approaches based on the ZX-calculus have recently gained some popularity in the field, but reduction of 2-qubit gates is not their focus.In this work, we present an alternative for improving 2-qubit gate count of a quantum circuit with the ZX-calculus by using heuristics in ZX-diagram simplification.Our approach maintains the good reduction of the T gate count provided by other strategies based on ZX-calculus, thus serving as an extension for other optimization algorithms.Our results show that combining the available ZX-calculus-based optimizations with our algorithms can reduce the number of 2-qubit gates by as much as 40 % compared to current approaches using ZXcalculus.Additionally, we improve the results of the best currently available optimization technique of Nam et.al [22] for some circuits by up to 15 %.