Decidable and undecidable problems about quantum automata.

Vincent D. Blondel (1) , Emmanuel Jeandel (1) , Pascal Koiran (1) , Natacha Portier (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Nous étudions le problème suivant : est-ce que le langage reconnu par un certain automate quantique est vide ? Nous savons que ce problème est indécidable dans le cas des automates probabilistes, que le seuil de reconnaissance soit strict ou ne le soit pas. nous montrons que pour les automates quantiques, en revanche, la réponse n'est pas la même dans les deux cas.

Mots clés: Automaton; Decidability; Quantum Computing

Mots clés: Calcul quantique; Automate; Décidabilité

Domaines: Informatique [cs]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier. Decidable and undecidable problems about quantum automata.. [Research Report] LIP RR-2003-24, Laboratoire de l'informatique du parallélisme. 2003, 2+11p. ⟨hal-02101900⟩