Techniques algébriques en calcul quantique
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
The main problem studied is the computation of the Zariski closure of algebraic groups and its applications on quantum computation. We give a polynomial time algorithm to decide whether a finitely generated subgroup of a given reductive group is Zariski-dense. A second algorithm, which computes precisely the Zariski-closure of a finitely generated group is given. These tools gives decidability results for several problems in quantum computing, mainly whether a set of gates is universal. We give also a separation between various models of quantum computing An other part of the thesis deals with finite automata. A new model of automata, topological automata, is defined. We then proved in a unified framework that all models of classical, probabilistic and quantum automata accept only regular languages with an isolated threshold.
Abstract FR:
Le principal problème étudié est le calcul de l'adhérence de Zariski de groupes algébriques, et leurs applications en calcul quantique. On donne ici un algorithme en temps polynomial qui décide si un sous-groupe finiment engendré d'un groupe reductif est dense dans ce groupe. On donne également un algorithme qui calcule précisément l'adhérence d'un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d'universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d'automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé.