PMI ^* =RE n'est pas une faute de frappe. C'est une découverte révolutionnaire et le titre accrocheur d'un article récent dans le domaine de la théorie de la complexité quantique. La théorie de la complexité est un zoo de « classes de complexité » – des collections de problèmes informatiques – dont MIP ^* et RE ne sont que deux.

L'article de 165 pages montre que ces deux classes sont les mêmes. Cela peut sembler un détail insignifiant dans une théorie abstraite sans aucune application dans le monde réel. Mais physiciens et mathématiciens affluent pour visiter le zoo, même s'ils ne comprennent probablement pas tout. Car il s'avère que la découverte a des conséquences étonnantes pour leurs propres disciplines.

En 1936, Alan Turing a montré que le problème de l'arrêt - décider de manière algorithmique si un programme informatique s'arrête ou boucle pour toujours - ne peut pas être résolu. L'informatique moderne est née. Son succès donnait l'impression que bientôt tous les problèmes pratiques allaient céder la place à l'immense puissance de l'ordinateur.

Mais il est vite devenu évident que, alors que certains problèmes peuvent être résolus algorithmiquement, le calcul réel durera longtemps après que notre Soleil aura englouti l'ordinateur effectuant le calcul. Trouver comment résoudre un problème de manière algorithmique ne suffisait pas. Il était essentiel de classer les solutions par efficacité. La théorie de la complexité classe les problèmes en fonction de la difficulté à les résoudre. La dureté d'un problème se mesure en fonction de la durée du calcul.

RE signifie problèmes qui peuvent être résolus par un ordinateur. C'est le zoo. Regardons quelques sous-classes.

La classe P est constituée de problèmes qu'un algorithme connu peut résoudre rapidement (techniquement, en temps polynomial). Par exemple, multiplier deux nombres appartient à P car la multiplication longue est un algorithme efficace pour résoudre le problème. Le problème de trouver les facteurs premiers d'un nombre n'est pas connu pour être dans P; le problème peut certainement être résolu par un ordinateur mais aucun algorithme connu ne peut le faire efficacement. Un problème connexe, décider si un nombre donné est un nombre premier, était dans des limbes similaires jusqu'en 2004, lorsqu'un algorithme efficace a montré que ce problème est dans P.

Une autre classe de complexité est NP. Imaginez un labyrinthe. « Y a-t-il un moyen de sortir de ce labyrinthe ? est une question oui/non. Si la réponse est oui, alors il y a un moyen simple de nous convaincre :il suffit de nous donner les indications, nous les suivrons, et nous trouverons la sortie. Si la réponse est non, cependant, il faudrait parcourir tout le labyrinthe sans jamais trouver d'issue pour être convaincu.

De tels problèmes oui/non pour lesquels, si la réponse est oui, nous pouvons démontrer efficacement que, appartiennent à NP. Toute solution à un problème sert à nous convaincre de la réponse, et donc P est contenu dans NP. Étonnamment, une question à un million de dollars est de savoir si P =NP. Personne ne sait.

Faire confiance aux machines

Les classes décrites jusqu'à présent représentent les problèmes rencontrés par un ordinateur normal. Mais les ordinateurs changent fondamentalement :les ordinateurs quantiques sont en cours de développement. Mais si un nouveau type d'ordinateur arrive et prétend résoudre l'un de nos problèmes, comment pouvons-nous croire qu'il est correct?

Imaginez une interaction entre deux entités, un interrogateur et un prouveur. Lors d'un interrogatoire de police, le prouveur peut être un suspect tentant de prouver son innocence. L'interrogateur doit décider si le prouveur est suffisamment convaincant. Il y a un déséquilibre; du point de vue des connaissances, l'interrogateur est dans une position inférieure.

En théorie de la complexité, l'interrogateur est la personne, avec une puissance de calcul limitée, essayer de résoudre le problème. Le prouveur est le nouvel ordinateur, qui est supposé avoir une immense puissance de calcul. Un système de preuve interactif est un protocole que l'interrogateur peut utiliser pour déterminer, au moins avec une forte probabilité, si le prouveur doit être cru. Par analogie, ce sont des crimes que la police peut ne pas être en mesure de résoudre, mais au moins des innocents peuvent convaincre la police de leur innocence. C'est l'IP de classe.

Si plusieurs prouveurs peuvent être interrogés, et les démonstrateurs ne sont pas autorisés à coordonner leurs réponses (comme c'est généralement le cas lorsque la police interroge plusieurs suspects), puis nous arrivons à la classe MIP. De tels interrogatoires, en recoupant les réponses des prouveurs, fournir à l'interrogateur une plus grande puissance, donc MIP contient IP.

La communication quantique est une nouvelle forme de communication réalisée avec des qubits. Enchevêtrement - une caractéristique quantique dans laquelle les qubits sont étrangement enchevêtrés, même si elle est séparée, rend la communication quantique fondamentalement différente de la communication ordinaire. Permettre aux prouveurs de MIP de partager un qubit intriqué conduit à la classe MIP ^*.

Il semble évident que la communication entre les prouveurs ne peuvent servir qu'à aider les prouveurs à coordonner les mensonges plutôt qu'à aider l'interrogateur à découvrir la vérité. Pour cette raison, personne ne s'attendait à ce que permettre plus de communication rende les problèmes de calcul plus fiables et résolvables. Étonnamment, nous savons maintenant que MIP ^* =RE. Cela signifie que la communication quantique se comporte très différemment de la communication normale.

Des implications de grande envergure

Dans les années 1970, Alain Connes a formulé ce qui est devenu connu sous le nom de Connes Embedding Problem. Grossièrement simplifié, cela a demandé si les matrices infinies peuvent être approchées par des matrices finies. Ce nouvel article a maintenant prouvé que ce n'est pas possible, une découverte importante pour les mathématiciens purs.

En 1993, pendant ce temps, Boris Tsirelson a identifié un problème de physique maintenant connu sous le nom de problème de Tsirelson. Il s'agissait de deux formalismes mathématiques différents d'une même situation en mécanique quantique – à ce jour une théorie incroyablement réussie qui explique le monde subatomique. Étant deux descriptions différentes du même phénomène, il fallait s'attendre à ce que les deux formalismes soient mathématiquement équivalents.

Mais le nouveau document montre maintenant qu'ils ne le sont pas. On ne sait pas exactement comment ils peuvent tous les deux donner les mêmes résultats et décrire la même réalité physique, mais c'est pourquoi les physiciens s'y intéressent aussi tout à coup.

Le temps nous dira quelles autres questions scientifiques sans réponse donneront à l'étude de la complexité. Indubitablement, PMI ^* =RE est un grand pas en avant.

Cet article est republié à partir de The Conversation sous une licence Creative Commons. Lire l'article original.