Implementing Quantum Finite Automata Algorithms on Noisy Devices
Quantum finite automata (QFAs) literature offers an alternative mathematical
model for studying quantum systems with finite memory. As a superiority of
quantum computing, QFAs have been shown exponentially more succinct on certain
problems such as recognizing the language $ MOD_p = \{a^j \mid j \equiv 0 \mod
p\} $ with bounded error, where $p$ is a prime number. In this paper we present
improved circuit based implementations for QFA algorithms recognizing the $
MOD_p $ problem using the Qiskit framework. We focus on the case $p=11$ and
provide a 3 qubit implementation for the $MOD_{11}$ problem reducing the total
number of required gates using alternative approaches. We run the circuits on
real IBM quantum devices but due to the limitation of the real quantum devices
in the NISQ era, the results are heavily affected by the noise. This limitation
reveals once again the need for algorithms using less amount of resources.
Consequently, we consider an alternative 3 qubit implementation which works
better in practice and obtain promising results even for the problem $ MOD_{31}
$.
Utku Birkan Özlem Salehi Viktor Olejar Cem Nurlu Abuzer Yakaryılmaz