Decidable and Undecidable Problems about Quantum Automata

Abstract

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.