Cost-efficient QFA Algorithm for Quantum Computers

2021/07/05 by Salehi, Özlem, Yakaryılmaz, Abuzer
#FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2107.02262

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 \mathttMOD_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 \mathttMOD_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.

Related

• Implementing Quantum Finite Automata Algorithms on Noisy Devices
• Deterministic Construction of QFAs based on the Quantum Fingerprinting Technique
• A Framework for Quantum Finite-State Languages with Density Mapping
• Quantum finite automata: A modern introduction
• A small 1-way quantum finite automaton