10:45
11:45

Séminaire d’Yvan Le Borgne

Partant de deux arbres binaires complets de hauteur d, certains ont proposé de les souder via une permutation alternant entre leurs feuilles. Un tel graphe peut-être présenté via une vue locale sous la forme d'un oracle renvoyant pour un sommet donné, la liste de ses voisins. Le premier problème est, étant donné l'identifiant d'une racine de l'arbre, de trouver l'identifiant de l'autre racine. En 2003, Childs, Cleve, Deotto, Farhi, Gutmann, Spielman ont obtenu à la fois une borne inférieure exponentielle sur le nombre d'appels à l'oracle pour tout algorithme classique ainsi qu'un algorithme quantique avec un nombre polynomial d'appels. En 2021, Aaronson a conjecturé qu'un avantage quantique pourrait exister pour le second problème consistant à trouver un chemin entre les deux racines ne connaissant qu'une des deux. J'évoquerai des résultats très récents sur ce sujet et aussi nos travaux avec Shrinidhi Teganahally Sridhara dans le prolongement de mon co-encadrement de son stage de M1 via ReLaX de cet été. Nous proposons des analyses de marches classiques pour ce second problème ainsi qu'un algorithme quantique toujours avec un nombre exponentiel d'appels à l'oracle mais atteignant la meilleure borne inférieure classique que nous connaissons.

Salle 76