Nous avons étudié les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Après avoir construit quelques algorithmes, nous nous sommes interessés aux équivalents quantiques des marches aléatoires. Ces marches peuvent être à la base de nouveaux algorithmes quantiques. Nous avons commencé par généraliser le modèle existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons étudié des marches sur l'hypercube et le réseau simple à une et deux directions. Pour ces graphes nous avons calculé analytiquement la fonction d'onde et exploré numériquement le temps d'arrivée et la variance. Nous avons de plus élargi deux théorèmes existants concernant l'existence des marches scalaires et la limite faible. Ces résultats nous permettent d'envisager de compléter la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.

Un des objectifs majeurs de cette thèse est la construction d'un formalisme algébrique englobant la notion de graphe orienté pondéré et celle de cogèbre coassociative. On montre la nécessité de travailler avec des cogèbres équipées de deux coproduits ou co-opérations. Ce faisant on retrouve la notion de digèbre associative introduite dix ans plus tôt par Jean-Louis Loday, notion motivée par la K-théorie, proposant ainsi un point de vue complémentaire à son formalisme. Le développement du formalisme algébrique introduit dans cette thèse propose aussi une extension de la notion de graphe orienté ainsi que l'utilisation de cogèbres équipées de plusieurs coproduits. La construction de graphes orientés sur des objets algébriques tels que les produits. La construction de graphes orientés sur des objets algébriques tels que les algèbres, bigèbres ou algèbres de Hopf motive ainsi la construction naturelle d'autres types d'algèbres tels que les trigèbres associatives, trigèbres cubiques, algèbres dendriformes, algèbres diptères et algèbres pré-dendriformes introduites par Jean-Louis Loday et Maria Ronco et re-découvertes par l'auteur. La construction de pavages ou de recouvrements coassociatifs de graphes orientés par des cogèbres coassociatives ou cogèbres codiptères permet la construction d'objets algèbriques plus généraux qu'on appelle variétés coassociatives. D'autres objectifs développés dans cette thèse sont liés à l'utilisation de grammaires coassociatives ou au formalisme de Quillen appliqué aux dérivées de type Leibniz-Ito, outils apparaissant en calculs stochastiques classique et quantique et reliés de très près au formalisme proposé par l'auteur.

Un ordinateur quantique (OQ), i.e. utilisant les ressources de la physique Q, superposition et intrication, pourrait fournir un gain exponentiel de temps de calcul. Une simulation utilisant ces ressources est appelée simulation Q (SQ). L’avantage des SQs sur les simulations classiques est bien établi au niveau théorique, i.e. software. Leur avantage pratique requiert un hardware Q. L’OQ, sous-entendu universel (cf. plus bas), n’a pas encore vu le jour, mais les efforts en ce sens sont croissants et variés. Aussi la SQ a-t-elle déjà été illustrée par de nombreuses expériences de principe, grâce à des calculateurs ou simulateurs Qs de taille réduite. Les marches Qs (MQs) sont des schémas de SQ particulièrement étudiés, étant des briques élémentaires pour concevoir n’importe quel algorithme Q, i.e. pour le calcul Q universel. La présente thèse est un pas de plus vers une simulation des théories Qs des champs basée sur les MQs à temps discret (MQTD). En effet, il est montré, dans certains cas, comment les MQTD peuvent simuler, au continu, l'action d'un champ de jauge Yang-Mills sur de la matière fermionique, et la rétroaction de cette-dernière sur la dynamique du champ de jauge. Les schémas proposés préservent l’invariance de jauge au niveau de la grille d’espace-temps, i.e. pas seulement au continu. Il est proposé (i) des équations de Maxwell sur grille, compatibles avec la conservation du courant sur la grille, et (ii) une courbure non-abélienne définie sur la grille. De plus, il est montré comment cette matière fermionique à base de MQTD peut être couplée à des champs gravitationnels relativistes du continu, i.e. des espaces-temps courbes, en dimension 1+2. / A quantum (Q) computer (QC), i.e. utilizing the resources of Q physics, superposition of states and entanglement, could fournish an exponential gain in computing time. A simulation using such resources is called a Q simulation (QS). The advantage of QSs over classical ones is well established at the theoretical, i.e. software level. Their practical benefit requires their implementation on a Q hardware. The QC, i.e. the universal one (see below), has not seen the light of day yet, but the efforts in this direction are both growing and diverse. Also, QS has already been illustrated by numerous experimental proofs of principle, thanks too small-size and specific-task Q computers or simulators. Q walks (QWs) are particularly-studied QS schemes, being elementary bricks to conceive any Q algorithm, i.e. to achieve so-called universal Q computation. The present thesis is a step more towards a simulation of Q field theories based on discrete-time QWs (DTQWs). Indeed, it is shown, in certain cases, how DTQWs can simulate, in the continuum, the action of Yang-Mills gauge fields on fermionic matter, and the retroaction of the latter on the gauge-field dynamics. The suggested schemes preserve gauge invariance on the spacetime lattice, i.e. not only in the continuum. In the (1+2)D Abelian case, consistent lattice equivalents to both Maxwell’s equations and the current conservation are suggested. In the (1+1)D non-Abelian case, a lattice version of the non-Abelian field strength is suggested. Moreover, it is shown how this fermionic matter based on DTQWs can be coupled to relativistic gravitational fields of the continuum, i.e. to curved spacetimes, in several spatial dimensions.

Les simulateurs quantiques, qui utilisent un système quantique contrôlable pour étudier le comportement et les propriétés d'un autre système quantique, moins accessible, sont une ressource prometteuse. Dans les dernières années, des progrès significatifs ont été faits dans de nombreux domaines expérimentaux et théoriques. Les marches quantiques à temps discret sont des systèmes simples et sophistiqués. En particulier, il a été montré qu'à la limite continue, ces marches peuvent simuler certaines théories de champs. Dans ce travail de thèse, lesdites marches sont utilisées pour explorer certains sujets d'intérêt physique, qui s'articulent autour de trois axes : (i) la connexion entre les propriétés géométriques de la marche et celles de divers champs de jauge ; (ii) la limite classique et la limite quasi-quantique, en relation surtout avec les théories de champs ; (iii) l'équilibration spontanée pour certains modèles non linéaires de marches quantiques. Chaque résultat est appuyé par une étude numérique et analytique. / Problems too demanding for classical computers can be approached promisingly with quantum simulators, which operate using one controllable quantum system in order to investigate the behavior and properties of a less accessible one. Over the past few years, significant progress has been made in a number of experimental and theoretical fields. Quantum Walks (QWs) are simple and sophisticated discrete space and time dynamical systems and it has been shown that in the continuous limit different emergent quantum fields can be simulated. In this thesis we will draw on QWs to further explore various areas of interest in Physics. More specifically our analysis will branch out into three main directions: (i) the connection between QWs and quantum field theory, with particular attention to bridging the quantum coin of QWs with the geometrical properties of gauge field theories; (ii) the study of QWs' classical limit and of the transient semi-classical dynamics, especially in relation with field theories; (iii) the spontaneous equilibration and thermalization in some nonlinear QWs-like models. Every step of this thesis will be validated by specific analytical results and numerical implementations.