Il y a une célèbre parabole sur un groupe d'aveugles rencontrant un éléphant pour la toute première fois. Le premier aveugle, qui avait la main du côté de l'éléphant, a dit que c'était comme un énorme mur. Le deuxième aveugle, enroulant ses bras autour de la jambe de l'éléphant, s'est exclamé que c'était sûrement un gigantesque tronc d'arbre. Le troisième, sentant la queue de l'éléphant, déclara que ce devait être une corde épaisse. Un désaccord véhément s'ensuit, mais après un certain temps, les aveugles finissent par se rendre compte que, alors que chaque personne avait partiellement raison, l'éléphant a bien plus à faire que ce que l'on pensait initialement.

Le mois dernier, Zhengfeng, Anand, Thomas, John et moi avons publié MIP * = RE à arXiv. Le papier ressemble beaucoup à l'éléphant de la fable - et pas seulement à cause du nombre de pages! Pour un informaticien, le papier est ostensiblement sur la complexité des preuves interactives. Pour un physicien quantique, il s'agit de modèles mathématiques de l'intrication quantique. Pour le mathématicien, il existe une résolution revendiquée à un problème de longue date dans les algèbres d'opérateurs. Comme les aveugles de la parabole, chacun ressent une petite part d'un phénomène nouveau. Comment le mur, le tronc d'arbre et la corde s'assemblent-ils tous ensemble?

J'essaierai de tracer les contours de l'éléphant: il commence par un mystère dans la théorie de la complexité quantique, courbe à travers les fondements mathématiques de la mécanique quantique, et arrive à une question profonde sur les algèbres d'opérateurs.

En 2004, les informaticiens Cleve, Hoyer, Toner et Watrous pensaient à propos d'une chose amusante appelée jeux non locaux. Un jeu non local implique trois parties: deux joueurs coopérants nommés Alice et Bob, et quelqu'un appelé le vérificateur. Le vérificateur échantillonne une paire de questions aléatoires et envoie à Alice (qui répond avec réponse ), Et à Bob (qui répond avec réponse ). Le vérificateur utilise alors une fonction qui lui indique si les joueurs gagnent, en fonction de leurs questions et réponses.

Les trois parties connaissent les règles du jeu avant qu'il ne commence, et l'objectif d'Alice et Bob est de maximisent leur probabilité de gagner le match. Les joueurs ne sont pas autorisés à communiquer entre eux pendant le jeu, c'est donc une tâche non triviale pour eux de coordonner une stratégie optimale (c'est-à-dire, comment ils devraient répondre individuellement aux questions du vérificateur) avant le début du jeu.

L'exemple le plus célèbre d'un jeu non local est le jeu CHSH (qui a déjà fait plusieurs apparitions sur ce blog): dans ce jeu, le vérificateur envoie un bit uniformément aléatoire à Alice (qui répond un peu ) et un bit uniformément aléatoire à Bob (qui répond un peu ). Les joueurs gagnent si (en d'autres termes, la somme de leurs bits de réponse est égale au produit des bits d'entrée modulo ).

Quelle est la probabilité de gain maximale d'Alice et de Bob? Eh bien, cela dépend du type de stratégie qu'ils utilisent. S'ils utilisent une stratégie qui peut être modélisée par classique physique, alors leur probabilité de gagner ne peut pas dépasser (nous appelons cela le valeur classique de CHSH). D'un autre côté, s'ils utilisent une stratégie basée sur quantum physique, Alice et Bob peuvent faire mieux en partageant deux bits quantiques (qubits) qui sont enchevêtré. Pendant le jeu, chaque joueur mesure son propre qubit (où la mesure dépend de sa question reçue) pour obtenir des réponses qui gagnent le jeu CHSH avec probabilité (nous appelons cela le valeur quantique de CHSH). Donc, même si les qubits intriqués ne permettent pas à Alice et Bob de communiquer entre eux, l'intrication leur donne un moyen de gagner avec une probabilité plus élevée! En termes techniques, leurs réponses sont plus corrélé que ce qui est possible classiquement.

Le jeu CHSH vient de la physique et a été initialement formulé non pas comme un jeu impliquant Alice et Bob, mais plutôt comme une expérience impliquant deux appareils séparés dans l'espace pour tester si des corrélations plus fortes que les classiques existent dans la nature. Ces expériences sont appelées Tests de Bell, du nom de John Bell. En 1964, il a prouvé que les corrélations de l'intrication quantique ne peuvent être expliquées par aucune «théorie des variables cachées locales» - en d'autres termes, une théorie classique de la physique.¹ Il a ensuite montré qu'un test de Bell, comme le jeu CHSH, donne un test statistique simple pour la présence de corrélations non locales entre des systèmes séparés. Depuis les années 1960, de nombreux tests de Bell ont été menées expérimentalement, et le verdict est clair: la nature ne se comporte pas de façon classique.

Cleve, Hoyer, Toner et Watrous ont remarqué que les jeux non locaux / tests Bell peuvent être considérés comme une sorte de preuve interactive multiprouveur. Dans la théorie de la complexité, les preuves interactives sont des protocoles où certains étalons essaient de convaincre un vérifieur d'une solution à un calcul long et difficile, et le vérificateur essaie de déterminer efficacement si la solution est correcte. Dans un test de Bell, on peut penser aux prouveurs comme essayant de convaincre le vérificateur d'un déclaration physique: qu'ils possèdent l'intrication quantique.

Avec la lentille de calcul entraînée fermement sur les jeux non locaux, il devient alors naturel de poser des questions sur la complexité de jeux non locaux. Plus précisément, quelle est la complexité de l'approximation de la probabilité de gain optimale dans un jeu non local donné ? En termes de complexité, ceci est formulé comme une question sur la caractérisation de la classe MIP * (prononcé «étoile MIP»). C'est aussi une question bien motivée pour un expérimentaliste effectuant des tests de Bell: à tout le moins, ils voudraient déterminer si (a) les joueurs quantiques peuvent faire mieux que les joueurs classiques, et (b) quelle peut être la meilleure stratégie quantique possible atteindre?

L'étude de cette question dans le cas des joueurs classiques a conduit à certains des résultats les plus importants de la théorie de la complexité, tels que MIP = NEXP et par Théorème du PCP. En effet, le théorème du PCP dit qu’il est NP- difficile d'approcher la valeur classique d'un jeu non local (c'est-à-dire la probabilité de gain maximale des joueurs classiques) avec une précision additive constante (par exemple ). Ainsi, en supposant que P n'est pas égal à NP, nous ne devrions pas nous attendre à un algorithme polynomial pour cela. Cependant, il est facile de voir qu'il existe un algorithme de «force brute» pour ce problème: en prenant temps exponentiel pour énumérer toutes les stratégies déterministes possibles des joueurs, on peut calculer exactement la valeur classique des jeux non locaux.

Cependant, lorsque l'on considère des jeux avec des joueurs enchevêtrés, il n'est même pas clair s'il existe un algorithme de «force brute» similaire qui résout ce problème dans tous quantité de temps - oubliez le temps polynomial; même si nous nous accordons une durée de fonction exponentielle, doublement exponentielle, Ackermann, nous ne savons toujours pas comment résoudre ce problème d'approximation de la valeur quantique. Le problème est qu'il n'y a pas de limite supérieure connue sur le montant de l'intrication nécessaire pour que les joueurs jouent à un jeu non local. Par exemple, pour un jeu donné , une stratégie quantique optimale nécessite-t-elle un qubit, dix qubits ou qubits d'enchevêtrement? Sans limite supérieure, un algorithme de «force brute» ne saurait pas quelle est la taille d'une stratégie quantique à rechercher - il continuerait à énumérer des stratégies de plus en plus grandes dans l'espoir d'en trouver une meilleure.

Ainsi, l'approximation de la valeur quantique peut même ne pas être résolu en principe! Mais pourrait-il vraiment être non calculable? Peut-être que nous n'avons tout simplement pas trouvé le bon outil mathématique pour donner une limite supérieure à la dimension - peut-être que nous avons juste besoin de trouver une variante intelligente de, disons, Johnson-Lindenstrauss ou une autre technique de réduction de dimension.²

En 2008, des progrès prometteurs ont été accomplis vers une solution algorithmique à ce problème. Deux papiers [DLTW, NPA] (apparaissant sur arXiv le même jour!) a montré qu'un algorithme basé sur une programmation semi-définie peut produire une séquence de nombres qui convergent vers quelque chose appelé le valeur de l'opérateur de navettage d'un jeu non local.³ Si l'on pouvait montrer que la valeur de l'opérateur de navettage et la valeur quantique d'un jeu non local coïncident, cela donnerait un algorithme pour résoudre ce problème d'approximation!

Cependant, se demander si cet opérateur et ces valeurs quantiques sont les mêmes nous amène immédiatement au précipice de certains mystères profonds de la physique mathématique et des algèbres des opérateurs, loin de l'informatique et de la théorie de la complexité. Cela nous amène à la prochaine partie de l'éléphant.

Le mystère de la valeur quantique par rapport à la valeur de l'opérateur de navettage des jeux non locaux tient à deux façons différentes de modéliser Alice et Bob en mécanique quantique. Comme je l'ai mentionné plus tôt, la physique quantique prédit que la probabilité de gain maximale dans, disons, le jeu CHSH lorsque Alice et Bob partagent l'intrication est d'environ 85%. Comme pour toute théorie physique, ces prédictions sont faites en utilisant un cadre mathématique - des règles formelles pour modéliser des expériences physiques comme le jeu CHSH.

Dans une théorie de l'information quantique typique cahier de texte, les joueurs du jeu CHSH sont généralement modélisés de la manière suivante: le dispositif d'Alice est décrit territoire de l'État (tous les états possibles dans lesquels l'appareil pourrait se trouver), un Etat de et un ensemble de opérateurs de mesure (opérations pouvant être effectuées par l'appareil). Il n'est pas nécessaire de savoir ce que ces choses sont officiellement; la caractéristique importante est que ces trois choses sont suffisantes pour faire une prédiction sur l'appareil d'Alice - au moins lorsqu'il est traité isolément. De même, le périphérique de Bob peut être décrit en utilisant son propre espace d'état , Etat et opérateurs de mesure .

Cependant, dans le jeu CHSH, on veut faire des prédictions sur les appareils d'Alice et de Bob ensemble. Ici, les manuels disent qu'Alice et Bob sont décrits conjointement par le produit tenseur le formalisme, qui est une façon mathématique naturelle de «rapprocher des espaces séparés». Leur espace d'état est désigné par . L'État conjoint la description des dispositifs provient de cet espace produit tensoriel. Lorsque Alice et Bob effectuent indépendamment leurs mesures locales, cela est décrit par un opérateur de mesure du produit tensoriel des opérateurs de ainsi que les . Les étranges corrélations de la mécanique quantique surviennent lorsque leur état conjoint is enchevêtré, c'est-à-dire qu'il ne peut pas être écrit comme un état bien défini du côté d'Alice combiné avec un état bien défini du côté de Bob (même si l'espace d'état lui-même est deux espaces indépendants combinés ensemble!)

Le modèle de produit tensoriel fonctionne bien; il satisfait les propriétés naturelles que vous voudriez de l'expérience CHSH, telles que la contrainte qu'Alice et Bob ne peuvent pas se signaler instantanément. De plus, les prédictions faites dans ce modèle correspondent très précisément aux résultats expérimentaux!

Mais ce n'est pas toute l'histoire. Le formalisme des produits tenseurs fonctionne très bien mécanique quantique non relativiste, où les choses bougent lentement et où les énergies sont faibles. Pour décrire des scénarios physiques plus extrêmes - comme lorsque des particules sont écrasées ensemble à des vitesses proches de la lumière dans le Grand collisionneur de hadrons - les physiciens se tournent vers les plus puissants théorie des champs quantiques. Cependant, la notion de séparation spatio-temporelle dans les contextes relativistes devient notamment délicat. En particulier, lorsque l'on essaie de décrire des systèmes de mécanique quantique, il n'est plus évident de comment attribuer à Alice et Bob leurs propres espaces d'états indépendants, et il n'est donc pas clair comment mettre Alice et Bob relativistes dans le cadre du produit tensoriel!

Dans la théorie des champs quantiques, la localité est plutôt décrite en utilisant modèle d'opérateur de navettage. Au lieu d'attribuer à Alice et Bob leurs propres espaces d'état individuels, puis de les tendre ensemble pour obtenir un espace combiné, le modèle d'opérateur de navettage stipule qu'il n'y a qu'un unique espace monolithique pour Alice et Bob. Leur état commun est décrit à l'aide d'un vecteur de et les opérateurs de mesure d'Alice et Bob agissent tous deux sur . La contrainte qu'ils ne peuvent pas communiquer est capturée par le fait que les opérateurs de mesure d'Alice commuer avec les opérateurs de Bob. En d'autres termes, l'ordre dans lequel les joueurs effectuent leurs mesures sur le système n'a pas d'importance: Alice mesurant avant Bob, ou Bob mesurant avant Alice, les deux produisent les mêmes résultats statistiques. La localité est imposée par la commutativité.

Le cadre de l'opérateur de navettage contient le cadre du produit tensoriel comme cas spécial⁴, c'est donc plus général. Le modèle d'opérateur de navettage pourrait-il permettre des corrélations qui ne peuvent pas être capturées par le modèle du produit tensoriel, même approximativement⁵⁶? Cette question est connue sous le nom Le problème de Tsirelson, du nom du défunt mathématicien Boris Tsirelson.

Il existe un moyen simple mais utile de formuler cette question à l'aide de jeux non locaux. Ce que nous appelons la «valeur quantique» d'un jeu non local (dénoté par ) se réfère vraiment au supremum des probabilités de succès sur les stratégies de produits tensoriels pour Alice et Bob. S'ils utilisent des stratégies du modèle d'opérateur de navettage plus général, alors nous appelons leur probabilité de réussite maximale la valeur de l'opérateur de navettage of (dénoté par ). Puisque les stratégies de produits tensoriels sont un cas particulier des stratégies d'opérateurs de navettage, nous avons la relation pour tous les jeux non locaux .

Pourrait-il y avoir un jeu non local dont la valeur du produit tensoriel est différent de sa valeur d'opérateur de navettage? Avec ironie: y a-t-il un jeu qu'Alice et Bob pourraient mieux réussir s'ils utilisaient l'intrication quantique à des vitesses proches de la lumière? Il est difficile de trouver même un jeu candidat plausible pour lequel les valeurs d'opérateur quantique et de navettage peuvent différer. Le jeu CHSH, par exemple, a la même valeur d'opérateur quantique et de navettage; c'était prouvé par Tsirelson.

Si le produit tensoriel et les modèles d'opérateur de navettage sont les mêmes (c'est-à-dire la résolution «positive» du problème de Tsirelson), alors comme je l'ai mentionné plus tôt, cela a des ramifications inattendues: il y aurait un algorithme pour approximer la valeur quantique des jeux non locaux.

Comment fonctionne cet algorithme? Il se compose de deux parties: une procédure rechercher ci-dessouset un pour recherche d'en haut. L'algorithme de «recherche par le bas» calcule une séquence de nombres De est (approximativement) la meilleure probabilité de gagner quand Alice et Bob utilisent un de produit tenseur à XNUMX bits. Pour fixe , le nombre peut être calculé en énumérant sur (une discrétisation de) l'espace de tous les possibles -qubit stratégies. Cela prend un doublement exponentielle quantité de temps en - mais au moins c'est encore un temps fini! Cet algorithme naïf de «force brute» progressera lentement, calculant une séquence de meilleures probabilités de gain. Nous sommes garantis que dans la limite va à l'infini, la séquence converge vers la valeur quantique . Bien sûr, le problème est que la procédure de «recherche par le bas» ne sait jamais à quel point elle est proche de la vraie valeur quantique.

C'est là qu'intervient la «recherche d'en haut». Il s'agit d'un algorithme qui calcule une séquence différente de nombres où chacun est un limite supérieure sur la valeur de l'opérateur de navettage , et en outre comme va à l'infini, converge finalement vers . En outre, chaque peut être calculé par une technique connue sous le nom optimisation semi-définie; cela a été démontré par le deux papiers J'ai mentionné.

Rassemblons les morceaux. Si les valeurs d'opérateur quantique et de navettage d'un jeu coïncident (c.-à-d. ), nous pouvons alors exécuter les procédures de «recherche par le bas» et «recherche par le haut» en parallèle, entrelacer le calcul de la ainsi que les . Étant donné que les deux sont garantis pour converger vers la valeur quantique, à un moment donné la limite supérieure viendra dans certains à la limite inférieure , et donc nous aurions logé dans (une approximation de) . Nous y voilà: un algorithme pour approximer la valeur quantique des jeux.

Il ne reste sûrement plus qu'à résoudre le problème de Tsirelson par l'affirmative (que les corrélations des opérateurs de navettage peuvent être approximées par des corrélations de produits tensoriels), puis nous pourrions poser cette question embêtante sur la valeur quantique. Droite?

À la fin des années 1920, l'extraordinaire polymathe John von Neumann a formulé le premier cadre mathématique rigoureux pour la mécanique quantique récemment développée. Ce cadre, désormais familier aux physiciens et aux théoriciens de l'information quantique du monde entier, postule que les états quantiques sont des vecteurs dans un espace de Hilbert et que les mesures sont des opérateurs linéaires agissant sur ces espaces. Il n'a pas fallu longtemps à von Neumann pour réaliser qu'il y avait une théorie beaucoup plus profonde des opérateurs sur les espaces de Hilbert à découvrir. Avec Francis Murray, dans les années 1930, il a commencé à développer une théorie des «anneaux d'opérateurs» - aujourd'hui on les appelle algèbres de von Neumann.

La théorie des algèbres d'opérateurs s'est depuis épanouie dans un domaine riche et beau des mathématiques. Il reste inséparable de la physique mathématique, mais a établi des liens profonds avec des sujets tels que la théorie des nœuds et la théorie des groupes. L'un des objectifs les plus importants des algèbres d'opérateurs a été de fournir une classification des algèbres de von Neumann. Dans leur série d'articles sur le sujet, Murray et von Neumann ont d'abord montré que la classification des algèbres de von Neumann se réduit à la compréhension de leur facteurs, les atomes à partir desquels toutes les algèbres de von Neumann sont construites. Ensuite, ils ont montré que les facteurs des algèbres de von Neumann entrent dans l'une des trois espèces: type , Le type et tapez . Type Murray et von Neumann ont complètement classé les facteurs et ils ont fait beaucoup de progrès pour caractériser certains types les facteurs. Mais les progrès se sont arrêtés jusqu'aux années 1970, lorsque Alain Connes a classification De type facteurs (travail pour lequel il recevra plus tard la médaille Fields). Dans le même document de classification de 1976, Connes fait une remarque décontractée sur quelque chose appelé type facteurs⁷:

Nous construisons maintenant une intégration de développement . Apparemment, une telle intégration devrait exister pour tous les facteurs.

Cette ligne, écrite d'une manière presque jetable, a fini par être appelée «Problème d'intégration de Connes»: chaque séparable facteur intégré dans une ultrapuissance de l'hyperfini facteur? Il semble que Connes présume que c'est le cas (et donc cela est aussi appelé «l'intégration de Connes conjecture“). Depuis 1976, ce problème est devenu une question centrale des algèbres des opérateurs, nombreuses formulations équivalentes ainsi que les conséquences à travers les mathématiques.

En 2010, deux papiers (apparaissant à nouveau sur l'arXiv le même jour!) a montré que la portée de la conjecture d'intégration de Connes remonte aux fondements de la mécanique quantique. Si le problème d'intégration de Connes a une réponse positive (c'est-à-dire qu'il existe une intégration), alors le problème de Tsirelson (c'est-à-dire si l'opérateur de navettage peut être approximé par des corrélations de produits tensoriels) aussi a une réponse positive! Plus tard, c'était montré par Ozawa que le problème d'intégration de Connes est en fait équivalent au problème de Tsirelson.

N'oubliez pas que notre approche pour calculer la valeur des jeux non locaux reposait sur l'obtention d'une réponse positive au problème de Tsirelson. La séquence des articles [NPA, DLTW, Fritz, JNPPSW] montrent ensemble que la résolution - d'une manière ou d'une autre - du fonctionnement de cet algorithme de recherche par le bas et par la recherche par le haut réglerait essentiellement la conjecture d'intégration de Connes. Ce qui a commencé comme une question amusante à la périphérie de l'informatique et de la théorie de l'information quantique s'est transformé en une attaque contre l'un des problèmes centraux des algèbres d'opérateurs.

Nous avons maintenant terminé là où nous avons commencé: la complexité des jeux non locaux. Prenons un peu de recul et essayons de donner un sens à l'éléphant.

Même pour un théoricien de la complexité, «MIP * = RE»Peut apparaître ésotérique. Les classes de complexité MIP * ainsi que les RE se réfèrent à un sac à main déroutant de concepts: il y a Alice, Bob, les machines de Turing, les vérificateurs, les preuves interactives, l'intrication quantique. Quelle est la signification de l'égalité de ces deux classes?

Premièrement, il dit que le Le problème de l'arrêt a une preuve interactive impliquant des prouveurs enchevêtrés quantiques. Dans le problème Halting, vous voulez décider si une machine de Turing , si vous commenciez à l'exécuter, finirait par se terminer par une réponse bien définie, ou s'il resterait bloqué dans une boucle infinie. Alan Turing montré que ce problème est indécidable: il n'y a pas d'algorithme qui puisse résoudre ce problème en général. En gros, la meilleure chose que vous puissiez faire est de simplement appuyer sur l'interrupteur et attendez de voir s’il s’arrête. Si se coince dans une boucle infinie - eh bien, vous allez attendre pour toujours.

MIP * = RE montre avec l'aide d'Alice et Bob tout-puissants, un vérificateur à durée limitée peut exécuter une épreuve interactive pour «raccourcir» l'attente. Étant donné la machine de Turing la description (son «code source»), le vérificateur peut calculer efficacement la description d'un jeu non local dont le comportement reflète celui de . Si ne s'arrête finalement (ce qui pourrait arriver après un million d'années), il y a ensuite une stratégie pour Alice et Bob qui amène le vérificateur à accepter avec probabilité . En d'autres termes, . Si reste coincé dans une boucle infinie, alors quelle que soit la stratégie qu'Alice et Bob utilisent, le vérificateur rejette toujours avec une forte probabilité, donc est proche de .

En jouant à ce jeu non local, le vérificateur peut obtenir preuves statistiques qui est une machine de Turing qui finit par se terminer. Si le vérificateur joue et les prouveurs gagnent, alors le vérificateur doit croire qu'il est probable que s'arrête. S'ils perdent, le vérificateur conclut qu'il n'y a pas suffisamment de preuves que Arrête⁸. Le vérificateur ne s'exécute jamais réellement dans ce jeu; elle a déchargé la tâche sur Alice et Bob, que nous pouvons supposer être dieux informatiques capable d'effectuer instantanément des calculs d'un million d'années. Pour eux, le défi consiste plutôt à convaincre le vérificateur que si elle ont été d'attendre des millions d'années, elle assisterait à la fin de . Incroyablement, la quantité de travail mise par le vérificateur dans la preuve interactive est indépendant du temps qu'il faut pour faire halte!

Le fait que le problème de l'arrêt ait une preuve interactive semble à la limite absurde: si le problème de l'arrêt est insoluble, pourquoi devrions-nous nous attendre à ce qu'il soit vérifiable? Bien que la théorie de la complexité nous ait appris qu'il peut y avoir un grand écart entre la complexité de la vérification par rapport à la recherche, il a toujours été une différence de efficace: si les solutions à un problème peuvent être vérifiées efficacement, alors des solutions peuvent également être trouvées (bien qu'à un coût de calcul considérablement plus élevé). MIP * = RE montre qu'avec l'intrication quantique, il peut y avoir un gouffre de calculabilité entre vérifier les solutions et les trouver.

Passons maintenant aux conséquences de la non-complexité de MIP * = RE. Le fait que nous puissions encoder le problème Halting dans des jeux non locaux nous indique également immédiatement qu'il n'y a aucun algorithme pour approximer la valeur quantique. Supposons qu'il y ait un algorithme qui pourrait se rapprocher . Ensuite, en utilisant la transformation des machines de Turing en jeux non locaux mentionnés ci-dessus, nous pourrions utiliser cet algorithme pour résoudre le problème de Halting, ce qui est impossible.

Maintenant, les dominos commencent à tomber. Cela signifie que, en particulier, l'algorithme proposé «recherche par le bas» / «recherche par le haut» ne peut pas réussir à se rapprocher . Il doit y avoir un jeu , alors, pour lequel la valeur quantique est différente de la valeur de l'opérateur de navettage. Mais cela implique que le problème de Tsirelson a une réponse négative, et donc la conjecture d'intégration de Connes est fausse.

Nous avons seulement esquissé les contours les plus simples de cet éléphant, et pourtant il est assez difficile de le garder dans les yeux de l'esprit tout à la fois⁹. Cette histoire est étroitement liée à certains des développements les plus fondamentaux du siècle dernier: la mécanique quantique moderne, les algèbres d'opérateurs et la théorie de la calculabilité sont nées dans les années 1930. Einstein, Podolsky et Rosen ont écrit leur article historique remettant en question la nature de l'intrication quantique en 1935, et John Bell a découvert son célèbre test et l'inégalité en 1964. Connes a formulé sa conjecture dans les années 70, Tsirelson a apporté sa contribution aux fondements de la mécanique quantique dans les années 80, et à peu près à la même époque, les informaticiens inventaient la théorie des preuves interactives et des preuves probabilistes vérifiables (PCP).

Nous n'avons rien dit sur la preuve de MIP * = RE pour le moment (cela pourrait faire l'objet de futurs articles de blog), mais c'est indéniablement un produit de la théorie de la complexité. Le langage des épreuves interactives et des machines de Turing n'est pas seulement pratique mais nécessaire: en son cœur MIP * = RE est le théorème PCP classique, à l'aide de l'intrication quantique, récursé à l'infini.

Que se passe-t-il dans cette preuve? Quelles parties sont fondamentales et quelles parties sont inutiles? Quel est le noyau de celui-ci qui se rapporte à la conjecture d'intégration de Connes? Y a-t-il d'autres conséquences de ce résultat non calculable? Ce sont des questions à explorer dans les prochains jours et mois, et les réponses que nous trouverons seront fascinantes.

Remerciements. Merci à William Slofstra et Thomas Vidick pour leurs commentaires utiles sur ce post.

Source : https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/