Thèse Calcul Distribué Quantique H/F

École polytechnique

Établissement : École polytechnique
École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris
Laboratoire de recherche : LIX - Laboratoire d'informatique
Direction de la thèse : Marc-Olivier RENOU ORCID 0000000243582384
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-04-01T23:59:59

La théorie de l'information quantique offre un potentiel prometteur, mais encore largement inexploré, pour améliorer le calcul distribué. Ce projet de thèse porte sur des questions fondamentales concernant les avantages que pourraient apporter les stratégies quantiques aux algorithmes distribués, en particulier leur capacité à fournir des solutions plus rapides ou une meilleure résilience que les approches classiques. En explorant ces problèmes ouverts, le projet vise à préciser les véritables capacités et limites des méthodes quantiques en calcul distribué.

De nombreux scénarios de base dans lesquels les qubits pourraient permettre des algorithmes distribués plus efficaces demeurent mal compris. Un exemple central est le problème du coloriage approprié d'un anneau de N processeurs dans un modèle synchrone. Les algorithmes classiques nécessitent un temps qui croît avec N, tandis que l'existence d'une solution quantique en temps constant reste une question ouverte (arXiv:2403.01903, 2307.09444).

Le projet étudiera les limites de la théorie de l'information quantique dans le contexte du calcul distribué, avec un accent particulier sur l'établissement ou non d'avantages quantiques pour de tels problèmes fondamentaux.

L'objectif général est d'identifier les situations dans lesquelles les qubits permettent des algorithmes plus rapides, plus robustes aux défaillances, ou nécessitant moins d'étapes de communication - une direction de recherche récente et très dynamique (arXiv:1810.10838, 1908.11488, 2307.09444, 2403.01903, 2409.01707, 2411.03240). Le projet sera adapté aux objectifs et intérêts du ou de la doctorant·e.

La thèse pourra être réalisée en cotutelle ou en collaboration étroite avec l'un de mes cinq collaborateurs mentionnés ci-dessus. Elle pourra être basée soit dans l'une de leurs institutions, soit à Saclay, selon le choix de l'étudiant·e. De longs séjours réguliers dans les autres instituts seront encouragés.

In recent years, the intersection between distributed computing and quantum information theory has emerged as a promising yet largely undeveloped research frontier. While quantum technologies have shown clear advantages in areas such as cryptography and communication complexity, their potential impact on distributed algorithms remains poorly understood. Classical distributed computing is constrained by locality, communication limits, and fault tolerance barriers; whether quantum resources-entanglement, quantum communication, or quantum measurements-can bypass these limitations is still an open question. A few pioneering works have revealed potential quantum speedups or structural advantages, but no general framework exists yet. This makes the field both scientifically compelling and conceptually foundational, offering the opportunity to uncover genuinely new algorithmic paradigms driven by quantum mechanics.