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:2412.18823 · Frontiers in Computer Science

Shallow implementation of quantum fingerprinting with application to quantum finite automata

Mansur Ziatdinov, Aliya Khadieva, Kamil Ravilevich Khadiev

Published May 16, 2025• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.3389/fcomp.2025.1519212

Related papers

GAPs for Shallow Implementation of Quantum Finite Automata

Mansur Ziatdinov, Aliya Khadieva, Abuzer Yakaryılmaz

Quantum fingerprinting is a technique that maps classical input word to a quantum state.The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography.One of the examples of quantum fingerprinting is quantum automata algorithms for MOD p = {a i•p | i ≥ 0} languages, where p is a prime number.However, implementing such an automaton on the 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 a large number of 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.

arXiv:2304.12868•Electronic Proceedings in Theoretical Computer Science•Sep 3, 2023•10 citations

State-efficient QFA Algorithm for Quantum Computers.

Özlem Salehi, Abuzer Yakaryılmaz

The study of quantum finite automata (QFA's) is one of the possible approaches in exploring quantum computers with finite memory. Despite being one of the most restricted models, Moore-Crutchfield quantum finite automaton (MCQFA) is proven to be exponentially more succinct than classical finite automata models in recognizing certain languages such as $\mathtt{MOD}_{\rm p} = \{a^{j}~ |~ j \equiv 0 \mod p\}$, where $p$ is a prime number. In this paper, we present a modified MCQFA algorithm for the language $\mathtt{MOD}_{\rm p}$, the operators of which are selected based on the basis gates on the available real quantum computers. As a consequence, we obtain shorter quantum programs using less basis gates compared to the implementation of the original algorithm given in the literature.

•Jul 5, 2021•1 citation

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

Cost-efficient QFA Algorithm for Quantum Computers

Özlem Salehi, Abuzer Yakaryılmaz

The study of quantum finite automata (QFAs) is one of the possible approaches in exploring quantum computers with finite memory. Despite being one of the most restricted models, Moore-Crutchfield quantum finite automaton (MCQFA) is proven to be exponentially more succinct than classical finite automata models in recognizing certain languages such as $\mathtt{MOD}_p = \{ a^{j} \mid j \equiv 0 \mod p\}$, where $p$ is a prime number. In this paper, we present a modified MCQFA algorithm for the language $\mathtt{MOD}_p$, the operators of which are selected based on the basis gates on the available real quantum computers. As a consequence, we obtain shorter quantum programs using fewer basis gates compared to the implementation of the original algorithm given in the literature.

arXiv:2107.02262•Jul 5, 2021•3 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

Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique

Aliya Khadieva, Mansur Ziatdinov

It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language $$MOD_{p}$$ has an exponential advantage over the classical finite automata. However, the construction of such QFA is probabilistic. In the current work, we propose a deterministic construction of the QFA for the language $$MOD_{p}$$ . We construct a QFA for a promise problem $$Palindrome_{s}$$ and implement this QFA on the IBMQ simulator using qiskit library tools.

arXiv:2212.14442•Lobachevskii Journal of Mathematics•Feb 1, 2023•6 citations
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.
Quantum fingerprinting is a technique that maps classical input word to a quantum state.The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography.One of the examples of quantum fingerprinting is quantum automata algorithms for MOD p = {a i•p | i ≥ 0} languages, where p is a prime number.However, implementing such an automaton on the 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 a large number of 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.
The study of quantum finite automata (QFA's) is one of the possible approaches in exploring quantum computers with finite memory. Despite being one of the most restricted models, Moore-Crutchfield quantum finite automaton (MCQFA) is proven to be exponentially more succinct than classical finite automata models in recognizing certain languages such as MODp={aj ∣ j≡0mod  p}\mathtt{MOD}_{\rm p} = \{a^{j}~ |~ j \equiv 0 \mod p\}MODp​={aj ∣ j≡0modp}, where ppp is a prime number. In this paper, we present a modified MCQFA algorithm for the language MODp\mathtt{MOD}_{\rm p}MODp​, the operators of which are selected based on the basis gates on the available real quantum computers. As a consequence, we obtain shorter quantum programs using less basis gates compared to the implementation of the original algorithm given in the literature.
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.
The study of quantum finite automata (QFAs) is one of the possible approaches in exploring quantum computers with finite memory. Despite being one of the most restricted models, Moore-Crutchfield quantum finite automaton (MCQFA) is proven to be exponentially more succinct than classical finite automata models in recognizing certain languages such as MODp={aj∣j≡0mod  p}\mathtt{MOD}_p = \{ a^{j} \mid j \equiv 0 \mod p\}MODp​={aj∣j≡0modp}, where ppp is a prime number. In this paper, we present a modified MCQFA algorithm for the language MODp\mathtt{MOD}_pMODp​, the operators of which are selected based on the basis gates on the available real quantum computers. As a consequence, we obtain shorter quantum programs using fewer basis gates compared to the implementation of the original algorithm given in the literature.
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.
It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language MODpMOD_{p}MODp​ has an exponential advantage over the classical finite automata. However, the construction of such QFA is probabilistic. In the current work, we propose a deterministic construction of the QFA for the language MODpMOD_{p}MODp​ . We construct a QFA for a promise problem PalindromesPalindrome_{s}Palindromes​ and implement this QFA on the IBMQ simulator using qiskit library tools.