Thèse Problèmes de Satisfaction de Contraintes et Supersymétrie H/F - 74

Établissement : Ecole normale supérieure - PSL
École doctorale : Physique en Ile de France
Laboratoire de recherche : Laboratoire de physique statistique
Début de la thèse : 2026-08-25
Date limite de candidature : 2026-04-15T23:59:59

Les problèmes de satisfaction de contraintes (SAT) constituent un paradigme central de la théorie de l'information (1). Cette classe est vaste, mais un exemple typique est celui de la coloration de graphes, où l'on cherche à attribuer l'une des
q couleurs aux sommets d'un graphe de telle sorte que deux sommets reliés par une arête n'aient pas la même couleur.

Une autre famille de problèmes, d'un grand intérêt en information quantique, concerne les
t-designs sphériques et unitaires (2,3). Il s'agit ici de trouver un ensemble de
N éléments sur une sphère ou sur le groupe unitaire tel que toutes les fonctions polynomiales jusqu'au degré
t aient la même moyenne sur cet ensemble fini que sur l'espace continu correspondant. Ce problème peut être formulé comme un problème SAT en écrivant les conditions sur les moyennes dans une base d'états polynomiaux, ce qui conduit à un système d'équations non linéaires simultanées.

Les physiciens statisticiens ont contribué de manière décisive au domaine de la satisfiabilité en apportant des outils et une intuition issus de l'étude des systèmes désordonnés. Le lien est le suivant : on introduit une « énergie » (ou, dans le langage de la science des données, une fonction de perte) égale au nombre de contraintes violées. L'état fondamental du système peut ou non avoir une énergie nulle ; dans le premier cas, une solution SAT a été trouvée. Pour le problème des designs, l'énergie est simplement la somme des carrés des équations, de sorte qu'une énergie nulle signifie là encore que toutes les contraintes sont satisfaites. En réalité, pratiquement tous les problèmes SAT peuvent être formulés de cette manière, comme des systèmes d'équations devant être résolues simultanément (4).

Pour les systèmes d'équations, la physique théorique offre un outil bien plus spécifique que la simple optimisation d'une somme de carrés : la supersymétrie BRS (Becchi-Rouet-Stora), initialement développée dans le cadre des théories de jauge. Il s'agit d'une méthode relativement élémentaire, ne nécessitant pas un appareillage technique lourd, qui permet néanmoins de démontrer de manière simple des propriétés non triviales des solutions, telles que des résultats de type théorie de Morse ou des propriétés topologiques de l'ensemble des solutions (5). Le point crucial est que la symétrie du formalisme « se souvient », à chaque étape du calcul, du fait que le problème provient d'un système d'équations simultanées - une information qui est généralement perdue dans l'approche standard par Hamiltonien SAT. Une promesse essentielle de cette méthode est qu'elle permet d'aller au-delà des résultats à l'ordre dominant et d'obtenir des énoncés valables à tous les ordres dans la limite thermodynamique.

Récemment, en collaboration avec Misaki Osawa (6), nous avons mené une étude des
t-designs pour de grands
t et N, dans le cas de sphères et de groupes unitaires de faible dimension. Nous souhaitons désormais étendre ce travail en y intégrant la supersymétrie et en abordant le cas plus difficile et physiquement plus intéressant des designs en grande dimension pour des valeurs fixées de
t=2,3,.... Ce régime demeure largement inexploré du point de vue de la mécanique statistique, malgré l'intérêt considérable qu'il suscite.

Three apparently different subjects are very close:
1. constraint satisfaction (SAT) in data science
2. `canyon landscapes' in spin liquids, cellular tissues and striped phases
3. unitary and spherical t-designs, in quantum information.
In all cases there is a system with a manifold of ground states, whose properties we wish to study. In the field theory language, this is the `moduli space', for which supersymmetry techniques has been used.

Find solutions for t-designs. Introduce supersymmetry in the constraint satisfaction domain.

Analytical pen-and paper, some numerics to check ideas and to inspire solutions.