Problèmes de Satisfaction de Contraintes Et Supersymétrie

**Problèmes de satisfaction de contraintes et supersymétrie // Constraint satisfaction problems and supersymmetry**:

- Réf **ABG-135339**
**ADUM-69113**
- Sujet de Thèse
- 30/01/2026
- Contrat doctoral
- Ecole normale supérieure - PSL
- Lieu de travail- Paris - Ile-de-France - France
- Intitulé du sujet- Problèmes de satisfaction de contraintes et supersymétrie // Constraint satisfaction problems and supersymmetry
- Champs scientifiques- Physique
- Mots clés- Informatique theorique, mecanique statistique, Theorie de champs, information quantique
Theoretical informatics, field theory, statistical mechanics, quantum information

**Description du sujet**:

- 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.

Constraint satisfaction (SAT) problems are a central paradigm in information theory (1). The class is vast, but typical example is 'graph coloring', in which
we are asked to assign one of q colors to the vertices of a graph in such a way that no vertices connected by a line have the same color.

Another family of problems, of great interest in quantum information, is the one of spherical and unitary 't-designs' (2,3): here we are asked to find a set of N elements on a sphere
or on the unitary group such that all polynomials up to degree t take the same average over these elements as they do over the full space. This problem may be stated as a SAT
problem just by writing the condition of averages on a basis of polynomials: a system of simultaneous nonlinear equations.

Statistical physicists have contributed to the field of satisfiability in a very decisive way, bringing in expertise on disordered systems. The connection is as follows: one writes an
'energy' (or 'loss function', in the language of data science) as the number of errors. The ground stat