Quantum automata and algebraic groups.

Harm Derksen (1) , Emmanuel Jeandel (1) , Pascal Koiran (1)

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

We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

Nous montrons ici que plusieurs problèmes indécidables pour des automates probabilistes sont décidables pour des automates quantiques.Ce résultat s’appuie sur un algorithme intéressant en soi, qui, étant donné des matrices inversibles, calcule la clôture de Zariski du groupe engendré par ses matrices.

Mots clés: Algebraic Geometry; Algebraic Groups; Probabilistic Automata; Quantum Automata; Undecidability

Mots clés: Automates quantiques; Géométrie algébrique; Automates probabilistes; Indécidabilité; Groupes algébriques

Domaines: Informatique [cs]

Harm Derksen, Emmanuel Jeandel, Pascal Koiran. Quantum automata and algebraic groups.. [Research Report] LIP RR-2003-39, Laboratoire de l'informatique du parallélisme. 2003, 2+15p. ⟨hal-02101965⟩