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:2406.05581 · Quantum

Optimizing Gate Decomposition for High-Level Quantum Programming

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

Published Mar 12, 2025• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2025-03-12-1659

Related papers

Automated Auxiliary Qubit Allocation in High-Level Quantum Programming

Evandro C. R. Rosa, Jerusa Marchi, Eduardo I. Duzzioni +1 more

We present a method for optimizing quantum circuit compilation by automating the allocation of auxiliary qubits for multi-qubit gate decompositions. This approach is implemented and evaluated within the high-level quantum programming platform Ket. Our results indicate that the decomposition of multi-qubit gates is more effectively handled by the compiler, which has access to all circuit parameters, rather than through a quantum programming API. To evaluate the approach, we compared our implementation against Qiskit, a widely used quantum programming platform, by analyzing two quantum algorithms. Using a 16-qubit QPU, we observed a reduction of 87% in the number of CNOT gates in Grover's algorithm for 9 qubits. For a state preparation algorithm with 7 qubits, the number of CNOT gates was reduced from $2.8\times10^7$ to $5.7\times10^3$, leveraging additional Ket optimizations for high-level quantum program constructions. Overall, a quadratic reduction in the number of CNOT gates in the final circuit was observed, with greater improvements achieved when more auxiliary qubits were available. These findings underscore the importance of automatic resource management, such as auxiliary qubit allocation, in optimizing quantum applications and improving their suitability for near-term quantum hardware.

arXiv:2412.20543•Dec 29, 2024•0 citations

Decomposition of Multi-controlled Special Unitary Single-Qubit Gates

Rafaella F. Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo +2 more

Multi-controlled unitary gates have been a subject of interest in quantum computing since its inception, and are widely used in quantum algorithms. The current state-of-the-art approach to implementing n-qubit multi-controlled gates involves the use of a quadratic number of single-qubit and CNOT gates. However, linear solutions are possible for the case where the controlled gate is a special unitary SU(2). The most widely-used decomposition of an n-qubit multi-controlled SU(2) gate requires a circuit with a number of CNOT gates proportional to 28n. In this work, we present a new decomposition of n-qubit multi-controlled SU(2) gates that requires a circuit with a number of CNOT gates proportional to 20n, and proportional to 16n if the SU(2) gate has at least one real-valued diagonal. This new approach significantly improves the existing algorithm by reducing the number of CNOT gates and the overall circuit depth. As an application, we show the use of this decomposition for sparse quantum state preparation. Our results are further validated by demonstrating a proof of principle on a quantum device accessed through quantum cloud services.

arXiv:2302.06377•Feb 13, 2023•4 citations

Design and Optimization of Complex Quantum Circuits Targeting Near-Term Quantum Processors Using Custom Algorithms and Qiskit Transpiler

Kazi Redwan, Mustakim Ahmed, Md. Faruk Abdullah Al Sohan +5 more

Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such as$R_{x}\left(\theta_{1}\right) \cdot R_{x}\left(\theta_{2}\right)$, are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelity$F \geq 0.99$. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such as$e^{i \pi / 4}$are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.

IEEE Region 10 Conference (TENCON)•Oct 27, 2025•0 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

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

Device-Aware Decomposition and Mapping of Multiple-Control Toffoli Circuits in Quantum Computing Systems

Yibo Jiang, Xueyun Cheng, Pengcheng Zhu +2 more

Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.

•Sep 13, 2024•0 citations
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.
We present a method for optimizing quantum circuit compilation by automating the allocation of auxiliary qubits for multi-qubit gate decompositions. This approach is implemented and evaluated within the high-level quantum programming platform Ket. Our results indicate that the decomposition of multi-qubit gates is more effectively handled by the compiler, which has access to all circuit parameters, rather than through a quantum programming API. To evaluate the approach, we compared our implementation against Qiskit, a widely used quantum programming platform, by analyzing two quantum algorithms. Using a 16-qubit QPU, we observed a reduction of 87% in the number of CNOT gates in Grover's algorithm for 9 qubits. For a state preparation algorithm with 7 qubits, the number of CNOT gates was reduced from 2.8×1072.8\times10^72.8×107 to 5.7×1035.7\times10^35.7×103, leveraging additional Ket optimizations for high-level quantum program constructions. Overall, a quadratic reduction in the number of CNOT gates in the final circuit was observed, with greater improvements achieved when more auxiliary qubits were available. These findings underscore the importance of automatic resource management, such as auxiliary qubit allocation, in optimizing quantum applications and improving their suitability for near-term quantum hardware.
Multi-controlled unitary gates have been a subject of interest in quantum computing since its inception, and are widely used in quantum algorithms. The current state-of-the-art approach to implementing n-qubit multi-controlled gates involves the use of a quadratic number of single-qubit and CNOT gates. However, linear solutions are possible for the case where the controlled gate is a special unitary SU(2). The most widely-used decomposition of an n-qubit multi-controlled SU(2) gate requires a circuit with a number of CNOT gates proportional to 28n. In this work, we present a new decomposition of n-qubit multi-controlled SU(2) gates that requires a circuit with a number of CNOT gates proportional to 20n, and proportional to 16n if the SU(2) gate has at least one real-valued diagonal. This new approach significantly improves the existing algorithm by reducing the number of CNOT gates and the overall circuit depth. As an application, we show the use of this decomposition for sparse quantum state preparation. Our results are further validated by demonstrating a proof of principle on a quantum device accessed through quantum cloud services.
Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such asRx(θ1)⋅Rx(θ2)R_{x}\left(\theta_{1}\right) \cdot R_{x}\left(\theta_{2}\right)Rx​(θ1​)⋅Rx​(θ2​), are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelityF≥0.99F \geq 0.99F≥0.99. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such aseiπ/4e^{i \pi / 4}eiπ/4are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.
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.
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.
Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.