Tutorial introduction to classical and quantum automata

We start with a discussion on computational problems and algorithms. We define a generic form of decision problems, and then introduce deterministic finite automaton (DFA) as a basic decider. After having a few examples on the DFAs with discussions on their limitations, we introduce their probabilistic and quantum variants. We present a representative algorithm for each of these variants, followed by a discussion on the quantum advantages in finite automata settings. We shortly review the recent implementations of QFA algorithms on real quantum hardware.

Dr Yakaryilmaz works at the Center for Quantum Computing Science, University of Latvia (https://quantum.lu.lv/). He is also one of the founders of the QWorld organization (https://qworld.net/), which promotes the use of quantum computing.