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:2208.14249 · Scientific Reports

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

Byeongyong Park, Doyeol Ahn

Published May 27, 2023• 34 citations
arXivHTMLPDF

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

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

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

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

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.

Quantum Information and Computation•Jan 1, 2011•79 citations

An Efficient Method to Convert Arbitrary Quantum Circuits to Ones on a Linear Nearest Neighbor Architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2009•73 citations
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.
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.
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.
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.
Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.
A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.