Cost-efficient QFA Algorithm for Quantum Computers
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
. 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 MOD p = { a j | j ≡ 0 mod p } , where p is a prime number. In this paper, we present a modified MCQFA algorithm for the language 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.