Quantum automata and algebraic groups.

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