Survol

Tenseurs : information quantique, complexité et combinatoires quantiques
14-25 novembre 2022

La compréhension structurelle et informatique des tenseurs est le moteur de l'accélération des algorithmes de multiplication matricielle dans la théorie de la complexité algébrique, de l'élucidation de l'intrication quantique dans la théorie de l'information quantique et de la percée dans le problème de l'ensemble plafond en combinatoire. Un problème central est le problème de conversion asymptotique pour les états quantiques enchevêtrés multipartites. Avec les intuitions de l'information quantique et de la complexité algébrique et les outils mathématiques de la théorie des représentations et de la recherche tensorielle, une ligne de recherche commune fructueuse a émergé. L'atelier réunira des experts dans ce domaine ainsi que d'autres sujets de la théorie de l'information quantique (réseaux tensoriels), de la complexité algébrique (P algébrique contre NP, théorie de la complexité géométrique), de la combinatoire (ensembles libres de progression arithmétique) et de la théorie des graphes (capacité de Shannon) qui sont liés à ces questions de recherche.

Le programme consiste en un atelier du 14 au 25 novembre 2022.

Le problème de la construction d'algorithmes rapides de multiplication matricielle est équivalent à la limitation supérieure du rang des tenseurs de la famille des tenseurs de multiplication matricielle. En 1969, Strassen a publié son célèbre algorithme permettant de multiplier des matrices n × n en utilisant seulement O(n^2,81) opérations arithmétiques, améliorant ainsi l'algorithme standard O(n³). Au fil des années, des constructions de plus en plus ingénieuses d'algorithmes de multiplication matricielle plus rapides, reposant sur des idées impliquant des sommes directes de tenseurs de multiplication matricielle, des fermetures d'orbite et des ensembles libres de progression arithmétique, conduisent à des limites supérieures de plus en plus élevées de l'exposant optimal ω. En même temps, une voie séparée de la théorie des représentations a été proposée sous le nom de méthode de la théorie des groupes par Cohn et Umans. La borne supérieure actuelle est ω ≤ 2,37286 obtenue en 2020 par Alman et Vassilevska W. et s'appuie sur les bornes précédentes de Vassilevska W., Le Gall et Stothers. La question de savoir si ω = 2 ou ω > 2 reste ouverte.

En 2016, la connexion entre la combinatoire extrémale et les tenseurs a été fermement établie avec la solution du problème de l'ensemble de cap par Ellenberg-Gijswijt et la preuve de tenseur par Tao en utilisant sa nouvelle notion de rang de tranche. Cette percée a suscité un intérêt particulier pour les paramètres des tenseurs liés au "subrank", par exemple le rang analytique de Gowers-Wolf. Le slice rank a également donné lieu à une riche série de travaux sur les barrières pour les algorithmes de multiplication matricielle obtenus via des tenseurs intermédiaires ou des versions de la méthode de la théorie des groupes, prolongeant les premières barrières d'Ambainis, Filmus et Le Gall.

Pour en revenir à Strassen, il a développé dans trois magnifiques articles entre 1987 et 1991 une théorie sophistiquée de la conception d'algorithmes de multiplication matricielle rapides et de la compréhension des relations asymptotiques entre les tenseurs. Son approche explique et relie entre eux de nombreux résultats dans ce domaine. Son idée essentielle était l'introduction d'une théorie générale de la dualité pour des conversions efficaces entre tenseurs ou autres objets, qui peut être considérée comme une vaste généralisation de la dualité de programmation linéaire ou un Positivstellensatz. L'objet dual, le spectre asymptotique des tenseurs, est constitué de paramètres tensoriels qui sont SLOCC-monotones, ⊗-multiplicatifs, ⊕-additifs et convenablement normalisés.

Une famille d'éléments dans le spectre asymptotique de tous les tenseurs complexes, les fonctionnelles quantiques, a été développée en 2018 par Christandl, Vrana et Zuiddam. Ces fonctionnelles sont définies comme des optimisations sur le polytope des moments, un objet contenant l'information asymptotique de la théorie des représentations d'un tenseur, reliant la multiplication matricielle, la théorie de l'information et la théorie des représentations. En parallèle, de grands progrès ont été réalisés récemment dans la compréhension algorithmique des polytopes de moments et des cônes nuls grâce au développement d'algorithmes de mise à l'échelle.

Nous espérons que l'approfondissement continu des connexions entre les points de vue physique, mathématique et informatique sur les tenseurs générera des orientations précieuses dans ces domaines de recherche.