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.

Nous nous ici intéressons à la propagation d'états non-classiques de la lumière à travers des milieux désordonnés, comme les couches de peinture ou les fibres multimodes. Ces milieux sont généralement considérés comme des obstacles à la propagation de la lumière: par exemple, la diffusion de la lumière dans les tissus biologiques diminue considérablement les capacités des systèmes d'imagerie optique. C'est donc un phénomène duquel on souhaite généralement s'affranchir. Au contraire, dans notre étude nous exploitons ce désordre et utilisons ces milieux comme des "mélangeurs" de lumière. La lumière qui y pénètre est fortement diffusée et ses propriétés spectrales, spatiales et de polarisation sont complètement redistribuées. Cette redistribution est associée à un phénomène de propagation d'onde et d'interférence complexe qui est donc déterministe. Nous pouvons alors utiliser des méthodes de manipulation de front d'onde pour étudier ou contrôler ce mélange. Associés à des états non-classiques, ces systèmes permettent de réaliser des marches aléatoires quantiques dans des environnements bien plus complexes que ceux qui existent actuellement. Les méthodes de contrôle de front d'onde nous ont permis d'étudier et de manipuler ces marches aléatoires. Nous avons notamment montré qu'il est possible de guider les photons en manipulant les interférences classiques et quantiques. Ce travail nous a permis d'étudier de nouveaux aspects de la physique des milieux complexes, mais aussi d'explorer un nouveau type de plateformes pour marches aléatoires quantiques qui pourraient jouer un rôle important dans le développement des nouvelles applications pour traitement de l'information. / Light is not only an ideal medium to transmit information, but also a very interesting physical system to process it. In this respect, quantum optics has recently emerged as a highly promising domain for the development of new computing applications that can surpass the performances of currently available systems. In this respect, quantum walk of photons has recently emerged as a very powerful model for quantum information science, and integrated photonic devices have proven a versatile architecture for their implementation. While these waveguide structures allow only near-neighbor coupling between up to a few tens of modes, complex linear systems, such as white paint layer or multimode fiber, enable to couple efficiently a huge numbers of optical modes. Unstable and lossy, these systems have always been considered unpractical for quantum optics experiments. Wavefront shaping methods, developed in the last decade to control light propagating in complex media, allow moving beyond these limitations and make them exploitable with non-classical light. In our work, we demonstrate the implementation of quantum walks in a layer of paint and a multimode fiber using single-photons and photon-pairs. For this purpose, we extend wavefront shaping methods, originally developed to control classical light propagation in complex media, to non-classical light. This capability to manipulate photons allows building new controllable highly multimode optical platforms. Such systems pave the way for the next generation of quantum information processing devices.

Soit G un groupe dénombrable, qui se scinde en un produit libre de la forme G=G_1*...*G_k*F, où F est un groupe libre de type fini, et les G_i sont librement indécomposables et non isomorphes à Z. Nous montrons que le groupe Out(G) des automorphismes extérieurs de G satisfait l'alternative de Tits, dès lors que chacun des groupes G_i et Out(G_i) la satisfait. Par des méthodes similaires, nous montrons aussi l'alternative suivante pour tout sous-groupe H de Out(F_N), due à Handel et Mosher lorsque H est de type fini : soit H fixe virtuellement la classe de conjugaison d'un facteur libre propre de F_N, soit H contient un automorphisme complètement irréductible. Nos méthodes, géométriques, utilisent l'étude de la dynamique de l'action de certains sous-groupes de Out(G) sur des espaces hyperboliques. Nous décrivons notamment l'adhérence de l'outre-espace de G relatif aux G_i, et le bord de Gromov du complexe (hyperbolique) des scindements cycliques relatifs associé. Nous étudions par ailleurs les marches aléatoires sur Out(F_N). Sous un certain nombre de conditions sur la mesure de probabilité mu, nous montrons que presque toute trajectoire de la marche aléatoire sur (Out(F_N),mu) converge vers un point du bord de Gromov du complexe des facteurs libres de F_N, que nous identifions au bord de Poisson de (Out(F_N),mu). Par ailleurs, nous décrivons l'horofrontière de l'outre-espace. Ceci a des applications à l'étude de la croissance des classes de conjugaison de F_N sous l'effet de produits aléatoires d'automorphismes extérieurs. / Let G be a countable group that splits as a free product of the form G=G_1*...*G_k*F, where F is a finitely generated free group, and the groups G_i are freely indecomposable and not isomorphic to Z. We show that Out(G) satisfies the Tits alternative, as soon as all the groups G_i and Out(G_i) do. Similar techniques also yield another alternative for subgroups H of Out(F_N), due to Handel and Mosher when H is finitely generated, namely: either H virtually fixes the conjugacy class of some proper free factor of F_N, or H contains a fully irreducible automorphism. Our methods are geometric, and require understanding the dynamics of the action of some subgroups of Out(G) on Gromov hyperbolic spaces. In particular, we determine the closure of the outer space of G relative to the G_i's, as well as the Gromov boundary of the (hyperbolic) complex of relative cyclic splittings of G. We also study random walks on Out(F_N). Given a probability measure mu on Out(F_N) (satisfying some conditions), we prove that almost every sample path of the random walk on (Out(F_N),mu) converges to a point of the Gromov boundary of the free factor complex of F_N, which we identify with the Poisson boundary of (Out(F_N),mu). We also describe the horoboundary of outer space, and give applications to growth of conjugacy classes of F_N under random products of outer automorphisms.

Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority. / This thesis is devoted to the study of stochastic decentralized processes. Typical examples in the real world include the dynamics of weather and temperature, of traffic, the way we meet our friends, etc. We take the rich tool set from probability theoryfor the analysis of Markov Chains and employ it to study a wide range of such distributed processes: Forest Fire Model (social networks), Balls-into-Bins with Deleting Bins, and fundamental consensus dynamics and protocols such as the Voter Model, 2-Choices, and 3-Majority.

Le modèle de dimères, également connu sous le nom de modèle de couplage parfait, est un modèle probabiliste introduit à l'origine dans la mécanique statistique. Une configuration de dimères d'un graphe est un sous-ensemble des arêtes tel que chaque sommet est incident à exactement une arête. Un poids est attribué à chaque arête et la probabilité d'une configuration est proportionnelle au produit des poids des arêtes présentes. Dans cette thèse, nous étudions principalement deux modèles qui sont liés au modèle de dimères, et plus particulièrement leur comportements limites. Le premier est le modèle des forêts couvrantes enracinées sur des cycles (CRSF) sur le tore, qui sont en bijection avec les configurations de dimères via la bijection de Temperley. Dans la limite quand la taille du tore tend vers l'infini, la mesure sur les CRSF converge vers une mesure de Gibbs ergodique sur le plan tout entier. Nous étudions la connectivité de l'objet limite, prouvons qu'elle est déterminée par le changement de hauteur moyen de la mesure de Gibbs ergodique et donnons un diagramme de phase. Le second est le modèle de perles, un processus ponctuel sur $\mathbb{Z}\times\mathbb{R}$ qui peut être considéré comme une limite à l'échelle du modèle de dimères sur un réseau hexagonal. Nous formulons et prouvons un principe variationnel similaire à celui du modèle dimère \cite{CKP01}, qui indique qu'à la limite de l'échelle, la fonction de hauteur normalisée d'une configuration de perles converge en probabilité vers une surface $h_0$ qui maximise une certaine fonctionnelle qui s'appelle "entropie". Nous prouvons également que la forme limite $h_0$ est une limite de l'échelle des formes limites de modèles de dimères. Il existe une correspondance entre configurations de perles et (skew) tableaux de Young standard, qui préserve la mesure uniforme sur les deux ensembles. Le principe variationnel du modèle de perles implique une forme limite d'un tableau de Young standard aléatoire. Ce résultat généralise celui de \cite{PR}. Nous dérivons également l'existence d'une courbe arctique d'un processus ponctuel discret qui encode les tableaux standard, defini dans \cite{Rom}. / The dimer model, also known as the perfect matching model, is a probabilistic model originally introduced in statistical mechanics. A dimer configuration of a graph is a subset of the edges such that every vertex is incident to exactly one edge of the subset. A weight is assigned to every edge, and the probability of a configuration is proportional to the product of the weights of the edges present. In this thesis we mainly study two related models and in particular their limiting behavior. The first one is the model of cycle-rooted-spanning-forests (CRSF) on tori, which is in bijection with toroidal dimer configurations via Temperley's bijection. This gives rise to a measure on CRSF. In the limit that the size of torus tends to infinity, the CRSF measure tends to an ergodic Gibbs measure on the whole plane. We study the connectivity property of the limiting object, prove that it is determined by the average height change of the limiting ergodic Gibbs measure and give a phase diagram. The second one is the bead model, a random point field on $\mathbb{Z}\times\mathbb{R}$ which can be viewed as a scaling limit of dimer model on a hexagon lattice. We formulate and prove a variational principle similar to that of the dimer model \cite{CKP01}, which states that in the scaling limit, the normalized height function of a uniformly chosen random bead configuration lies in an arbitrarily small neighborhood of a surface $h_0$ that maximizes some functional which we call as entropy. We also prove that the limit shape $h_0$ is a scaling limit of the limit shapes of a properly chosen sequence of dimer models. There is a map form bead configurations to standard tableaux of a (skew) Young diagram, and the map is measure preserving if both sides take uniform measures. The variational principle of the bead model yields the existence of the limit shape of a random standard Young tableau, which generalizes the result of \cite{PR}. We derive also the existence of an arctic curve of a discrete point process that encodes the standard tableaux, raised in \cite{Rom}.

Le présent travail se veut une contribution à l’extension du domaine des applications de la théorie des chemins rugueux à travers l’étude de la convergence des processus discrets, qui permet un nouveau regard sur plusieurs problèmes qui se posent dans le cadre du calcul stochastique classique. Nous étudions la convergence en topologie rugueuse, d’abord des chaînes de Markov sur graphes périodiques, ensuite des marches de Markov cachées, et ce changement de cadre permet d’apporter des informations supplémentaires sur la limite grâce à l’anomalie d’aire, invisible en topologie uniforme. Nous voulons montrer que l’utilité de cet objet dépasse le cadre des équations différentielles. Nous montrons également comment le cadre des chemins rugueux permet d’en- coder la manière dont on plonge un modèle discret dans l’espace des fonctions continues, et que les limites des différents plongements peuvent être différenciées précisément grâce à l’anomalie d’aire. Nous définissons ensuite les temps d’occupation itérés pour une chaîne de Markov et montrons, en utilisant les sommes itérées, qu’ils donnent une structure combinatoire aux marches de Markov cachées. Nous proposons une construction des chemins rugueux en passant par les sommes itérées et la comparons à la construction classique, faite par les intégrales itérées, pour trouver à la limite deux types de chemins rugueux différents, non-géométrique et géométrique respectivement. Pour finir, nous illustrons le calcul et la construction de l’anomalie d’aire et nous donnons quelques résultats supplémentaires sur la convergence des sommes et temps d’occupation itérés. / Through the present work, we hope to contribute to extending the domain of applications of rough paths theory by studying the convergence of discrete processes and thus allowing for a new point of view on several issues appearing in the setting of classical stochastic calculus. We study the convergence, first of Markov chains on periodic graphs, then of hidden Markov walks, in rough path topology, and we show that this change of setting allows to bring forward extra information on the limit using the area anomaly, which is invisible in the uniform topology. We want to show that the utility of this object goes beyond the setting of dierential equations. We also show how rough paths can be used to encode the way we embed a discrete process in the space of continuous functions, and that the limits of these embeddings dier precisely by the area anomaly term. We then define the iterated occupation times for a Markov chain and show using iterated sums that they form an underlying combinatorial structure for hidden Markov walks. We then construct rough paths using iterated sums and compare them to the classical construction, which uses iterated integrals, to get two dierent types of rough paths at the limit: the non-geometric and the geometric one respectively. Finally, we illustrate the computation and construction of the area anomaly and we give some extra results on the convergence of iterated sums and occupation times.

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D. / In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.

L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseau / The recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques

L’évolution de la reconstruction de surface de l’Au(111) sous contrainte-déformation a été étudiée dans le cadre d’une approche, à la fois expérimentale par microscopie à effet tunnel sous environnement ultra-vide couplée à un dispositif en compression, et numériquement par simulations en dynamique moléculaire. Dans un premier temps, nous avons étudié l’interaction entre les marches atomiques (vicinales ou traces de glissement) et la reconstruction. Nous avons notamment montré expérimentalement une forte dépendance de la longueur de la reconstruction avec la largeur des terrasses, en très bon accord avec les simulations atomistiques. Nous avons démontré de manière quantitative que ce comportement provenait de la relaxation des contraintes de surface, à la fois le long et perpendiculairement aux marches atomiques. Par la suite, nous avons montré que l’apparition d’une trace de glissement, résultant de l’émergence d’une dislocation à la surface, induit une réorganisation de la reconstruction, caractérisée par la formation d’un motif en forme de U. Nous avons par ailleurs observé expérimentalement la présence de décrochements le long de la trace. Les simulations ont confirmé que ces décrochements étaient corrélés avec la modification de la reconstruction. Dans un second temps, l’étude s’est axée sur l’évolution de la reconstruction en chevrons sous contrainte-déformation appliquée. Les observations expérimentales ont montré qu’une contrainte de compression macroscopique était à l’origine d’une modification de la structure en chevrons. Les simulations en dynamique moléculaire ont permis d’analyser l’influence de l’orientation de la contrainte sur les dislocations perçant la surface. Nous avons montré qu’une réorganisation irréversible de la structure en chevrons a lieu, se caractérisant par l’annihilation des dislocations perçant la surface et la suppression de la structure en chevrons. / The evolution of the surface reconstruction of the Au(111) under stress-strain has been studied in the context of an experimental approach, both by tunneling microscopy under ultra-vacuum environment coupled to a compression device, and numerically by molecular dynamics simulations. At first, we studied the interaction between atomic steps (vicinal or slip traces) and reconstruction. In particular, we showed experimentally a strong dependence of the length of the reconstruction with the width of the terraces, in very good agreement with the atomistic simulations. We have quantitatively demonstrated that this behavior is originated from the release of surface stress, both along and perpendicular to the atomic steps. Subsequently, we have shown that the appearance of a slip traces, resulting from the emergence of dislocations at the surface, induce a reorganization of the reconstruction, characterized by the formation of a U-shaped pattern. We also observed experimentally the presence of kinks along the trace. The simulations confirmed that these kinks are correlated with the modification of the reconstruction. At last, the study focused on the evolution of the chevron pattern under applied stress-strain. Experimental observations have shown that a macroscopic compressive strain involved a modification of the herringbone structure. Molecular dynamics simulations allowed to analyze the influence of stress orientation on surface threading dislocations. We have shown that an irreversible reorganisation of the herringbone structure takes place, characterized by the annihilation of the surface threading dislocations and the removal of the herringbone structure.

Nous nous penchons sur les fluctuations des marches dans plusieurs modèles de marches aléatoires en milieux aléatoires. En particulier, le résultat principal de ce mémoire est de prouver qu'il existe un théorème central limite trempé pour la marche aléatoire sur un arbre de Galton-Watson infini avec feuilles équipé de biais aléatoires plus grand que 1. Un tel théorème a été prouvé dans le cas où le biais est constant dans [1]; il s'agit donc de généraliser ce théorème. / We examine the fluctuations of walks in multiple models of random walks in random environments. In particular, the primary result of this dissertation is to prove there exists a quenched central limit theorem for the random on an infinite Galton-Watson tree with leaves equiped with random biases greater than 1. Such a theorem has already been proven in the case where the bias is constant in [1]; this is a generalization of that theorem.