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:2501.18677 · Quantum Information and Computation

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

Kamil Ravilevich Khadiev, Aliya Khadieva, Zeyu Chen, Junde Wu

Published Dec 1, 2025• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.2478/qic-2025-0028

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

Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph

Kamil Khadiev, Ilnur Valeev

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

quant-pharXiv:2605.20789•May 21, 2026•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

Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path

Kamil Khadiev, Aliya Khadieva, Vadim Sagitov +2 more

One of the obstacles to the widespread adoption of quantum computing is the problem of efficient circuit synthesis. Current quantum hardware has limited connections between qubits, with each qubit connected to only a few others. This means that the circuit has to be transformed to accommodate this. In this paper, we present an algorithm that converts a circuit containing a sequence of CNOT gates into a form that is suitable for arbitrary quantum computer architectures. Although we demonstrate the algorithm only in the context of quantum fingerprinting, similar gate sequences are prevalent in quantum algorithms; for instance, they are present in the textbook quantum Fourier transform. We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting algorithm) for a quantum device with restrictions on the application of two-qubit gates that are expressed as a qubit connectivity graph. As an example of usage of the technique, we apply it to quantum finite automata recognizing the unary $MOD_p=\{a^\ell: \ell \bmod p=0\}$ language, and the $EQ_p=\{a^\ell b^r: \ell \equiv r \pmod p\}$ language. Given the enhancements that our algorithm provides~-- for instance, in one case it achieves a 16\%--17\% decrease in CNOT circuit cost~-- we believe it could also be useful in a broader quantum compilation context.

quant-pharXiv:2608.09134•Aug 11, 2026•0 citations

Quantum hashing algorithm implementation

Aliya Khadieva

We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. This algorithm is based on a quantum finite automaton for a unary language $\mathtt{MOD_p}$, where $ \mathtt{MOD_p} = \{ a^{i \cdot p} \mid i \geq 0 \} $, for any prime number $p$. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one. We optimize quantum circuits for the quantum hashing algorithm with respect to minimizing the number of control operators as the most expensive ones. We apply the same approach for an optimized circuit implementation of Quantum Fourier Transform (QFT) operation on the aforementioned machines because QFT and hashing circuits have common parts.

arXiv:2407.10136•Jul 14, 2024•2 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
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.
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.
We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has O(n3)O(n^3)O(n3) complexity to build the circuit, where nnn is the number of qubits and mmm is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an O(n3)O(n^3)O(n3)-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.
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.
One of the obstacles to the widespread adoption of quantum computing is the problem of efficient circuit synthesis. Current quantum hardware has limited connections between qubits, with each qubit connected to only a few others. This means that the circuit has to be transformed to accommodate this. In this paper, we present an algorithm that converts a circuit containing a sequence of CNOT gates into a form that is suitable for arbitrary quantum computer architectures. Although we demonstrate the algorithm only in the context of quantum fingerprinting, similar gate sequences are prevalent in quantum algorithms; for instance, they are present in the textbook quantum Fourier transform. We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting algorithm) for a quantum device with restrictions on the application of two-qubit gates that are expressed as a qubit connectivity graph. As an example of usage of the technique, we apply it to quantum finite automata recognizing the unary MODp={aℓ:ℓ mod p=0}MOD_p=\{a^\ell: \ell \bmod p=0\}MODp​={aℓ:ℓmodp=0} language, and the EQp={aℓbr:ℓ≡r(modp)}EQ_p=\{a^\ell b^r: \ell \equiv r \pmod p\}EQp​={aℓbr:ℓ≡r(modp)} language. Given the enhancements that our algorithm provides~-- for instance, in one case it achieves a 16\%--17\% decrease in CNOT circuit cost~-- we believe it could also be useful in a broader quantum compilation context.
We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. This algorithm is based on a quantum finite automaton for a unary language MODp\mathtt{MOD_p}MODp​, where $ \mathtt{MOD_p} = \{ a^{i \cdot p} \mid i \geq 0 \} $, for any prime number ppp. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one. We optimize quantum circuits for the quantum hashing algorithm with respect to minimizing the number of control operators as the most expensive ones. We apply the same approach for an optimized circuit implementation of Quantum Fourier Transform (QFT) operation on the aforementioned machines because QFT and hashing circuits have common parts.
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.