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:2302.06377 · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Circuit Decomposition of Multicontrolled Special Unitary Single-Qubit Gates

Rafaella F. Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo, Israel F. Araujo, Adenilton José da Silva

Published Oct 24, 2023• 59 citations
arXivHTMLPDF

Abstract

Multicontrolled unitary gates have been a subject of interest in quantum computing since their conception and are widely used in quantum algorithms. The current state-of-the-art approach to implementing$n$-qubit multicontrolled gates with a single target without relying on auxiliary qubits or approximate results 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 special unitary, SU(2). The decomposition of an$n$-qubit multicontrolled 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 multicontrolled SU(2) gates that require 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. The proposed algorithms produce the most efficient known circuits and improve 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.

DOI
10.1109/tcad.2023.3327102

Related papers

Linear Decomposition of Approximate Multicontrolled Single Qubit Gates

Jefferson D. S. Silva, Thiago Melo D. Azevedo, Israel F. Araujo +1 more

We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.

arXiv:2310.14974•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 1, 2024•6 citations

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits

Jefferson D. S. Silva, Adenilton José da Silva

The synthesis of quantum operators involves decomposing general quantum gates into the gate set supported by a given quantum device. Multi-controlled gates are essential components in this process. In this work, we present an improved decomposition of multi-controlled NOT gates with logarithmic depth using a single ancilla qubit while reducing the ancillary resource requirements compared to previous work. We further introduce a relative-phase multi-controlled NOT gate that eliminates the need for ancillas. Building on these results, we optimize a previously proposed decomposition of multi-target, multi-controlled special unitary SU(2) gates by identifying the presence of a conditionally clean qubit. Additionally, we introduce the best-known decomposition of multi-controlled approximate unitary U(2) gates, which do not require ancilla qubits. This approach significantly reduces the overall circuit depth and CNOT count while preserving an adjustable error parameter, yielding a more efficient and scalable solution for synthesizing large controlled-unitary gates. Our method is particularly suitable for both NISQ and fault-tolerant quantum architectures. All software developed in this project is freely available.

arXiv:2507.00400•Jul 1, 2025•5 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•387 citations

Linear-depth quantum circuits for multiqubit controlled gates

Adenilton José da Silva, Daniel K. Park

Quantum circuit depth minimization is critical for practical applications of circuit-based quantum computation. In this work, we present a systematic procedure to decompose multiqubit controlled unitary gates, which is essential in many quantum algorithms, to controlled-not and single-qubit gates with which the quantum circuit depth only increases linearly with the number of control qubits. Our algorithm does not require any ancillary qubits and achieves a quadratic reduction of the circuit depth against known methods. We show the advantage of our algorithm with proof-of-principle demonstrations on the IBM quantum cloud platform.

arXiv:2203.11882•Physical Review A•Oct 4, 2022•68 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•1 citation

Constructing quantum circuits with global gates

John van de Wetering

Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.

arXiv:2012.09061•New Journal of Physics•Mar 24, 2021•44 citations
Multicontrolled unitary gates have been a subject of interest in quantum computing since their conception and are widely used in quantum algorithms. The current state-of-the-art approach to implementingnnn-qubit multicontrolled gates with a single target without relying on auxiliary qubits or approximate results 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 special unitary, SU(2). The decomposition of annnn-qubit multicontrolled SU(2) gate requires a circuit with a number of CNOT gates proportional to28n28n28n. In this work, we present a new decomposition ofnnn-qubit multicontrolled SU(2) gates that require a circuit with a number of CNOT gates proportional to20n20n20nand proportional to16n16n16nif the SU(2) gate has at least one real-valued diagonal. The proposed algorithms produce the most efficient known circuits and improve 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.
We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.
The synthesis of quantum operators involves decomposing general quantum gates into the gate set supported by a given quantum device. Multi-controlled gates are essential components in this process. In this work, we present an improved decomposition of multi-controlled NOT gates with logarithmic depth using a single ancilla qubit while reducing the ancillary resource requirements compared to previous work. We further introduce a relative-phase multi-controlled NOT gate that eliminates the need for ancillas. Building on these results, we optimize a previously proposed decomposition of multi-target, multi-controlled special unitary SU(2) gates by identifying the presence of a conditionally clean qubit. Additionally, we introduce the best-known decomposition of multi-controlled approximate unitary U(2) gates, which do not require ancilla qubits. This approach significantly reduces the overall circuit depth and CNOT count while preserving an adjustable error parameter, yielding a more efficient and scalable solution for synthesizing large controlled-unitary gates. Our method is particularly suitable for both NISQ and fault-tolerant quantum architectures. All software developed in this project is freely available.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
Quantum circuit depth minimization is critical for practical applications of circuit-based quantum computation. In this work, we present a systematic procedure to decompose multiqubit controlled unitary gates, which is essential in many quantum algorithms, to controlled-not and single-qubit gates with which the quantum circuit depth only increases linearly with the number of control qubits. Our algorithm does not require any ancillary qubits and achieves a quadratic reduction of the circuit depth against known methods. We show the advantage of our algorithm with proof-of-principle demonstrations on the IBM quantum cloud platform.
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.
Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.