Problèmes de satisfaction de contraintes et supersymétrie

Topic description Les problèmes de satisfaction de contraintes (SAT) constituent un paradigme central de la théorie de l'information . 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 . 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 . 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 , 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 . 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 state of the system may or may not have zero `energy', the latter case signals that a SAT solution has been found. For the `design' problem, the energy is simply the sum of the equations squared, so again a zero means that all have been satisfied. Indeed, essentially all SAT problems may be written in this way, as a set of equations that have to be simultaneously solved . For systems of equations, theoretical physics offers a tool that is much more specific than simply optimising a sum of squares: it is the so called BRS (Becchi Rouet Stora) supersymmetry, originally developed for gauge theories. This is a rather elementary method (it does not require a great expertise) that has allowed to prove in a simple way the properties of solutions, such as Morse theory and topological properties of the set of solutions . The crucial property is that the symmetry of the problem `remembers' at each stage of the calculation the fact that the problem originated from a simultaneous set of equations -- this is something that the usual approach of SAT hamiltonians loses track of. Right away, a promise of this method is that it will allow to obtain stronger results, extending leading order results to all orders in the thermodynamic limit. Recently, together with Misaki Osawa we have completed a work for t-designs at large t and N, for low dimensional spheres and unitaries. We wish to extend this, and incorporate supersymmetry, to the more interesting case of designs in large dimensions and t=2,3,... a subject of which not much is known from the statistical mechanics side, and which has elicited a large interest------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Début de la thèse : 25/08/ Funding category Public funding alone (i.e. government, region, European, international organization research grant) Funding further details Concours pour un contrat doctoral*