“Dans notre cas, deux nœuds constituants du réseau sont reliés par une arête s'ils peuvent communiquer l'un avec l'autre. Ayant l'intuition que pour ce problème toute amélioration des algorithmes classiques pourrait servir à élaborer des algorithmes quantiques encore plus efficaces, nous avons traité le problème de la détection des cycles de longueur fixe dans ces graphes-réseaux.” Maël Luce, ancien doctorant à l'IRIF.

Lien de sa thèse : Distributed Randomized and Quantum Algorithms for Cycle Detection in Networks

Originaire des Yvelines, je suis passé par une classe préparatoire Maths-Physique avant d'intégrer l'école d'ingénieur Télécom Paris. J'ai ensuite bénéficié d'une passerelle pour faire du MPRI mon M2. C'est durant cette année-là que j'ai découvert les calculs distribué et quantique. Pierre Fraigniaud, mon professeur de distribué, m'a ensuite pris en stage à l'IRIF avec Frédéric Magniez, chercheur en quantique. Ce stage s'est alors poursuivi en thèse sous la direction de Pierre et de Ioan Todinca.

Durant l'école d'ingénieur, j'ai fini par me rendre compte que mes cours orientés ingénierie et applications ne m'intéressaient pas tant que ça. Au même moment, je découvrais avec émerveillement l'informatique théorique. J'ai donc suivi le cursus qui me permettrait de continuer à en faire: le MPRI puis la recherche.

Petit graphe quelconque contenant un cycle de longueur 4

Le distribué est le domaine de la modélisation des réseaux de communication. Pour ce faire, on utilise les graphes: objet mathématique très générique représentant des nœuds reliés par des arêtes (pensez par exemple à une carte de métro où les nœuds sont des stations reliées par des tronçons de ligne, ou au graphe des relations sur votre réseau social préféré). Dans notre cas, deux nœuds constituants du réseau sont reliés par une arête s'ils peuvent communiquer l'un avec l'autre. Ayant l'intuition que pour ce problème toute amélioration des algorithmes classiques pourrait servir à élaborer des algorithmes quantiques encore plus efficaces, nous avons traité le problème de la détection des cycles de longueur fixe dans ces graphes-réseaux.

L'hypothèse d'une bande passante est réaliste

Un problème local est un problème de calcul distribué dans lequel la réponse de chaque nœud ne dépend que de son voisinage à petite distance. C'est le cas pour la détection de cycle: imaginons que je sois un nœud du réseau, pour savoir si je fais partie d'un cycle de longueur donnée, je n'ai besoin de connaître la structure du graphe qu'à une distance égale à la moitié de cette longueur donnée. En effet, si je fais partie d'un cycle de longueur 4, je trouverai deux chemins distincts de longueur 2 me reliant au nœud à mon opposé dans le cycle.

En supposant que les nœuds peuvent communiquer à leurs voisins n'importe quelle quantité d'information en un temps donné, les problèmes locaux sont triviaux. Il n'y a besoin que de 2 étapes de communication pour que, en tant que nœud, je puisse détecter mes cycles de longueur 4 : d'abord les voisins de mes voisins se manifestent auprès de mes voisins, puis mes voisins m'envoient toute cette information.

Imposons maintenant une bande passante qui limite la quantité d'information échangée entre deux nœuds durant une étape de communication, hypothèse réaliste. Le problème de détection de sous-structures devient bien plus intéressant. Un de mes voisins ne peut plus m'envoyer toute l'information de ses propres voisins en une étape, si ces derniers sont trop nombreux.

L'hypothèse de la bande passante permet de discriminer les problèmes locaux qui sont tous triviaux sans celle-là. Par exemple, certaines structures très simples restent triviales à détecter avec une bande passante tandis qu'il en existe d'autres plus complexes qu'on ne peut détecter qu'avec énormément d'étapes de communication. Le cycle est la structure la plus simple pour laquelle la question n'est pas encore résolue.

Je l'ai créé moi-même mais il est directement inspiré des travaux qui m'ont précédé sur ce problème et je n'aurais pas pu avoir une seule de mes idées sans l'aide de mes directeurs et co-auteurs, Ioan et Pierre, et de mon co-auteur Frédéric.

Cet algorithme résout la détection de cycle de longueur paire en un nombre d'étapes de communication minimal à ce jour. Il généralise une performance qui avait déjà été atteinte pour les cycles pairs de plus petites longueurs. J'ai commencé ma thèse en cherchant à étendre la preuve de l'algorithme déjà existant à toutes les longueurs paires. Nous avons fini par prouver que cet algorithme ne marchait en fait que pour les longueurs déjà prouvées, car il existe une famille de graphes dans lesquels il ne marche pas. C'est en réfléchissant aux modifications à apporter pour le faire marcher dans nos graphes contre-exemples que m'est venue l'idée de mon propre algorithme.

De la même manière, l'accélération quantique de notre algorithme classique s'inspire des quantizations ayant déjà été trouvées dans le modèle sur lequel nous travaillons.

C'est dans les cours de distribué et de quantique que je me sentais le plus à l'aise et le plus stimulé durant mon M2. Sophie Laplante, ma professeure de quantique, m'a alors informé de l'existence du calcul quantique distribué, jeune domaine en plein essor.

Étudier ce modèle avec bande passante renforce notre compréhension de domaines très théoriques et omniprésents dans la technologie moderne (théorie des graphes, complexité de la communication, …) et les met même en relation grâce à beaucoup de résultats sous la forme “d'après ce théorème sur les graphes, il suffit que les nœuds communiquent tant de bits pour résoudre ce problème”.

En outre, vers une application plus directe, s'assurer de l'absence de certaines structures dans un réseau peut parfois permettre d'appliquer des algorithmes qui ne marcheraient pas sinon.

Je pars pour un an de post-doctorat au Japon, je ne me pose pas encore la question pour la suite.