Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique
Aliya Khadieva, Mansur Ziatdinov · Lobachevskii Journal of Mathematics · 2023
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.