🔆 🤴🏼 😺 MIP * = RE: preuve historique du domaine de l'informatique qui a provoqué l'effet domino en physique et en mathématiques 🛵 🤱 💆🏽

Les informaticiens ont franchi de nouvelles frontières dans la vérification des solutions aux problèmes par des méthodes informatiques. Dans le même temps, ils ont trouvé des réponses aux questions ouvertes les plus importantes de la mécanique quantique et des mathématiques pures.

En 1935, Albert Einstein, en collaboration avec Boris Podolsky et Nathan Rosen, a étudié la possibilité offerte par les nouvelles lois de la physique quantique: deux particules peuvent être enchevêtrées lorsque même de grandes distances ne violent pas leur interconnexion. L'année suivante, Alan Turing a formulé la première théorie générale du calcul et a prouvé qu'il existe des problèmes qui ne peuvent jamais être résolus par les ordinateurs. Ces deux idées ont révolutionné les domaines scientifiques auxquels elles se rapportent. De plus, il semblait qu'ils n'avaient rien à voir les uns avec les autres. Mais maintenant, la preuve

MIP * = RE les a combinés, ce qui a permis de résoudre de nombreux problèmes dans le domaine de l'informatique, de la physique et des mathématiques.

Les ordinateurs quantiques effectuent des calculs en utilisant des bits quantiques intriqués (qubits), plutôt que des zéros et des uns classiques. De nouvelles preuves indiquent que ces ordinateurs, théoriquement, peuvent être utilisés pour tester des solutions à un grand nombre de problèmes. Le lien entre l'intrication quantique et l'informatique traditionnelle a été une grande surprise pour de nombreux chercheurs.

Miguel Navascués est étudiant en physique quantique à l'Institut d'optique quantique et d'information quantique de Vienne. "C'était une surprise totale", a-t-il dit, commentant les preuves.

Les co-auteurs des preuves ont fixé l'objectif de définir les limites de l'approche de vérification des solutions aux problèmes de calcul. Cette approche implique l'intrication quantique. Ayant découvert ces limites, les chercheurs sont parvenus à la solution de deux autres problèmes, qui étaient presque un sous-produit de leur travail. Nous parlons de l'hypothèse de Zirelson en physique concernant la modélisation mathématique de l'intrication quantique et du problème connexe en mathématiques pures - le problème Conn dans la théorie de l'algèbre de von Neumann (problème d'intégration de Conn).

En conséquence, les résultats de l'application des preuves en mathématiques et en physique ont provoqué quelque chose comme l'effet domino.

«Toutes les idées appartiennent à la même période. C'est agréable de les voir se réunir à nouveau d'une manière aussi spectaculaire », a déclaré Henry Yuen.) de l'Université de Toronto - l'un des co-auteurs de la preuve. En dehors de lui dans ce travail ont participé Chzhenfen Ji ( Zhengfeng of Ji ) de l'Université de Technologie de Sydney, John Wright ( le John Wright ) de l'Université du Texas à Austin, Anand Natarajan ( Anand Natarajan ) et Thomas Vidic ( par Thomas Vidick ) du California Institute of Technology. Les cinq scientifiques travaillent tous dans le domaine de l'informatique.

Tâches insolubles

Turing, avant même l'avènement des ordinateurs, a jeté les bases sur lesquelles se construisent les réflexions sur l'informatique. Et lui, en même temps, a montré qu'il existe un certain problème que les ordinateurs ne peuvent résoudre, ce qui est prouvable. Il s'agit du soi-disant problème d'arrêt.

En règle générale, les programmes informatiques reçoivent quelque chose à l'entrée et génèrent une sortie. Mais parfois, ils se retrouvent coincés dans des cycles sans fin, ce qui signifie qu'ils ne s'arrêtent jamais. Lorsque cela se produit, il n'y a qu'un seul moyen de sortir de cette situation. Selon Henry Yuen, vous devez arrêter manuellement le programme. Vous avez juste besoin de mettre fin à son travail.

Turing a prouvé qu'il n'y a pas d'algorithme universel capable de déterminer si un programme sera jamais arrêté. Pour le savoir, vous devez exécuter le programme.

Henry Yuen, Thomas Widick, Zhengfeng Ji, Anand Natarajan, John Wright

«Vous avez attendu un million d'années et le programme ne s'est pas arrêté. Peut-être qu'il vous suffit d'attendre 2 millions d'années? Il n'y a aucun moyen de le dire à l'avance ", - explique William Slofstra ( William Slofstra ), un mathématicien de l'Université de Waterloo.

Turing, d'un point de vue technique, a prouvé que le problème de l'arrêt est insoluble. Même l'ordinateur le plus puissant que vous puissiez imaginer n'est pas en mesure de le gérer.

Après Turing, les informaticiens ont commencé à classer d'autres tâches selon leur complexité. Les tâches plus complexes nécessitent plus de puissance de traitement - plus de temps processeur et de mémoire. Il s'agit d'une étude de la complexité de calcul des algorithmes.

Par conséquent, tout problème pose deux grandes questions aux chercheurs: «Est-il difficile de le résoudre? Quelle est la difficulté de vérifier que la solution résultante est correcte? »

Interrogatoire de la décision par interrogatoire

Si les tâches sont relativement simples - leurs solutions peuvent être vérifiées indépendamment. Mais lorsque les tâches deviennent plus compliquées, même la vérification des résultats de leur solution peut être incroyablement difficile. Malgré cela, en 1985, les informaticiens ont décidé qu'il était possible de renforcer la confiance dans l'exactitude de la réponse même s'il n'était pas possible de le confirmer par eux-mêmes.

La méthode de vérification suit la logique des interrogatoires de police.

Si le suspect raconte une histoire mûrement réfléchie, l'enquêteur ne sera probablement pas en mesure de simplement prendre et de trouver la confirmation de chacun de ses détails. Mais en posant les bonnes questions, vous pouvez soit attraper le suspect sur un mensonge, soit confirmer la véracité de son histoire.

En termes d'informatique, les deux côtés de l'interrogatoire sont représentés par deux ordinateurs. Le premier est un puissant système informatique qui offre une solution au problème. Il s'appelle le témoin. Le second n'est plus un appareil aussi puissant qui pose des questions au testeur pour déterminer si la réponse qu'il propose est correcte. Cet ordinateur est appelé vérificateur.

Prenons un exemple simple. Supposons que quelqu'un (le vérificateur) souffre de daltonisme. Quelqu'un d'autre (le témoin) affirme que les deux boules sont peintes de couleurs différentes et ne sont pas différentes l'une de l'autre. Le vérificateur ne peut pas vérifier lui-même cette instruction. Mais, ayant intelligemment construit l'interrogatoire, il peut néanmoins savoir si c'est vraiment le cas.

Pour ce faire, vous pouvez masquer les boules derrière le dos et les mélanger. Et puis - demandez au prouveur quelle balle est dans quelle main. S'ils sont vraiment différents, le prouveur doit toujours répondre correctement à une telle question. Mais s'ils ont la même couleur, c'est-à-dire qu'ils ont exactement la même apparence, la moitié des réponses du prouveur se révéleront fausses.

Thomas Widick dit que si bien plus de la moitié des réponses du prouveur se révèlent être correctes, alors on peut être très confiant que les balles ont des couleurs différentes.

En posant des questions au prouveur, vous pouvez vérifier les solutions d'une classe de problèmes plus large que vous ne pouvez vérifier vous-même.

En 1988, des informaticiens ont examiné une situation dans laquelle deux prouveurs proposent des solutions au même problème. En fin de compte, s'il y a deux suspects qui peuvent être interrogés, cela simplifiera la divulgation du crime, ou - la vérification de la décision, car ils peuvent être contraints de jouer l'un contre l'autre.

Selon Thomas Widick, cela donne au vérificateur plus d'influence. Il interroge, pose des questions connexes, vérifie les réponses. Si les suspects disent la vérité, leurs réponses doivent correspondre la plupart du temps. S'ils mentent, leurs réponses divergent souvent.

De même, les chercheurs ont montré qu'en interrogeant deux témoins séparément, en leur posant des questions sur les solutions qu'ils ont trouvées, il est possible de vérifier rapidement les solutions d'une classe de problèmes encore plus étendue que lorsqu'ils travaillent avec un seul témoin.

Les études de la complexité de calcul des algorithmes peuvent sembler purement théoriques, mais elles sont très étroitement liées au monde réel. Les ressources dont les ordinateurs ont besoin pour résoudre les problèmes et vérifier les solutions - temps et mémoire - sont des ressources physiques. Pour cette raison, de nouvelles découvertes en physique pourraient changer l'approche de l'étude de la complexité informatique.

Anand Natarajan dit que si nous nous éloignons de la base physique classique des calculs et choisissons quelque chose de complètement différent, comme les mécanismes quantiques, nous aurons également une nouvelle théorie de la complexité de calcul.

La nouvelle preuve est le résultat final d'une collision d'informaticiens du 21e siècle avec l'une des idées les plus étranges de la physique du siècle dernier - avec l'idée de l'intrication quantique.

Le problème de Conn

Lorsque deux particules sont enchevêtrées, elles ne s’affectent en fait pas. Il n'y a pas de relation causale entre leurs actions. Einstein et ses co-auteurs ont travaillé sur cette idée dans un article de 1935. Par la suite, les physiciens et les mathématiciens ont essayé de trouver une manière mathématique de décrire ce que l'intrication quantique signifie réellement.

Cependant, ces efforts ont conduit à des résultats mitigés. Les scientifiques ont mis au point deux modèles mathématiques différents de l'intrication. Cependant, il n'était pas clair si ces modèles sont équivalents les uns aux autres.

La présence d'une telle dissonance potentielle, de manière détournée, a conduit à l'apparition d'un problème important dans le domaine des mathématiques pures. C'est le problème de Conn dans la théorie des algèbres de von Neumann. En fin de compte, il a joué le rôle d'une sorte d '«indice» dont cinq informaticiens ont profité pour dériver leurs preuves.

La première façon de modéliser l'intrication quantique était de percevoir les particules comme des objets isolés spatialement les uns des autres. Supposons qu'une de ces particules se trouve sur Terre et que l'autre se trouve sur Mars. La distance entre eux est quelque chose qui exclut une relation causale entre eux (ils sont séparés par causalité). C'est ce qu'on appelle un modèle de produit tensoriel.

Mais dans certaines situations, la séparation causale des entités n'est pas entièrement évidente. En conséquence, les mathématiciens sont arrivés à une deuxième façon, plus générale, de décrire l'indépendance causale.

Lorsque l'ordre dans lequel deux opérations sont effectuées n'affecte pas le résultat, l'opération est dite commutative: 3x2 est identique à 2x3. Dans ce deuxième modèle, les particules sont enchevêtrées lorsque leurs propriétés sont corrélées, mais l'ordre dans lequel les mesures sont effectuées n'a pas d'importance. On peut prendre des mesures sur la particule A afin de prédire la quantité de mouvement de la particule B, et vice versa. Dans tous les cas, le résultat sera le même. C'est ce qu'on appelle un modèle d'enchevêtrement d'opérateur de commutation.

Les deux descriptions de l'intrication utilisent des tableaux de nombres appelés matrices. Les matrices sont constituées de lignes et de colonnes. Le modèle de produit tensoriel utilise des matrices avec un nombre fini de lignes et de colonnes. Le modèle d'opérateur de commutation utilise des objets plus généraux qui fonctionnent comme des matrices avec un nombre infini de lignes et de colonnes.

Au fil du temps, les mathématiciens ont commencé à étudier ces matrices en tant qu'objets d'intérêt indépendant, n'ayant aucun lien avec le monde physique. Conformément à ce travail, le mathématicien Alain Connes a suggéré en 1976 qu'il devrait être possible d'approximer de nombreuses matrices de dimension infinie en utilisant des matrices de dimension finie. C'est l'une des conséquences du problème Conn dans la théorie des algèbres de von Neumann.

Au cours de la prochaine décennie, le physicien Boris Tsirelson a formulé une nouvelle version de ce problème, qui l'a de nouveau renvoyé au domaine de la physique. Zirelson a suggéré que les modèles du produit tensoriel et de l'opérateur de navettage sont approximativement équivalents l'un à l'autre. Cette affirmation a du sens, puisque ces deux modèles, théoriquement, sont deux façons différentes de décrire le même phénomène physique. Des travaux ultérieurs ont montré qu'en raison de la connexion entre les matrices et les modèles physiques qui les utilisent, les problèmes de Conn et Zirelson sont indirectement liés: si l'un est résolu, l'autre sera résolu.

Mais la solution à ces deux problèmes est venue d'un endroit complètement inattendu.

Physique du jeu

Dans les années 1960, le physicien John Bell a mis au point un test pour déterminer si l'intrication quantique est un véritable phénomène physique et non un concept théorique. Le test a utilisé quelque chose comme un jeu, dont les résultats ont permis de savoir si certains mécanismes non liés à la physique ordinaire fonctionnent pendant le jeu.

Plus tard, les informaticiens ont réalisé que ce test lié à l'intrication quantique peut également être utilisé comme un outil pour vérifier les solutions à des problèmes très complexes.

Mais avant de continuer, parlons du jeu. Imaginez qu'il y ait deux joueurs: Alice et Bob, ainsi qu'un terrain de jeu 3x3. Le présentateur attribue une ligne à Alice et l'invite à entrer 0 ou 1 dans chaque cellule, afin que leur somme donne un nombre impair. Bob obtient une colonne qui doit être remplie de zéros et de uns afin que leur somme donne un nombre pair. Ils gagneront s'ils mettent le même numéro à l'endroit où la ligne et la colonne se croisent. Il est impossible de communiquer avec lui.

Dans des circonstances ordinaires, le mieux qu'ils peuvent faire est de gagner 89% du temps. Mais si vous prenez en compte le facteur de l'intrication quantique, alors leurs chances sont améliorées.

Imaginez qu'Alice et Bob ont emmêlé des particules quantiques. Ils prennent des mesures de leurs particules et utilisent les résultats de mesure pour indiquer quoi écrire dans chaque cellule - 0 ou 1. Parce que les particules sont enchevêtrées, les résultats de mesure seront en corrélation les uns avec les autres. Et cela signifie également que les actions des joueurs seront interconnectées. En conséquence, il s'avère qu'ils pourront toujours gagner le match.

S'il y a des nombres différents dans la cellule où la ligne et la colonne se croisent, le jeu est perdu. S'ils sont les mêmes - gagnés.

Donc, s'il s'avère que deux joueurs réussissent étonnamment à jouer à ce jeu, alors nous pouvons conclure qu'ils utilisent quelque chose de différent de ce que la physique classique peut donner. Ces expériences "Bell" sont aujourd'hui appelées jeux "non locaux", se référant à la séparation des joueurs. En fait, les physiciens mènent des jeux similaires dans les laboratoires.

Henry Yuen dit qu'au fil des ans, les scientifiques ont mené des expériences pour prouver la réalité de ces phénomènes effrayants.

Comme pour l'analyse de n'importe quel jeu, vous devrez peut-être savoir à quelle fréquence les joueurs peuvent gagner dans un jeu non local, étant donné qu'ils jouent aussi bien qu'ils le peuvent. Par exemple, dans le cas du solitaire, vous pouvez calculer la fréquence des victoires possibles de celui qui joue parfaitement.

Mais en 2016, William Slofstra a prouvé qu'il n'y a pas d' algorithme général pour calculer la probabilité maximale exacte de gagner pour tous les jeux non locaux. En conséquence, les chercheurs ont posé la question: est-il possible de calculer au moins approximativement le pourcentage maximum de gains?

Les informaticiens ont trouvé la réponse en utilisant les deux modèles d'intrication quantique décrits ci-dessus. L'algorithme qui utilise le modèle de produit tensoriel définit la valeur minimale pour le calcul approximatif de la probabilité maximale de gagner pour tous les jeux non locaux. Un autre algorithme qui utilise le modèle de l'opérateur de commutation définit la valeur maximale.

La réponse donnée par les implémentations de ces algorithmes est d'autant plus précise que le programme s'exécute plus longtemps. Si l'hypothèse de Zirelson est vraie et que ces deux modèles sont équivalents, les limites inférieure et supérieure devraient se rapprocher l'une de l'autre, se transformant en une valeur unique représentant la probabilité maximale approximative de gagner.

Mais si l'hypothèse de Zirelson n'est pas vraie et que les deux modèles ne sont pas équivalents, alors, selon Henry Yuen, les limites supérieure et inférieure seront toujours séparées. Et il n'y aura aucun moyen de calculer même le pourcentage approximatif des gains pour les jeux non locaux.

Cinq chercheurs dans leur nouveau travail ont profité de l'argument pour savoir si les limites supérieure et inférieure convergent et si l'hypothèse de Zirelson est vraie ou fausse. Ils l'ont fait dans le but de trouver la réponse à la question de savoir dans quelles situations il est possible de vérifier les solutions aux problèmes de calcul.

Aide complexe

Au début des deux millièmes informaticiens, ils ont commencé à se demander comment l'éventail des tâches allait changer, dont les solutions peuvent être vérifiées en «interrogeant» deux prouveurs qui possèdent des particules complexes.

La plupart des scientifiques pensaient que la confusion nuit à la vérification. Au final, il sera plus facile pour les deux «suspects» de concilier de faux témoignages s'ils ont un moyen de coordonner les réponses.

Mais au cours des prochaines années, il est devenu clair que la déclaration opposée était vraie: en «interrogeant» les prouveurs qui ont des particules complexes, une classe de problèmes beaucoup plus large peut être vérifiée que lorsque l'on travaille avec des prouveurs qui n'ont pas de telles particules.

Thomas Widick dit que l'intrication est un moyen de créer des corrélations qui semblent aider les témoins à mentir. Mais, en fait, ce phénomène peut être utilisé à leur avantage.

Pour comprendre comment l'utiliser, il faut d'abord faire face à l'échelle quasi surnaturelle des tâches dont les solutions peuvent être vérifiées grâce à cette procédure interactive.

Imaginez un graphique - un ensemble de points (sommets) reliés par des lignes (faces). Vous devez savoir si, en utilisant trois couleurs, il est possible de peindre les sommets de sorte qu'il n'y ait pas deux sommets dans le graphique qui soient reliés par une face et en même temps peints de la même couleur. Si possible, un tel graphique est en «trois couleurs».

Si vous donnez une paire de preuves à un très grand graphique et qu'elles disent que c'est «tricolore», alors vous vous demandez peut-être s'il existe un moyen de vérifier leur réponse.

Dans le cas de très gros graphiques, il serait impossible de vérifier directement la réponse. Au lieu de cela, vous pouvez demander à chacun des testeurs de quelle couleur a l'un des deux sommets connectés. Si chacun d'eux rapporte des couleurs différentes, et ils donneront des réponses similaires à chaque fois qu'ils seront interrogés à ce sujet, nous aurons confiance que le graphique est en effet «tricolore».

Mais même cette stratégie d'interrogation ne fonctionnera pas sur d'énormes graphes avec plus de visages et de sommets que d'atomes dans l'univers. Même poser une question spécifique («Dites-moi la couleur du sommet XYZ») devient un problème insupportable pour quelqu'un qui essaie de vérifier une solution à un problème. La quantité de données nécessaires pour spécifier simplement le nom d'un sommet particulier est supérieure à ce que le vérificateur peut stocker dans la mémoire à sa disposition.

Mais l'intrication quantique rend possible un schéma de travail, dans l'application duquel les testeurs formulent eux-mêmes les questions.

«Le vérificateur n'a pas besoin de poser de questions. Le vérificateur oblige les promoteurs à formuler ces questions de manière indépendante et à y répondre », explique John Wright.

Le vérificateur a besoin des prouveurs pour signaler les couleurs des sommets connectés. Si les sommets ne sont pas connectés, les réponses aux questions ne diront pas si le graphique est «tricolore» ou non. En d'autres termes, le vérificateur a besoin que les testeurs posent des questions connexes. L'un des prouveurs pose des questions sur le sommet de ABC et le second sur le sommet de XYZ. On suppose que les deux pics sont connectés, même si aucun des prouveurs ne sait à quel pic l'autre «pense». (Cela ressemble à la façon dont Alice et Bob espèrent écrire le même nombre dans la même cellule, malgré le fait qu'aucun d'entre eux ne connaisse la ligne ou la colonne du tableau avec laquelle l'autre travaille.)

Si deux prouveurs formulaient de manière complètement indépendante de telles questions, alors il n'y aurait pas de mécanisme pour les forcer à sélectionner des sommets connectés (corrélateurs), de manière à permettre au vérificateur de vérifier leurs réponses. Mais une telle corrélation est exactement ce que l'intrication quantique peut réaliser.

Thomas Widick dit qu'ils vont utiliser des subtilités pour renvoyer pratiquement tous les cas aux témoins. Les scientifiques obligent les testeurs à choisir leurs propres questions.

À la fin de cette procédure, chacun des étalons signale une couleur de sommet. Le vérificateur vérifie s'il s'agit de couleurs différentes ou non. Si le graphique est en effet «tricolore», alors les testeurs ne doivent jamais rapporter la même couleur.

Selon Henry Yuen, si le graphique est «tricolore», alors les testeurs pourront convaincre le chercheur qu'il en est bien ainsi.

Il s'est avéré que cette procédure de vérification est un autre exemple de jeu non local. Les correcteurs «gagnent» s'ils convainquent le chercheur que leur décision est correcte.

En 2012, Thomas Widik et Tsuyoshi Ito) a prouvé que l'on peut jouer à une grande variété de jeux non locaux en utilisant des prouveurs complexes pour tester des solutions. Cela s'applique, au minimum, au même nombre de tâches qui peuvent être vérifiées en interrogeant deux ordinateurs classiques. Ainsi, l'utilisation de preuves confuses ne nuit pas à la vérification. L'année dernière, Anand Natarajan et John Wright ont prouvé que l'interaction avec des témoins complexes étend en fait la classe de problèmes dont les solutions peuvent être vérifiées.

Mais les informaticiens ne connaissaient pas la gamme complète des tâches dont les solutions peuvent être vérifiées en utilisant cette approche. Maintenant, ils le savent.

effet domino

Dans leurs nouveaux travaux, cinq scientifiques ont prouvé que «l'interrogatoire» de témoins confus permet de vérifier des solutions à des problèmes insolubles, y compris la solution d'un problème d'arrêt.

Henry Yuen dit que les modèles de ce type ont des capacités de vérification inimaginables.

Mais la tâche d'arrêt est insoluble. Et ce fait a été la force motrice qui a conduit à la preuve finale.

Imaginez que vous avez remis le programme à quelques témoins confus. Vous leur avez demandé si ce programme s'arrêterait jamais. Vous êtes prêt à vérifier leurs réponses à travers une sorte de jeu non local. Les vérificateurs génèrent des questions et «gagnent» en fonction de la coordination de leurs réponses.

Si le programme s'arrête, les promoteurs devraient pouvoir gagner la partie dans 100% des cas. Ceci est similaire à un exemple avec un graphique - s'il est vraiment «tricolore», alors les prouveurs alambiqués ne devraient jamais rapporter la même couleur pour les sommets connectés. Si le programme ne s'arrête jamais, les testeurs ne devraient gagner que par hasard - dans 50% des cas.

Cela signifie que si quelqu'un vous demande de déterminer la probabilité maximale approximative de gagner pour un jeu non local particulier, vous devrez d'abord résoudre le problème d'arrêt. Mais résoudre ce problème est impossible. Cela signifie qu'il est impossible de trouver le niveau maximum approximatif de probabilité de gagner pour les jeux non locaux ainsi que pour le problème d'arrêt.

Et cela, à son tour, signifie que l'hypothèse de Tsirelson est fausse: les deux modèles d'intrication quantique ne sont pas équivalents. S'ils étaient équivalents, il serait alors possible de réduire les bornes inférieure et supérieure à la même valeur et de calculer la probabilité maximale approximative de gagner.

David Pérez-García de l'Université Complutense de Madrid dit qu'un tel algorithme ne peut pas exister, par conséquent les deux [modèles] doivent être différents.

Le nouveau travail prouve que la classe de problèmes dont les solutions peuvent être vérifiées à l'aide d'éprouveurs quantiques complexes, une classe appelée MIP *, est exactement égale à la classe de problèmes qui ne sont pas plus compliqués que le problème d'arrêt - la classe RE. Le titre de l'article contient une indication concise de ceci: «MIP * = RE».

Au cours de la preuve que les deux classes de complexité sont égales, les scientifiques ont prouvé que l'hypothèse de Tsirelson était fausse, ce qui, grâce à des travaux antérieurs, signifie que l'hypothèse Conn est également fausse.

Les chercheurs travaillant dans leurs domaines respectifs ont été stupéfaits par le fait que des solutions à de tels problèmes à grande échelle ont été obtenues grâce aux preuves du domaine de l'informatique, qui, semble-t-il, n'est pas liée aux mathématiques et à la physique.

Miguel Navazquez dit que s'il avait vu un article avec le titre MIP * = RE, il n'aurait pas pensé qu'elle avait quelque chose en commun avec son travail. Il était co-auteur d'un ouvrage antérieur reliant les hypothèses de Zirelson et Conn. Pour lui, c'était une surprise totale.

Les physiciens et mathématiciens quantiques commencent tout juste à maîtriser une nouvelle preuve. Avant cela, les mathématiciens s'intéressaient à la question de savoir s'ils pouvaient approximer des matrices de dimension infinie, en utilisant plutôt de grandes matrices de dimension finie. Maintenant, grâce au fait que l'hypothèse de Conn s'est avérée fausse, ils savent que cela ne peut pas être fait.

"Leurs résultats indiquent que ce n'est pas possible", a déclaré William Slofstra.

Les informaticiens n'ont pas cherché à analyser l'hypothèse de Conn. Et ils ne sont donc pas les mieux placés pour expliquer les conséquences possibles de la résolution de ce problème.

«Personnellement, je ne suis pas mathématicien. «Je ne comprends pas très bien la formulation initiale de l'hypothèse Conn», explique Anand Natarajan.

Lui et ses co-auteurs s'attendent à ce que les mathématiciens traduisent de nouveaux résultats dans leur propre langue. Dans une publication rapportant la preuve, Thomas Widick écrit: "Je ne doute pas qu'au final, la théorie de la complexité de calcul ne sera pas nécessaire pour obtenir des résultats purement mathématiques."

Néanmoins, lorsque d'autres chercheurs se familiarisent avec la preuve, le chemin de la recherche, grâce auquel il a été possible de l'atteindre, s'achève. Pendant plus de trois décennies, les informaticiens ont simplement tenté de savoir jusqu'où la vérification interactive des solutions aux problèmes pouvait les mener. Maintenant, devant eux se trouve la réponse, sous la forme d'un long article avec un titre simple et avec des échos des idées de Turing.

«Il existe de nombreux ouvrages dont les auteurs se demandent seulement quelles sont les possibilités d'une procédure de vérification utilisant deux preuves quantiques complexes. Nous savons maintenant à quel point cette procédure est puissante. Cette histoire a pris fin », explique Anand Natarajan.

Chers lecteurs! Que signifie la preuve MIP * = RE pour la zone dans laquelle vous travaillez?