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:2404.02279 · Physical Review Applied

Efficient implementation of multicontrolled quantum gates

Ben Zindorf, Sougato Bose

Published Sep 15, 2025• 50 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/8blx-nfcr

Related papers

Multi-Controlled Quantum Gates in Linear Nearest Neighbor

Ben Zindorf, Sougato Bose

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.

arXiv:2506.00695•May 31, 2025•7 citations

Efficient implementation of multi-control Toffoli gates in linear nearest neighbor arrays

Saman Daraeizadeh

Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.

•May 1, 2014•1 citation

Techniques for fault-tolerant decomposition of a multicontrolled Toffoli gate

Laxmidhar Biswal, Debjyoti Bhattacharjee, Anupam Chattopadhyay +1 more

Physical implementation of scalable quantum architectures faces an immense challenge in the form of fragile quantum states. To overcome it, quantum architectures with fault tolerance are desirable. These are achieved currently by using a surface code along with a transversal gate set. This indicates the need for decomposition of universal $n$-qubit multicontrolled Toffoli ($n$-MCT) gates using a transversal gate set. Additionally, the transversal non-Clifford phase gate incurs high latency, which makes it an important factor to consider during decomposition. Additionally, the decomposition of a large MCT gate without ancillas presents an additional hurdle. In this paper, we address both of these issues by introducing the $\mathrm{Clifford}+{Z}_{N}$ gate library. We present an ancilla-free decomposition of MCT gates with linear phase depth and quadratic phase count. Furthermore, we provide a technique for decomposition of MCT gates in unit phase depth using the $\mathrm{Clifford}+{Z}_{N}$ library, albeit at the cost of ancillary lines and exponential phase count.

arXiv:1904.06920•Physical Review A•Dec 19, 2019•27 citations

Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla

Abhoy Kole, Majd Assaad, Till Schnittka +1 more

Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.

quant-pharXiv:2605.18169•May 19, 2026•1 citation

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
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.
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.
Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.
Physical implementation of scalable quantum architectures faces an immense challenge in the form of fragile quantum states. To overcome it, quantum architectures with fault tolerance are desirable. These are achieved currently by using a surface code along with a transversal gate set. This indicates the need for decomposition of universal nnn-qubit multicontrolled Toffoli (nnn-MCT) gates using a transversal gate set. Additionally, the transversal non-Clifford phase gate incurs high latency, which makes it an important factor to consider during decomposition. Additionally, the decomposition of a large MCT gate without ancillas presents an additional hurdle. In this paper, we address both of these issues by introducing the Clifford+ZN\mathrm{Clifford}+{Z}_{N}Clifford+ZN​ gate library. We present an ancilla-free decomposition of MCT gates with linear phase depth and quadratic phase count. Furthermore, we provide a technique for decomposition of MCT gates in unit phase depth using the Clifford+ZN\mathrm{Clifford}+{Z}_{N}Clifford+ZN​ library, albeit at the cost of ancillary lines and exponential phase count.
Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.
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.