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:2303.04498 · Quantum Science and Technology

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

P. V. Sriluckshmy, Vicente Pina-Canelles, Mario Ponce-Martinez, Manuel G. Algaba, Fedor Šimkovic, Martin Leib

Published Sep 25, 2023• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/2058-9565/acfa20

Related papers

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

Ken M. Nakanishi, Synge Todo

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.

arXiv:2410.00910•Oct 1, 2024•1 citation

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

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

Teague Tomesh, Nicholas Allen, Daniel Dilley +1 more

The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .

arXiv:2210.04378•Quantum•Oct 4, 2024•8 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

Hardware-Conscious Optimization of the Quantum Toffoli Gate

Max Aksel Bowman, Pranav Gokhale, Jeffrey M. Larson +2 more

While quantum computing holds great potential in combinatorial optimization, electronic structure calculation, and number theory, the current era of quantum computing is limited by noisy hardware. Many quantum compilation approaches can mitigate the effects of imperfect hardware by optimizing quantum circuits for objectives such as critical path length. Few approaches consider quantum circuits in terms of the set of vendor-calibrated operations (i.e., native gates) available on target hardware. This manuscript expands the analytical and numerical approaches for optimizing quantum circuits at this abstraction level. We present a procedure for combining the strengths of analytical native gate-level optimization with numerical optimization. Although we focus on optimizing Toffoli gates on the IBMQ native gate set, the methods presented are generalizable to any gate and superconducting qubit architecture. Our optimized Toffoli gate implementation demonstrates an 18% reduction in infidelity compared with the canonical implementation as benchmarked on IBM Jakarta with quantum process tomography. Assuming the inclusion of multi-qubit cross-resonance (MCR) gates in the IBMQ native gate set, we produce Toffoli implementations with only six multi-qubit gates, a 25% reduction from the canonical eight multi-qubit implementations for linearly connected qubits.

arXiv:2209.02669•ACM Transactions on Quantum Computing•Jul 20, 2023•13 citations

Decomposition of multi-qutrit gates generated by Weyl-Heisenberg strings

Daniele Trisciani, Marco Cattaneo, Zoltán Zimborás

Decomposing unitary operations into native gates is an essential step for implementing quantum algorithms. For qubit-based devices, where native gates are typically single- and two-qubit operations, a range of decomposition techniques have been developed. In particular, efficient algorithms exist for decomposing exponentials of Pauli strings while taking hardware topology in account. Motivated by the growing interest in qutrit-based quantum computing, we develop analogous decomposition methods for qutrit systems. Specifically, we introduce an algorithm that decomposes the exponential of an arbitrary tensor product of Weyl-Heisenberg operators (plus their Hermitian conjugation) into single- and two-qutrit gates. We further extend this approach to unitaries generated by Gell-Mann string (i.e., a tensor product of Gell-Mann matrices). Since both Gell-Mann matrices and Weyl-Heisenberg operators form (together with identity) complete operator bases of qutrit operators, we can use this result also to decompose any multi-qutrit gate that is diagonal up to single-qutrit rotations. As a practical application, we use our method to decompose the layers of the quantum approximate optimization algorithm for qutrit-based implementations of the graph k-coloring problem. For values of $k$ well-suited to qutrit architectures (e.g., $k=3$ or in general $k=3^n$), our approach yields significantly shallower circuits compared to qubit-based implementations, an advantage that grows with problem size, while also requiring a smaller total Hilbert space dimension. Finally, we also address the routing challenge in qutrit architectures that arises due to the limited connectivity of the devices. In particular, we generalize the Steiner-Gauss method, originally developed to reduce CNOT counts in qubit circuit, to optimize gate routing in qutrit-based systems.

arXiv:2507.09781•Jul 13, 2025•0 citations
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.
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.
The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .
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.
While quantum computing holds great potential in combinatorial optimization, electronic structure calculation, and number theory, the current era of quantum computing is limited by noisy hardware. Many quantum compilation approaches can mitigate the effects of imperfect hardware by optimizing quantum circuits for objectives such as critical path length. Few approaches consider quantum circuits in terms of the set of vendor-calibrated operations (i.e., native gates) available on target hardware. This manuscript expands the analytical and numerical approaches for optimizing quantum circuits at this abstraction level. We present a procedure for combining the strengths of analytical native gate-level optimization with numerical optimization. Although we focus on optimizing Toffoli gates on the IBMQ native gate set, the methods presented are generalizable to any gate and superconducting qubit architecture. Our optimized Toffoli gate implementation demonstrates an 18% reduction in infidelity compared with the canonical implementation as benchmarked on IBM Jakarta with quantum process tomography. Assuming the inclusion of multi-qubit cross-resonance (MCR) gates in the IBMQ native gate set, we produce Toffoli implementations with only six multi-qubit gates, a 25% reduction from the canonical eight multi-qubit implementations for linearly connected qubits.
Decomposing unitary operations into native gates is an essential step for implementing quantum algorithms. For qubit-based devices, where native gates are typically single- and two-qubit operations, a range of decomposition techniques have been developed. In particular, efficient algorithms exist for decomposing exponentials of Pauli strings while taking hardware topology in account. Motivated by the growing interest in qutrit-based quantum computing, we develop analogous decomposition methods for qutrit systems. Specifically, we introduce an algorithm that decomposes the exponential of an arbitrary tensor product of Weyl-Heisenberg operators (plus their Hermitian conjugation) into single- and two-qutrit gates. We further extend this approach to unitaries generated by Gell-Mann string (i.e., a tensor product of Gell-Mann matrices). Since both Gell-Mann matrices and Weyl-Heisenberg operators form (together with identity) complete operator bases of qutrit operators, we can use this result also to decompose any multi-qutrit gate that is diagonal up to single-qutrit rotations. As a practical application, we use our method to decompose the layers of the quantum approximate optimization algorithm for qutrit-based implementations of the graph k-coloring problem. For values of kkk well-suited to qutrit architectures (e.g., k=3k=3k=3 or in general k=3nk=3^nk=3n), our approach yields significantly shallower circuits compared to qubit-based implementations, an advantage that grows with problem size, while also requiring a smaller total Hilbert space dimension. Finally, we also address the routing challenge in qutrit architectures that arises due to the limited connectivity of the devices. In particular, we generalize the Steiner-Gauss method, originally developed to reduce CNOT counts in qubit circuit, to optimize gate routing in qutrit-based systems.