Thèse Réécriture de Graphes Quantique H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : Laboratoire Méthodes Formelles Direction de la thèse : Pablo ARRIGHI ORCID 0000000235351009 Début de la thèse : 2026-10-01 Date limite de candidature : 2027-10-28T23:59:59 La théorie de la réécriture modélise le calcul par l'application de règles locales, effectuées sur des termes, ou des graphes. Elle est intrinsèquement asynchrone : les règles peuvent être appliquées dans des ordres arbitraires, mais elles aboutiront néanmoins au même résultat pour peu que le système soit 'confluent'.

En informatique quantique, en revanche, les lois de la physique imposent que l'évolution globale, celle qui envoie l'état à l'instant t sur l'état à l'instant t+1, soit unitaire.

Les deux cadres semblent incompatibles : la réécriture est intrinsèquement non-déterministe, tandis que les évolutions quantiques sont elles déterministes et même réversibles.

L'objectif de ce projet est de développer un formalisme de réécriture quantique de graphes qui parvienne à réconcilier ces deux points de vue. Dans ce formalisme, nous agirons de façon asynchrone, à coups de règles locales quantiques, sur des superpositions quantiques de graphes---mais des propriétés de type confluence nous permettrons de garantir que l'évolution globale entre deux « snapshots » quelconques reste bien unitaire.

D'un point de vue informatique, ce projet contribuera à transposer certaines notions fondamentales de l'informatique théorique, vers le domaine de l'informatique quantique, et à établir un premier modèle rigoureux et entièrement quantique de calcul distribué. D'un point de vue Physique, le projet pourrait contribuer aux approches de la gravité quantique où la géométrie de l'espace est également modélisée par une superposition quantique de graphes, mais où l'unitarité et la simulabilité restent des questions ouvertes. In [1] we introduced space-time deterministic graph rewriting, a strengthening of confluence adapted to non-terminating, distributed computation. There, different orders of local rewrites are required to produce the same causal structure of events---its space-time. This space-time determinism captures the physicist's notion of covariance in computational form: independence of the outcome from the chosen evaluation order plays the same conceptual role as coordinate invariance in relativity. In [2] we worked out the reversible case.

In parallel, we developed Quantum Causal Graph Dynamics [3]: unitary and causal operators acting on quantum superpositions of graphs. This model enforces unitarity and locality but remains synchronous. The challenge is to merge it with [1, 2].

The resulting space-time deterministic quantum graph rewriting would make explicit when a state-based quantum description (as required by unitarity) is compatible with a space-time description (as required by covariance/background-invariance). It would thus delineate the precise interface between quantum computation and discrete space-time models. We will seek to reconcile the rewriting paradigm, dear to computer scientists, with the unitarity imposed by quantum mechanics. We will formulate these results in terms of strong confluence properties in the context of quantum graphs rewriting.

Étudiant en informatique théorique fortement intéressé par l'informatique quantique, la théorie de la réécriture (lambda calcul), les systèmes dynamiques (automates cellulaires...). Probablement issu d'un master tel que MPRI, QMI, QDCS, QI ou similaire.
Étudiant en physique théorique ou en mathématiques ayant suivi des cours sur l'information quantique, et qui soit fortement intéressé par l'informatique théorique, la physique mathématique, la gravité quantique.