Implementing Quantum Finite Automata Algorithms on Noisy Devices

2021

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 \(\mathtt {MOD}_\mathrm{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 \(\mathtt {MOD}_\mathrm{p}\) problem using the Qiskit framework. We focus on the case \(p=11\) and provide a 3 qubit implementation for the \(\mathtt {MOD}_\mathrm{11}\) problem reducing the total number of requi…