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• 10 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•12 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•5 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•7 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

Efficient Equivalent of Shallow Quantum Hashing

Ilnar Zinnatullin, Alexander Vasiliev

Quantum hashing is a widely used technique in quantum computation that allows us to design space-efficient algorithms and protocols. Recently, Vasiliev has shown that the phase form of shallow quantum hashing can be implemented by a circuit of depth 2. In this paper, we establish a connection between shallow quantum hashing and single-qubit quantum hashing for the amplitude form. For a shallow circuit, we propose a circuit of depth 1 that achieves the same collision resistance.

quant-pharXiv:2511.19292•Nov 25, 2025•0 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.
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.