Quantum finite automaton

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

The automata work by receiving a finite-length string ${\displaystyle \sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})}$ of letters ${\displaystyle \sigma _{i}}$ from a finite alphabet ${\displaystyle \Sigma }$, and assigning to each such string a probability ${\displaystyle \operatorname {Pr} (\sigma )}$ indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string.

The languages accepted by QFAs are not the regular languages of deterministic finite automata, nor are they the stochastic languages of probabilistic finite automata. Study of these quantum languages remains an active area of research.