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

Multi-Controlled Quantum Gates in Linear Nearest Neighbor

Ben Zindorf, Sougato Bose

Published May 31, 2025• 1 citation
arXivHTMLPDF

Abstract

Multi-controlled single-target (MC) gates are some of the most crucial building blocks for varied quantum algorithms. How to implement them optimally is thus a pivotal question. To answer this question in an architecture-independent manner, and to get a worst-case estimate, we should look at a linear nearest-neighbor (LNN) architecture, as this can be embedded in almost any qubit connectivity. Motivated by the above, here we describe a method which implements MC gates using no more than $\sim 4k+8n$ CNOT gates -- up-to $60\%$ reduction over state-of-the-art -- while allowing for complete flexibility to choose the locations of $n$ controls, the target, and a dirty ancilla out of $k$ qubits. More strikingly, in case $k \approx n$, our upper bound is $\sim 12n$ -- the best known for unrestricted connectivity -- and if $n = 1$, our upper bound is $\sim 4k$ -- the best known for a single long-range CNOT gate over $k$ qubits -- therefore, if our upper bound can be reduced, then the cost of one or both of these simpler versions of MC gates will be immediately reduced accordingly. In practice, our method provides circuits that tend to require fewer CNOT gates than our upper bound for almost any given instance of MC gates.

DOI
10.48550/arxiv.2506.00695

Related papers

Efficient implementation of multicontrolled quantum gates

Ben Zindorf, Sougato Bose

We present an implementation of multicontrolled () quantum gates that provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (multicontrolled Toffoli), and requires one clean ancilla, no ancilla, or one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor (LNN) connectivity. All of the methods use a linear cost of gates from the Clifford+ T (fault-tolerant) set. In the context of LNN architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, the quadratic-to-linear controlled- count for LNN, they will naturally result in a large reduction of errors.

arXiv:2404.02279•Physical Review Applied•Sep 15, 2025•17 citations

Reducing CNOT count in quantum Fourier transform for the linear nearest-neighbor architecture

Byeongyong Park, Doyeol Ahn

Physical limitations of quantum hardware often necessitate nearest-neighbor (NN) architecture. When synthesizing quantum circuits using the basic gate library, which consists of CNOT and single-qubit gates, CNOT gates are required to convert a quantum circuit into one suitable for an NN architecture. In the basic gate library, CNOT gates are considered the primary cost of quantum circuits due to their higher error rates and longer execution times compared to single-qubit gates. In this paper, we propose a new linear NN (LNN) circuit design for quantum Fourier transform (QFT), one of the most versatile subroutines in quantum algorithms. Our LNN QFT circuit has only about 40% of the number of CNOT gates compared to previously known LNN QFT circuits. Subsequently, we input both our QFT circuits and conventional QFT circuits into the Qiskit transpiler to construct QFTs on IBM quantum computers, which necessitate NN architectures. Consequently, our QFT circuits demonstrate a substantial advantage over conventional QFT circuits in terms of the number of CNOT gates. This outcome implies that the proposed LNN QFT circuit design could serve as a novel foundation for developing QFT circuits implemented in quantum hardware that demands NN architecture.

Scientific Reports•May 27, 2023•29 citations

Optimizing the number of CNOT gates in one-dimensional nearest-neighbor quantum Fourier transform circuit

Byeongyong Park, Doyeol Ahn

The physical limitations of quantum hardware often require nearest-neighbor qubit structures, in which two-qubit gates are required to construct nearest-neighbor quantum circuits. However, two-qubit gates are considered a major cost of quantum circuits because of their high error rate as compared with single-qubit gates. The controlled-not (CNOT) gate is the typical choice of a two-qubit gate for universal quantum circuit implementation together with the set of single-qubit gates. In this study, we construct a one-dimensional nearest-neighbor circuit of quantum Fourier transform (QFT), which is one of the most frequently used quantum algorithms. Compared with previous studies on n-qubit one-dimensional nearest-neighbor QFT circuits, it is found that our method reduces the number of CNOT gates by ~60%. Additionally, we showed that our results for the one-dimensional nearest-neighbor circuit can be applied to quantum amplitude estimation.

arXiv:2208.14249•Aug 30, 2022•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

Circuit Decomposition of Multicontrolled Special Unitary Single-Qubit Gates

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

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.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 24, 2023•23 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•0 citations
Multi-controlled single-target (MC) gates are some of the most crucial building blocks for varied quantum algorithms. How to implement them optimally is thus a pivotal question. To answer this question in an architecture-independent manner, and to get a worst-case estimate, we should look at a linear nearest-neighbor (LNN) architecture, as this can be embedded in almost any qubit connectivity. Motivated by the above, here we describe a method which implements MC gates using no more than ∼4k+8n\sim 4k+8n∼4k+8n CNOT gates -- up-to 60%60\%60% reduction over state-of-the-art -- while allowing for complete flexibility to choose the locations of nnn controls, the target, and a dirty ancilla out of kkk qubits. More strikingly, in case k≈nk \approx nk≈n, our upper bound is ∼12n\sim 12n∼12n -- the best known for unrestricted connectivity -- and if n=1n = 1n=1, our upper bound is ∼4k\sim 4k∼4k -- the best known for a single long-range CNOT gate over kkk qubits -- therefore, if our upper bound can be reduced, then the cost of one or both of these simpler versions of MC gates will be immediately reduced accordingly. In practice, our method provides circuits that tend to require fewer CNOT gates than our upper bound for almost any given instance of MC gates.
We present an implementation of multicontrolled () quantum gates that provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (multicontrolled Toffoli), and requires one clean ancilla, no ancilla, or one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor (LNN) connectivity. All of the methods use a linear cost of gates from the Clifford+ T (fault-tolerant) set. In the context of LNN architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, the quadratic-to-linear controlled- count for LNN, they will naturally result in a large reduction of errors.
Physical limitations of quantum hardware often necessitate nearest-neighbor (NN) architecture. When synthesizing quantum circuits using the basic gate library, which consists of CNOT and single-qubit gates, CNOT gates are required to convert a quantum circuit into one suitable for an NN architecture. In the basic gate library, CNOT gates are considered the primary cost of quantum circuits due to their higher error rates and longer execution times compared to single-qubit gates. In this paper, we propose a new linear NN (LNN) circuit design for quantum Fourier transform (QFT), one of the most versatile subroutines in quantum algorithms. Our LNN QFT circuit has only about 40% of the number of CNOT gates compared to previously known LNN QFT circuits. Subsequently, we input both our QFT circuits and conventional QFT circuits into the Qiskit transpiler to construct QFTs on IBM quantum computers, which necessitate NN architectures. Consequently, our QFT circuits demonstrate a substantial advantage over conventional QFT circuits in terms of the number of CNOT gates. This outcome implies that the proposed LNN QFT circuit design could serve as a novel foundation for developing QFT circuits implemented in quantum hardware that demands NN architecture.
The physical limitations of quantum hardware often require nearest-neighbor qubit structures, in which two-qubit gates are required to construct nearest-neighbor quantum circuits. However, two-qubit gates are considered a major cost of quantum circuits because of their high error rate as compared with single-qubit gates. The controlled-not (CNOT) gate is the typical choice of a two-qubit gate for universal quantum circuit implementation together with the set of single-qubit gates. In this study, we construct a one-dimensional nearest-neighbor circuit of quantum Fourier transform (QFT), which is one of the most frequently used quantum algorithms. Compared with previous studies on n-qubit one-dimensional nearest-neighbor QFT circuits, it is found that our method reduces the number of CNOT gates by ~60%. Additionally, we showed that our results for the one-dimensional nearest-neighbor circuit can be applied to quantum amplitude estimation.
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.
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.
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.