Decidable and Undecidable Problems about Quantum Automata
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier · SIAM Journal on Computing · 2005
We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict andnonstrict thresholds both lead to undecidable problems.