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

Scientific Reports

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

Byeongyong Park, Doyeol Ahn

Published May 27, 2023• 29 citations
Publisher

Abstract

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.

DOI
10.1038/s41598-023-35625-3

Related papers

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

Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs

Kamil Ravilevich Khadiev, Aliya Khadieva, Vadim Sagitov +1 more

In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.

arXiv:2510.09824•Oct 10, 2025•0 citations

Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs Based on 1-Cover Path

Kamil Ravilevich Khadiev, Aliya Khadieva, Vadim Sagitov +1 more

In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. We present a generic method for constructing quantum circuits for QFT on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•1 citation

Experimental demonstration of the Quantum Fourier Transform on up to 100 qubits using a convolutional compilation strategy

Paul Coote, Michael J. Biercuk, Yuval Baum

We present and experimentally validate the `Convolutional QFT': a constructive compilation strategy for the Quantum Fourier Transform (QFT) subroutine on a linear nearest neighbor (LNN) qubit topology. We first introduce a novel strategy that compiles the $n$-qubit QFT onto an LNN topology using only $n^2 - n$ $CX$ gates, matching requirements of a direct compilation on an all-to-all architecture. We then derive the convolutional variant used in our experiments, which requires an additional two $CX$ gates in total, and is realized via a compact, translation-invariant kernel circuit gadget that traverses a quantum register. We demonstrate the power of the convolutional compilation strategy on the IBM Quantum Platform by executing QFT benchmarking circuits. We measure a process fidelity of 11.4% at 50 qubits, and 1.8% at 80 qubits. The correct output state remains clearly distinguishable above background noise up to 100 qubits. These results constitute the largest experimental QFT demonstrated on any quantum computing hardware to date.

quant-pharXiv:2608.05435•Aug 7, 2026•0 citations

Implementation of Quantum Fourier Transform and Quantum Hashing for Quantum Devices with Arbitrary Qubit Connectivity Graphs

Kamil Ravilevich Khadiev, Aliya Khadieva, Zeyu Chen +1 more

Abstract In the paper, we consider quantum circuits for quantum fingerprinting (quantum hashing) and quantum Fourier transform (QFT) algorithms. Quantum fingerprinting (quantum hashing) is a well-known technique for comparing large objects using small images. The QFT algorithm is a very popular technique used in many algorithms. We present a generic method for constructing quantum circuits for these algorithms for quantum devices with restrictions. Many quantum devices (e.g., based on superconductors) have restrictions on applying two-qubit gates. The restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit. The heuristic version of the method is fast enough and works with O ( n 6 ) time complexity, where n is the number of qubits. The certain version of the algorithm has an exponential time complexity that is O ( n 2 2 n ). We compare quantum circuits built by our algorithm with quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, “sun” (a cycle with tails, presented by the 16-qubit IBMQ device) and “two joint suns” (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with a few more CNOT gates. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.

arXiv:2501.18677•Quantum Information and Computation•Dec 1, 2025•5 citations

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•1 citation
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.
In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.
In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. We present a generic method for constructing quantum circuits for QFT on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture.
We present and experimentally validate the `Convolutional QFT': a constructive compilation strategy for the Quantum Fourier Transform (QFT) subroutine on a linear nearest neighbor (LNN) qubit topology. We first introduce a novel strategy that compiles the nnn-qubit QFT onto an LNN topology using only n2−nn^2 - nn2−n CXCXCX gates, matching requirements of a direct compilation on an all-to-all architecture. We then derive the convolutional variant used in our experiments, which requires an additional two CXCXCX gates in total, and is realized via a compact, translation-invariant kernel circuit gadget that traverses a quantum register. We demonstrate the power of the convolutional compilation strategy on the IBM Quantum Platform by executing QFT benchmarking circuits. We measure a process fidelity of 11.4% at 50 qubits, and 1.8% at 80 qubits. The correct output state remains clearly distinguishable above background noise up to 100 qubits. These results constitute the largest experimental QFT demonstrated on any quantum computing hardware to date.
Abstract In the paper, we consider quantum circuits for quantum fingerprinting (quantum hashing) and quantum Fourier transform (QFT) algorithms. Quantum fingerprinting (quantum hashing) is a well-known technique for comparing large objects using small images. The QFT algorithm is a very popular technique used in many algorithms. We present a generic method for constructing quantum circuits for these algorithms for quantum devices with restrictions. Many quantum devices (e.g., based on superconductors) have restrictions on applying two-qubit gates. The restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit. The heuristic version of the method is fast enough and works with O ( n 6 ) time complexity, where n is the number of qubits. The certain version of the algorithm has an exponential time complexity that is O ( n 2 2 n ). We compare quantum circuits built by our algorithm with quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, “sun” (a cycle with tails, presented by the 16-qubit IBMQ device) and “two joint suns” (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with a few more CNOT gates. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.
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.