L'étude des structures fondamentales du traitement de l'information quantique est un défi majeur, dont l'un des objectifs est de mieux cerner les capacités et les limites de l'ordinateur quantique, tout en contribuant à sa réalisation physique notamment en s'intéressant aux ressources du calcul quantique. Les ressources d'un calcul quantique incluent le temps et l'espace mais également la taille des opérations utilisées et la quantité d'intrication. <br /> Cette thèse contribue de plusieurs manières à la recherche de ressources minimales dans le cadre de modèles de calcul quantique ouvrant de prometteuses perspectives de réalisations physiques. Ces modèles sont le calcul par consommation d'intrication et le calcul par mesures projectives. Cette thèse a également permis de réduire les ressources en temps et en espace nécessaires à la préparation de certains états quantiques, les états graphes. <br /> Etudier la réduction des ressources nécessite l'abstraction et la formalisation des modèles de calcul quantique mettant en évidence les structures même du traitement de l'information quantique. Le q-calcul et les machines de Turing contrôlées classiquement, introduits dans cette thèse, ont cet objectif. Des modèles plus spécifiques au calcul par consommation d'intrication, ou au calcul par mesures projectives sont également considérés.

Cette thèse a pour cadre la spécification et la vérification de systèmes informatiques distribués, concurrents ou réactifs au moyen de graphes infinis associés à des spécifications de Thue et à certaines machines. Nous montrons que la classe des graphes des spécifications de Thue est fermée par produit synchronisé. Nous établissons aussi ce fait pour la classe des graphes des machines de Turing et pour certaines de ses sous-classes. Nous nous intéressons également à la conservation par produit synchronisé de la décidabilité de la théorie du premier ordre de graphes infinis. Nous montrons que le produit synchronisé de graphes de machines à pile restreint à sa partie accessible depuis un sommet donné à une théorie du premier ordre qui n'est pas décidable. Cependant, le produit synchronisé de graphes sans racine distinguée et dont la théorie du premier oordre est décidable a une théorie du premier ordre qui est décidable. Enfin nous mettons en évidence des liens qui unissent les graphes des machines de Turing à ceux des spécifications de Thue.

Cette thèse s'inscrit dans le contexte du calcul en temps infini. Par cette désignation, nous faisons référence au temps indicé par des ordinaux, ces derniers possédant de bonnes propriétés pour ``compter''en leur long. En 2000, le modèle des machines de Turing à temps infini fut proposé par Hamkins et Lewis. Ce modèle généralise le processus de calcul des machines de Turing aux étapes de temps représentées par des ordinaux. Dans ce modèle de calcul, les étapes sont indicées par des ordinaux dénombrables, bien que le ruban soit toujours indicé par des entiers naturels. Les entrées du modèle sont donc les suites infinies de lettres. Un certain nombre de comportements nouveaux et étonnants apparaissent avec ces machines. Dans notre thèse, nous nous intéressons à certains de ces comportements.Naturellement, plus les temps de calcul sont longs, plus le modèle est puissant, et plus il devient possible de décider de nouveaux ensembles.À partir d’ordinaux assez grands, de nouvelles propriétés structurelles apparaissent également. L'une d'entre elles est l'existence de brèches dans les temps possibles d'arrêts de programmes. Lorsque ces brèches furent découvertes, de premiers liens entre elles et le caractère admissible des ordinaux qui les commencent furent établis. Notre approche utilise l'algorithmique pour préciser les liens entre les propriétés logiques des ordinaux et les propriétés calculatoires de ces machines à temps infini.Plus précisément, grâce à des des algorithmes spécifiques, nous découvrons et prouvons de nouvelles propriétés sur ces brèches,amenant à une meilleure compréhension de leur structure. Nous montrons notamment que les brèches peuvent être de toutes les tailles (limites) écrivables, qu'il en existe même de taille au moins aussi grande que leur ordinal de début. Jusqu’à la première brèche ayant cette caractéristique, la structure des brèches est assez proche de celle des ordinaux : elles apparaissent en ordre croissant en fonction de leur taille. Nous montrons également que jusqu'à cette brèche spéciale, si les ordinaux admissibles sont exactement les ordinaux débutant les brèches, au-dessus, des ordinaux admissibles peuvent apparaître au milieu de très grandes brèches et la structure des brèches devient désordonnée. / This thesis is centred on the study of infinite time computations. Infinite time here means having a time axis indexed by ordinals — the ordinals are convenient objects along which we can count. The infinite time Turing machine model was introduced by Hamkins and Lewis in 2000. This model generalises the Turing machine computation model to ordinal time. In this model, stages are indexed by (countable) ordinals, even though the tape is indexed by the integers as in the classical model. This model can thus now have infinite strings as input. The main focus of this thesis is the study of some of the new and surprising behaviours that these machines exhibit. Naturally, the longer, i.e., the greater ordinal, the computations run, the more powerful the model is, i.e. it computes/recognizes more sets. If the computations run beyond certain ordinal times, new structural properties also appear. One of these properties is the existence of gaps in the halting times of the machines. When these gaps had been discovered, some first links had been established between these gaps and the admissible character of the ordinals starting them. Our approach uses algorithmics as a mean to emphasize the links between the logical properties of the ordinals involved and the computational properties of the infinite time Turing machines. Moreover, thanks to some specific algorithms, we discover and prove new properties of these gaps, leading to a better understanding of their structure. We show in particular that gaps can have precisely every possible writable ordinal size and that there are gaps whose length is greater or equal than their starting ordinal point. Until the first of such a gap, the gaps appear in increasing sizes. We also show that even if, before this special gap, admissible ordinals only appear at the beginning of gaps, the gaps structure becomes quite disordered beyond that point, with admissible ordinals appearing not only at the beginning but also inside some (huge) gaps.

Les systèmes intégrables quantiques ont des propriétés mathématiques qui permettent la détermination exacte de leur spectre énergétique. A partir des équations de Bethe, je présente la relation de Baxter «T-Q». Celle-ci est à l'origine des deux approches que j'ai prioritairement employé dans mes recherches, les deux basés sur des équations intégrales non linéaires, celui de l'ansatz de Bethe thermo- dynamique et celui des équations de Klümper-Batchelor-Pearce-Destri-de Vega. Je montre le chemin qui permet de dériver les équations à partir de certain modèles sur réseau. J'évalue les limites infrarouge et ultraviolet et je discute l'approche numérique. D'autres constantes de mouvement peuvent être établies, ce qui permet un certain contrôle sur les vecteurs propres. Enfin, le modèle d'Hubbard, qui décrit des électrons interagissants sur un réseau, est présenté en relation à la théorie de jauge supersymétrique N = 4. Dans la deuxième partie, je présente un modèle d'évolution darwinienne basé sur les machines de Turing. En faisant évoluer une population d'algorithmes, je peut décrire certains aspects de l'évolution biologique, notamment la transformation entre parties codantes et non-codantes dans un génome ou la présence d'un seuil d'erreur. L'assemblage des protéines oligomériques est un aspect important qui intéresse la majorité des protéines dans une cellule. Le projet «Gemini» que j'ai contribué à créer a pour finalité d'explorer les donnés structuraux des interfaces des dites protéines pour différentier le rôle des acides aminés et déterminer la présence de patterns typiques de certaines géométries.

Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.