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• 7 citations
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•50 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

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.

arXiv:2208.14249•Scientific Reports•May 27, 2023•34 citations

Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Amlan Chakrabarti, Susmita Sur‐Kolay, Ayan Chaudhury

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

arXiv:1112.0564•Dec 2, 2011•58 citations

Quantum circuits with uniformly controlled one-qubit gates

Ville Bergholm, Juha J. Vartiainen, Mikko Möttönen +1 more

Uniformly controlled one-qubit gates are quantum gates which can be represented as direct sums of two-dimensional unitary operators acting on a single qubit. We present a quantum gate array which implements any $n$-qubit gate of this type using at most ${2}^{n\ensuremath{-}1}\ensuremath{-}1$ controlled-NOT gates, ${2}^{n\ensuremath{-}1}$ one-qubit gates, and a single diagonal $n$-qubit gate. To illustrate the versatility of these gates we then apply them to the decomposition of a general $n$-qubit gate and a state preparation procedure. Moreover, we study their implementation using only nearest-neighbor gates. We give upper bounds for the one-qubit and controlled-NOT gate counts for all the aforementioned applications. In all four cases, the proposed circuit topologies either improve on or achieve the previously reported upper bounds for the gate counts. Thus, they provide the most efficient method for general gate decompositions currently known.

arXiv:quant-ph/0410066•Physical Review A•May 27, 2005•179 citations

Implementation of quantum gate operations using neural networks

Shahri A. Zabihi

All quantum circuits are designed using different quantum gates, which can be decomposed into elementary gates. The number of elementary gates in a quantum circuit is called the gate count. Typically, there is a direct correspondence between the gate count and the complexity of a quantum circuit. Quantum systems are generally very fragile, and a quantum bit (qubit) can lose its super-position state very easily. This process is called decoherence. As such, when implementing a quantum operation, it becomes necessary to minimize the gate count as much as possible. This thesis focuses on two important applications where reducing the gate count is very significant. The first is quantum error correction (QEC). In a quantum error correction code (QECC), one information qubit is encoded with two or more auxiliary qubits to form a logical/encoded qubit. Oftentimes, when performing gate operations on logical qubits, decoding is required, which opens the system to decoherence. The aim here is to design encoded quantum gates in such a way that the decoding process is no longer needed for implementing gate operations on QEC circuits. The second focus is a controlled-NOT (CNOT) gate operation between uncoupled (remote) qubits. In order to implement a gate operation in a linear nearest neighbor (LNN) architecture, the qubits that are not neighbors need to be brought adjacent to each other before a gate operation can be performed between them. The LNN architecture is significant because most physical implementations of a practical quantum computer use this layout. Here, the aim is to implement a CNOT gate between remote qubits in an LNN architecture without bringing the qubits adjacent to each other, thereby tremendously reducing the gate count. This research employed a neural network approach based on gradient descent technique to reduce the gate count.

•May 1, 2017•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.
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 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.
Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.
Uniformly controlled one-qubit gates are quantum gates which can be represented as direct sums of two-dimensional unitary operators acting on a single qubit. We present a quantum gate array which implements any nnn-qubit gate of this type using at most ${2}^{n\ensuremath{-}1}\ensuremath{-}1$ controlled-NOT gates, ${2}^{n\ensuremath{-}1}$ one-qubit gates, and a single diagonal nnn-qubit gate. To illustrate the versatility of these gates we then apply them to the decomposition of a general nnn-qubit gate and a state preparation procedure. Moreover, we study their implementation using only nearest-neighbor gates. We give upper bounds for the one-qubit and controlled-NOT gate counts for all the aforementioned applications. In all four cases, the proposed circuit topologies either improve on or achieve the previously reported upper bounds for the gate counts. Thus, they provide the most efficient method for general gate decompositions currently known.
All quantum circuits are designed using different quantum gates, which can be decomposed into elementary gates. The number of elementary gates in a quantum circuit is called the gate count. Typically, there is a direct correspondence between the gate count and the complexity of a quantum circuit. Quantum systems are generally very fragile, and a quantum bit (qubit) can lose its super-position state very easily. This process is called decoherence. As such, when implementing a quantum operation, it becomes necessary to minimize the gate count as much as possible. This thesis focuses on two important applications where reducing the gate count is very significant. The first is quantum error correction (QEC). In a quantum error correction code (QECC), one information qubit is encoded with two or more auxiliary qubits to form a logical/encoded qubit. Oftentimes, when performing gate operations on logical qubits, decoding is required, which opens the system to decoherence. The aim here is to design encoded quantum gates in such a way that the decoding process is no longer needed for implementing gate operations on QEC circuits. The second focus is a controlled-NOT (CNOT) gate operation between uncoupled (remote) qubits. In order to implement a gate operation in a linear nearest neighbor (LNN) architecture, the qubits that are not neighbors need to be brought adjacent to each other before a gate operation can be performed between them. The LNN architecture is significant because most physical implementations of a practical quantum computer use this layout. Here, the aim is to implement a CNOT gate between remote qubits in an LNN architecture without bringing the qubits adjacent to each other, thereby tremendously reducing the gate count. This research employed a neural network approach based on gradient descent technique to reduce the gate count.