2005 • Journal Article
Decidable and undecidable problems about quantum automata
Authors:
Blondel, Vincent ,
Jeandel, E,
Koiran, P,
Portier, N
Published in:
SIAM Journal on Computing
Volume: 34 • Number: 6 • Pages: 1464-1473
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 and nonstrict thresholds both lead to undecidable problems.