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

Systematic construction of multi-controlled Pauli gate decompositions with optimal $T$-count

Ken M. Nakanishi, Synge Todo

Published Oct 1, 2024• 1 citation
arXivHTMLPDF

Abstract

Multi-controlled Pauli gates are typical high-level qubit operations that appear in the quantum circuits of various quantum algorithms. We find multi-controlled Pauli gate decompositions with smaller CNOT-count or $T$-depth while keeping the currently known minimum $T$-count. For example, for the CCCZ gate, we find decompositions with CNOT-count 7 or $T$-depth 2 while keeping the $T$-count at the currently known minimum of 6. The discovery of these efficient decompositions improves the computational efficiency of many quantum algorithms. What led to this discovery is the systematic procedure for constructing multi-controlled Pauli gate decompositions. This procedure not only deepens our theoretical understanding of quantum gate decomposition but also leads to more efficient decompositions that have yet to be discovered.

DOI
10.48550/arxiv.2410.00910

Related papers

Quantum-gate decomposer

Ken M. Nakanishi, Takahiko Satoh, Synge Todo

Efficient decompositions of multi-qubit gates are essential in NISQ applications, where the number of gates or the circuit depth is limited. This paper presents efficient decompositions of CCZ and CCCZ gates, typical multi-qubit gates, under several qubit connectivities. We can construct the CCZ gate with only four CZ-depth when the qubit is square-shaped, including one auxiliary qubit. In T-shaped qubit connectivity, which has no closed loop, we can decompose the CCCZ gate with 17 CZ gates. While previous studies have shown a CCCZ gate decomposition with 14 CZ gates for the fully connected case, we found only four connections are sufficient for 14 CZ gates' implementation. The search for constraint-sufficient decompositions is aided by an optimization method we devised to bring the parameterized quantum circuit closer to the target quantum gate. We can apply this scheme to decompose any quantum gates, not only CCZ and CCCZ. Such decompositions of multi-qubit gates, together with the newly found CCZ and CCCZ decompositions, shorten the execution time of quantum circuits and improve the accuracy of complex quantum algorithms on near future QPUs.

arXiv:2109.13223•Sep 27, 2021•3 citations

Decompositions of multiple controlled- Z gates on various qubit-coupling graphs

Ken M. Nakanishi, Takahiko Satoh, Synge Todo

Efficient decomposition of multiqubit operators is critical in the execution of quantum algorithms. In this paper, we introduce decompositions of the multiple controlled-$Z$ (ccz and cccz) gates tailored to various qubit-coupling graphs. Specifically, we demonstrate that the ccz gate is realized with cz-depth 4 on a square-shaped qubit-coupling graph utilizing one auxiliary qubit. As for the cccz gate, previous research indicated that the decomposition requires 14 cz gates in a fully connected topology. However, our findings reveal that only four specific qubit couplings are needed to achieve a decomposition using the same number of cz gates, 14. Our research employs an optimization method to improve the alignment of parametrized quantum circuits with their intended quantum gates, which facilitates these efficient decompositions. This methodology is versatile and can be applied to decompose any quantum gates, not just the ccz and cccz gates. These advancements in decomposing multiqubit gates, coupled with our ccz and cccz decompositions, are poised to reduce quantum circuit execution times and enhance the efficiency of complex quantum algorithms in imminent quantum computing applications.

Physical Review A•Jul 1, 2024•5 citations

Optimizing Gate Decomposition for High-Level Quantum Programming

Evandro C. R. Rosa, Eduardo I. Duzzioni, Rafael de Santiago

This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting U ( 2 ) gates as S U ( 2 ) gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from O ( n 2 ) to at most 32 n . Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from 16 n to 12 n and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.

arXiv:2406.05581•Quantum•Mar 12, 2025•12 citations

Optimal, hardware native decomposition of parameterized multi-qubit Pauli gates

P. V. Sriluckshmy, Vicente Pina-Canelles, Mario Ponce-Martinez +3 more

Abstract We show how to efficiently decompose a parameterized multi-qubit Pauli (PMQP) gate into native parameterized two-qubit Pauli (P2QP) gates minimizing both the circuit depth and the number of P2QP gates. Given a realistic quantum computational model, we argue that the technique is optimal in terms of the number of hardware native gates and the overall depth of the decomposition. Starting from PMQP gate decompositions for the path and star hardware graph, we generalize the procedure to any generic hardware graph and provide exact expressions for the depth and number of P2QP gates of the decomposition. Furthermore, we show how to efficiently combine the decomposition of multiple PMQP gates to further reduce the depth as well as the number of P2QP gates for a combinatorial optimization problem using the Lechner–Hauke–Zoller mapping.

arXiv:2303.04498•Quantum Science and Technology•Sep 25, 2023•11 citations

Low-depth Quantum Circuit Decomposition of Multi-controlled Gates

Thiago Melo D. Azevedo, Jefferson D. S. Silva, Adenilton José da Silva

Multi-controlled gates are fundamental components in the design of quantum algorithms, where efficient decompositions of these operators can enhance algorithm performance. The best asymptotic decomposition of an n-controlled X gate with one borrowed ancilla into single qubit and CNOT gates produces circuits with degree 3 polylogarithmic depth and employs a divide-and-conquer strategy. In this paper, we reduce the number of recursive calls in the divide-and-conquer algorithm and decrease the depth of n-controlled X gate decomposition to a degree of 2.799 polylogarithmic depth. With this optimized decomposition, we also reduce the depth of n-controlled SU(2) gates and approximate n-controlled U(2) gates. Decompositions described in this work achieve the lowest asymptotic depth reported in the literature. We also perform an optimization in the base of the recursive approach. Starting at 52 control qubits, the proposed n-controlled X gate with one borrowed ancilla has the shortest circuit depth in the literature. One can reproduce all the results with the freely available open-source code provided in a public repository.

arXiv:2407.05162•Jul 6, 2024•0 citations

Minimum Toffoli depth for the multi-controlled Toffoli gate via teleportation

Spyros Tserkis, Muhammad Umer, Eleftherios Mastorakis +1 more

The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an MCT gate. This decomposition has unit Toffoli depth, independent of the number of controls, while achieving the lowest Toffoli count among existing approaches for more than five controls at the cost of a linear overhead in ancilla qubits. We also investigate the parameter regimes in which the teleportation-based decomposition is preferable by analyzing the relative quality of distributed entanglement and Toffoli gates. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.

quant-pharXiv:2604.25861•Apr 29, 2026•0 citations
Systematic construction of multi-controlled Pauli gate decompositions with optimal TTT-count
Multi-controlled Pauli gates are typical high-level qubit operations that appear in the quantum circuits of various quantum algorithms. We find multi-controlled Pauli gate decompositions with smaller CNOT-count or TTT-depth while keeping the currently known minimum TTT-count. For example, for the CCCZ gate, we find decompositions with CNOT-count 7 or TTT-depth 2 while keeping the TTT-count at the currently known minimum of 6. The discovery of these efficient decompositions improves the computational efficiency of many quantum algorithms. What led to this discovery is the systematic procedure for constructing multi-controlled Pauli gate decompositions. This procedure not only deepens our theoretical understanding of quantum gate decomposition but also leads to more efficient decompositions that have yet to be discovered.
Efficient decompositions of multi-qubit gates are essential in NISQ applications, where the number of gates or the circuit depth is limited. This paper presents efficient decompositions of CCZ and CCCZ gates, typical multi-qubit gates, under several qubit connectivities. We can construct the CCZ gate with only four CZ-depth when the qubit is square-shaped, including one auxiliary qubit. In T-shaped qubit connectivity, which has no closed loop, we can decompose the CCCZ gate with 17 CZ gates. While previous studies have shown a CCCZ gate decomposition with 14 CZ gates for the fully connected case, we found only four connections are sufficient for 14 CZ gates' implementation. The search for constraint-sufficient decompositions is aided by an optimization method we devised to bring the parameterized quantum circuit closer to the target quantum gate. We can apply this scheme to decompose any quantum gates, not only CCZ and CCCZ. Such decompositions of multi-qubit gates, together with the newly found CCZ and CCCZ decompositions, shorten the execution time of quantum circuits and improve the accuracy of complex quantum algorithms on near future QPUs.
Efficient decomposition of multiqubit operators is critical in the execution of quantum algorithms. In this paper, we introduce decompositions of the multiple controlled-ZZZ (ccz and cccz) gates tailored to various qubit-coupling graphs. Specifically, we demonstrate that the ccz gate is realized with cz-depth 4 on a square-shaped qubit-coupling graph utilizing one auxiliary qubit. As for the cccz gate, previous research indicated that the decomposition requires 14 cz gates in a fully connected topology. However, our findings reveal that only four specific qubit couplings are needed to achieve a decomposition using the same number of cz gates, 14. Our research employs an optimization method to improve the alignment of parametrized quantum circuits with their intended quantum gates, which facilitates these efficient decompositions. This methodology is versatile and can be applied to decompose any quantum gates, not just the ccz and cccz gates. These advancements in decomposing multiqubit gates, coupled with our ccz and cccz decompositions, are poised to reduce quantum circuit execution times and enhance the efficiency of complex quantum algorithms in imminent quantum computing applications.
This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting U ( 2 ) gates as S U ( 2 ) gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from O ( n 2 ) to at most 32 n . Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from 16 n to 12 n and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.
Abstract We show how to efficiently decompose a parameterized multi-qubit Pauli (PMQP) gate into native parameterized two-qubit Pauli (P2QP) gates minimizing both the circuit depth and the number of P2QP gates. Given a realistic quantum computational model, we argue that the technique is optimal in terms of the number of hardware native gates and the overall depth of the decomposition. Starting from PMQP gate decompositions for the path and star hardware graph, we generalize the procedure to any generic hardware graph and provide exact expressions for the depth and number of P2QP gates of the decomposition. Furthermore, we show how to efficiently combine the decomposition of multiple PMQP gates to further reduce the depth as well as the number of P2QP gates for a combinatorial optimization problem using the Lechner–Hauke–Zoller mapping.
Multi-controlled gates are fundamental components in the design of quantum algorithms, where efficient decompositions of these operators can enhance algorithm performance. The best asymptotic decomposition of an n-controlled X gate with one borrowed ancilla into single qubit and CNOT gates produces circuits with degree 3 polylogarithmic depth and employs a divide-and-conquer strategy. In this paper, we reduce the number of recursive calls in the divide-and-conquer algorithm and decrease the depth of n-controlled X gate decomposition to a degree of 2.799 polylogarithmic depth. With this optimized decomposition, we also reduce the depth of n-controlled SU(2) gates and approximate n-controlled U(2) gates. Decompositions described in this work achieve the lowest asymptotic depth reported in the literature. We also perform an optimization in the base of the recursive approach. Starting at 52 control qubits, the proposed n-controlled X gate with one borrowed ancilla has the shortest circuit depth in the literature. One can reproduce all the results with the freely available open-source code provided in a public repository.
The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an MCT gate. This decomposition has unit Toffoli depth, independent of the number of controls, while achieving the lowest Toffoli count among existing approaches for more than five controls at the cost of a linear overhead in ancilla qubits. We also investigate the parameter regimes in which the teleportation-based decomposition is preferable by analyzing the relative quality of distributed entanglement and Toffoli gates. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.