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

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

Vivien Vandaele, Simon Perdrix, Christophe Vuillot

Published Jul 10, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2407.07846

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

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

Zhang, Fang, Jianxin Chen

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.

arXiv:1903.12456•Mar 29, 2019•15 citations

Qubit-count optimization using ZX-calculus

Vivien Vandaele

We propose several methods for optimizing the number of qubits in a quantum circuit while preserving the number of non-Clifford gates. One of our approaches consists in reversing, as much as possible, the gadgetization of Hadamard gates, which is a procedure used by some $T$-count optimizers to circumvent Hadamard gates at the expense of additional qubits. We prove the NP-hardness of this problem and we present an algorithm for solving it. We also propose a more general approach to optimize the number of qubits by showing how it relates to the problem of finding a minimal-width path-decomposition of the graph associated with a given ZX-diagram. This approach can be used to optimize the number of qubits for any computational model that can natively be depicted in ZX-calculus, such as the Pauli Fusion computational model which can represent lattice surgery operations. We also show how this method can be used to efficiently optimize the number of qubits in a quantum circuit by using the ZX-calculus as an intermediate representation.

arXiv:2407.10171•Jul 14, 2024•0 citations

Reducing the number of non-Clifford gates in quantum circuits

Aleks Kissinger, John van de Wetering

We present a method for reducing the number of non-Clifford quantum gates, in particularly T-gates, in a circuit, an important task for efficiently implementing fault-tolerant quantum computations. This method matches or beats previous approaches to ancillae-free T-count reduction on the majority of our benchmark circuits, in some cases yielding up to 50% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor networklike structure that can be transformed and simplified according to the rules of the ZX-calculus. We then extend a recent simplification strategy with a different ingredient, phase gadgetization, which we use to propagate non-Clifford phases through a ZX-diagram to find nonlocal cancellations. Our procedure extends unmodified to arbitrary phase angles and to parameter elimination for variational circuits. Finally, our optimization is self-checking, in the sense that the simplification strategy we propose is powerful enough to independently validate equality of the input circuit and the optimized output circuit. We have implemented the routines of this paper in the open-source library pyzx.

arXiv:1903.10477•Physical Review A•Aug 11, 2020•162 citations

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

quant-pharXiv:2610.02029•Oct 2, 2026•0 citations
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.
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.
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.
We propose several methods for optimizing the number of qubits in a quantum circuit while preserving the number of non-Clifford gates. One of our approaches consists in reversing, as much as possible, the gadgetization of Hadamard gates, which is a procedure used by some TTT-count optimizers to circumvent Hadamard gates at the expense of additional qubits. We prove the NP-hardness of this problem and we present an algorithm for solving it. We also propose a more general approach to optimize the number of qubits by showing how it relates to the problem of finding a minimal-width path-decomposition of the graph associated with a given ZX-diagram. This approach can be used to optimize the number of qubits for any computational model that can natively be depicted in ZX-calculus, such as the Pauli Fusion computational model which can represent lattice surgery operations. We also show how this method can be used to efficiently optimize the number of qubits in a quantum circuit by using the ZX-calculus as an intermediate representation.
We present a method for reducing the number of non-Clifford quantum gates, in particularly T-gates, in a circuit, an important task for efficiently implementing fault-tolerant quantum computations. This method matches or beats previous approaches to ancillae-free T-count reduction on the majority of our benchmark circuits, in some cases yielding up to 50% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor networklike structure that can be transformed and simplified according to the rules of the ZX-calculus. We then extend a recent simplification strategy with a different ingredient, phase gadgetization, which we use to propagate non-Clifford phases through a ZX-diagram to find nonlocal cancellations. Our procedure extends unmodified to arbitrary phase angles and to parameter elimination for variational circuits. Finally, our optimization is self-checking, in the sense that the simplification strategy we propose is powerful enough to independently validate equality of the input circuit and the optimized output circuit. We have implemented the routines of this paper in the open-source library pyzx.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.