The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijanis

We present a language $L_n$ which is recognizable by a probabilistic finite automaton (PFA) with probability $1-\epsilon$ for all $\epsilon >0$ with $O(lo{g}^{2}n)$ states, with a deterministic fi…