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:2407.10136

Quantum hashing algorithm implementation

Aliya Khadieva

Published Jul 14, 2024• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2407.10136

Related papers

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

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

Efficient Implementation of Amplitude Form of Quantum Hashing Using State-of-the-Art Quantum Processors

I. Zinnatullin, Kamil Ravilevich Khadiev, Aliya Khadieva

Abstract Current physical limitations require quantum circuits to be transformed to fit the nearest-neighbor architecture. To achieve this, we usually use different techniques such as nearest-neighbor decomposition. In this work, we optimize quantum circuits implementing quantum hashing for quantum computers with specific architecture provided by IBM Q Platform. The optimization is done by reducing the number of used CNOT gates. We show how to choose the best position for the target qubit to get optimal circuits for the considered architectures.

Russian Microelectronics•Dec 1, 2023•10 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

Shallow implementation of quantum fingerprinting with application to quantum finite automata

Mansur Ziatdinov, Aliya Khadieva, Kamil Ravilevich Khadiev

Quantum fingerprinting is a technique that maps a classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses fewer resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is the quantum automata algorithm for M O D p = { a i · p ∣ i ≥ 0 } languages, where p is a prime number. However, implementing such an automaton on current quantum hardware is not efficient. Quantum fingerprinting maps a word x ∈{0, 1} n of length n to a state |ψ( x )〉 of O (log n ) qubits, and uses O ( n ) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to many quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width, in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods. We provide a series of numerical experiments with implementation of the quantum automata for MOD 17 language on noisy simulators of IBMQ quantum devices. We show that shallow implementation based on GAPs produces results with much smaller computational error compared to standard deep circuit implementation. Despite the fact that on the ideal quantum computational device, the opposite situation arises. We show that the shallow circuit for the quantum automaton is better for near-future quantum computational devices.

arXiv:2412.18823•Frontiers in Computer Science•May 16, 2025•9 citations

Optimisation of circuit for quantum automata

Aliya Khadieva

he paper considers the implementation of a finite quantum automaton, recognizing the unary language MOD_p using the qiskit library and the language python programming. We also present an optimization of the quantum schemes for implementing the distributed controlled algorithm rotation used in the implementation of the aforementioned quantum machine.

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations
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 MODp={ai⋅p∣i≥0}\mathtt{MOD_p} = \{ a^{i \cdot p} \mid i \geq 0 \}MODp​={ai⋅p∣i≥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.
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.
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.
Abstract Current physical limitations require quantum circuits to be transformed to fit the nearest-neighbor architecture. To achieve this, we usually use different techniques such as nearest-neighbor decomposition. In this work, we optimize quantum circuits implementing quantum hashing for quantum computers with specific architecture provided by IBM Q Platform. The optimization is done by reducing the number of used CNOT gates. We show how to choose the best position for the target qubit to get optimal circuits for the considered architectures.
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.
Quantum fingerprinting is a technique that maps a classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses fewer resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is the quantum automata algorithm for M O D p = { a i · p ∣ i ≥ 0 } languages, where p is a prime number. However, implementing such an automaton on current quantum hardware is not efficient. Quantum fingerprinting maps a word x ∈{0, 1} n of length n to a state |ψ( x )〉 of O (log n ) qubits, and uses O ( n ) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to many quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width, in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods. We provide a series of numerical experiments with implementation of the quantum automata for MOD 17 language on noisy simulators of IBMQ quantum devices. We show that shallow implementation based on GAPs produces results with much smaller computational error compared to standard deep circuit implementation. Despite the fact that on the ideal quantum computational device, the opposite situation arises. We show that the shallow circuit for the quantum automaton is better for near-future quantum computational devices.