Soutenance de thèse de ROGET Mathieu
Titre de thèse
recherche par marche quantique : des grilles aux réseaux
quantum walk search: from grids to networks
Résumé de la thèse
L'informatique quantique est un nouveau domaine de l'informatique qui met à profit les propriétés quantiques des objets à petite échelle pour résoudre des tâches algorithmiques. Cependant, le manque d'intuition sur l'informatique quantique complique l'élaboration d'algorithmes quantiques efficaces. Dans ce contexte, cette thèse se concentre sur les marches quantiques : la version quantique des marches aléatoires. On considère ici un problème déjà bien étudié pour les marches aléatoires : la recherche d'éléments. En effet, il est déjà prouvé dans la littérature qu'une marche quantique sur une grille peut trouver une position marquée en temps $O(sqrt{n}text{ poly-log }n)$. Une première contribution de cette thèse est de montrer que, lorsque deux positions sont marquées, le même algorithme en trouve une avec une complexité moyenne de $O(sqrt{n}text{ poly-log }n)$ mais une complexité au pire cas de $O(ntext{ poly-log }n)$. Une seconde contribution de cette thèse est d'étendre le modèle des marches quantiques sur des graphes arbitraires. Le modèle proposé a la notable nouveauté d'être localisé sur les arrêtes au lieu des nœuds, celles-ci étant munis d'une polarité. Enfin, une troisième contribution introduit un modèle de calcul quantique distribué. De plus, nous montrons comment une marche quantique sur un graphe peut voir sa dynamique être reproduite sur ce même graphe dans un contexte distribué via le modèle proposé.
Thesis resume
Quantum computing is a new field of computer science that leverage the quantum properties of atomic and subatomic particles for solving computational tasks. However, quantum computing provides very little intuition on how it works. This makes the identification of computational tasks with a potential quantum speedup and the elaboration of quantum algorithms for said tasks very difficult. In this context, this thesis focuses on a quantum dynamical system called Discrete Time Quantum Walk (DTQW). DTQWs are dynamical systems with discrete time and space which are inspired from random walks. This thesis focuses on the problem of searching an element in an unstructured database. It is known in the literature that searching an element with a DTQW on a grid has a quasi-square-root (i.e. $O(sqrt{n}text{ poly-log }n)$) complexity in the dataset size $n$. This provides a significant quantum speedup over the linear complexity of classical brute-force or random walk based algorithms. A first contribution of this thesis shows that, when two elements are searched, the worst case complexity becomes quasi-linear while the average case complexity remains quasi-square-root. Moving on from grids to arbitrary topologies, a second contribution introduces a new model of DTQW onto the edges of an arbitrary graph. This model unique features are: (i) the position which is on the edges; (ii) a polarity on each edge that generalizes the notion of right and left we have on a line. A third contribution introduces a model of quantum distributed computing and shows how this model on an arbitrary graph can reproduce the dynamic of a DTQW on the same graph.