Decidable and undecidable problems about quantum automata
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
10 pages
10 pages