🤯 🏳️ 🧑🏿‍🤝‍🧑🏻 Une preuve significative du théorème de l'informatique capture la physique avec les mathématiques 📷 🤷🏼 🚅

Les spécialistes en informatique ont identifié de nouvelles frontières dans les connaissances vérifiées par le calcul. Et en même temps, ils ont résolu des problèmes importants de la mécanique quantique et des mathématiques pures.

En 1935, Albert Einstein, avec Boris Podolsky et Nathan Rosen, a tenté de faire face à l'opportunité qui s'est ouverte avec les nouvelles lois de la physique quantique: "l'intrication" de deux particules, qui dans ce cas peuvent être séparées par une distance énorme.

L'année suivante, Alan Turing formule la première théorie généralisée du calcul et prouve l'existence de problèmes, en principe non soumis aux ordinateurs.

Ces deux idées ont révolutionné leurs domaines respectifs. De plus, il semblait qu'ils n'avaient rien à voir les uns avec les autres. Cependant, maintenant une preuve significative les unit, résolvant simultanément beaucoup de problèmes de l'informatique, de la physique et des mathématiques.

Les nouvelles preuves suggèrent que les ordinateurs quantiques qui effectuent des calculs en utilisant des bits quantiques, ou «qubits», plutôt que des zéros et des uns classiques, peuvent théoriquement être utilisés pour confirmer des solutions à un large éventail de problèmes. Le lien entre l'intrication quantique et la technologie informatique a été un choc pour de nombreux chercheurs.

"C'était complètement inattendu", a expliqué Miguel Navazquez.étudie la physique quantique à l'Institut d'optique quantique et d'information quantique de Vienne.

Les co-auteurs de la preuve ont décidé de déterminer les limites des possibilités de confirmation des solutions aux problèmes de calcul. Leur approche utilise la confusion. Ayant trouvé ces limites, les chercheurs ont en même temps, comme effet presque secondaire, répondu à deux autres questions: le problème de Zirelson en physique concernant la modélisation mathématique des enchevêtrements, et le problème connexe des mathématiques pures, l' hypothèse de Conn sur l'emboîtement.

Les résultats sont finalement tombés comme des dominos.

«Toutes les idées originales sont nées à peu près au même moment. Il est commode qu'ils se soient tous réunis d'une manière si étonnante », a déclaré Henry Ewan.de l'Université de Toronto, l'un des auteurs de la preuve. Autres auteurs: Zhengfeng Ji de l'Université de technologie de Sydney, Anand Natarajan et Thomas Widick du California Institute of Technology et John Wright de l'Université du Texas à Austin. Tous les cinq sont des informaticiens.

Problèmes insolubles

Turing a identifié la principale plate-forme pour l'étude de l'informatique avant même l'avènement des ordinateurs eux-mêmes. Et littéralement, il a immédiatement montré que les ordinateurs, en principe, ne pouvaient pas résoudre certains problèmes - et que cela pouvait être prouvé. La question est de savoir si le programme qui résout un problème particulier termine son travail.

En règle générale, les programmes informatiques reçoivent des données d'entrée et, après un certain temps, produisent des données de sortie. Mais parfois, ils sont coincés dans des cycles sans fin, ce qui fait tourner leurs engrenages pour toujours. Lorsque cela vous arrive, il ne vous reste qu'une seule option.

«Je dois clouer manuellement le programme. Arrêtez-la simplement », a déclaré Ewan.

Turing a prouvé qu'aucun algorithme général ne peut déterminer si un programme terminera son exécution ou fonctionnera pour toujours. Pour le savoir, vous devez exécuter le programme lui-même.

Ewan, Vidik, Ji, Natarajan et Wright

«Vous avez attendu un million d'années et le programme n'a pas fini de fonctionner. Avez-vous besoin d'attendre encore un million d'années? Il n'y a pas de réponse à cette question », a déclaré William Slofstra , mathématicien à l'Université de Waterloo.

Techniquement parlant, la tâche d'arrêter un programme est insoluble - même l'ordinateur le plus puissant que vous pouvez imaginer ne peut pas le résoudre.

Après Turing, les informaticiens ont commencé à classer d'autres tâches en fonction de leur complexité. Des tâches plus complexes nécessitent plus de ressources informatiques à résoudre - plus de temps pour travailler, plus de mémoire. Étudiez donc la complexité de calcul des tâches.

Par conséquent, vous pouvez poser deux questions sur chaque tâche: «Est-il difficile de la résoudre?» »et« Est-il difficile de vérifier la bonne réponse? »

Interrogatoire pour confirmation

Dans le cas de tâches simples, la réponse peut être vérifiée indépendamment. Mais à mesure qu'ils deviennent plus compliqués, même vérifier la réponse peut devenir une tâche impossible. Cependant, en 1985, les informaticiens ont réalisé qu'il était possible de vérifier l'exactitude de la réponse, même s'il était impossible de la confirmer vous-même.

Cette méthode suit la logique d'une enquête policière. Si le suspect raconte une histoire déroutante, vous ne pourrez peut-être pas en vérifier tous les détails. Mais en posant les bonnes questions, vous pouvez attraper le suspect dans un mensonge, ou vous pouvez être assuré de la vérité de l'histoire.

En termes informatiques, l'interrogatoire contient un ordinateur puissant qui offre une solution au problème - connu sous le nom de «prouveur» - et un ordinateur moins puissant qui demande au prouveur des questions de déterminer l'exactitude de la réponse, connu sous le nom de «test».

Un exemple simple: imaginez que vous ne faites pas de distinction entre les couleurs, et l'autre personne - le prouveur - prétend que deux des boules ont une couleur différente. Vous ne pouvez pas vérifier vous-même cette déclaration, mais grâce à un interrogatoire ingénieux, vous pouvez toujours vérifier qu'elle est vraie.

Mettez les boules derrière et mélangez. Demandez au prouveur de vous dire laquelle a quelle couleur. S'ils sont vraiment de couleurs différentes, le prouveur doit constamment répondre correctement à la question. S'ils sont de la même couleur - c'est-à-dire qu'ils ont la même apparence - le prouveur dans la moitié des cas exprimera la mauvaise supposition.

"Si je constate que vous avez obtenu beaucoup plus de succès que dans la moitié des cas, alors je serai presque sûr qu'ils ne sont pas de la même couleur", a déclaré Vidik.

En posant des questions au prouveur, vous pouvez confirmer l'exactitude des solutions à un éventail de tâches plus large que vous ne pourriez le résoudre vous-même.

En 1988, les informaticiens ont réfléchi à ce qui se passerait si deux prouveurs suggéraient des solutions au même problème. Après tout, si vous avez la possibilité d'interroger deux suspects, il vous sera encore plus facile de résoudre le crime ou de confirmer l'exactitude de la décision - ils peuvent être comparés l'un à l'autre.

«Pour ceux qui le vérifient, cela donne plus de place à la pression. Vous interrogez, posez des questions liées à l'affaire, recoupez les réponses », a déclaré Vidik. Si les suspects disent la vérité, leurs réponses devraient coïncider la plupart du temps. S'ils mentent, il y aura plus de contradictions.

De même, les chercheurs ont montré qu'en interrogeant séparément les deux prouveurs sur leurs réponses, on peut rapidement confirmer l'exactitude de la solution pour une classe de problèmes encore plus large, par rapport à celle que l'on peut approcher avec un seul prouveur.

La complexité informatique peut vous sembler une idée purement théorique, mais elle est néanmoins étroitement liée au monde réel. Les ressources dont les ordinateurs ont besoin pour résoudre les problèmes et confirmer les décisions - temps et mémoire - sont fondamentalement physiques. Par conséquent, de nouvelles découvertes en physique peuvent changer la complexité de calcul.

"Si vous choisissez un ensemble différent de lois physiques, par exemple, le monde quantique au lieu du monde classique, alors une autre théorie de la complexité peut en être déduite", a déclaré Natarajan.

La nouvelle preuve est le résultat final de la confrontation entre un informaticien du 21e siècle et l'une des idées les plus étranges de la physique du 20e siècle: l'intrication.

L'hypothèse de nidification de Conn

Lorsque deux particules s'emmêlent, elles ne s'influencent pas l'une l'autre - elles n'ont aucune relation causale. Einstein et al.ont révélé cette idée dans un article de 1935. Après cela, les physiciens et les mathématiciens ont essayé de trouver une manière mathématique de décrire ce que signifie réellement la confusion.

Cependant, il y avait une certaine confusion. Les scientifiques ont proposé deux modèles mathématiques différents de l'intrication - et le fait qu'ils soient équivalents l'un à l'autre n'était pas du tout évident.

Indirectement, cette dissonance potentielle a influencé l'émergence d'un problème important du domaine des mathématiques pures, l'hypothèse de Conn de l'emboîtement. Et à la fin, cela a également servi de schisme, dont cinq informaticiens ont profité dans leurs nouvelles preuves.

La première façon de modéliser l'intrication consiste à imaginer des particules spatialement isolées. L'un d'eux, par exemple, est sur Terre, et l'autre sur Mars; la distance entre eux exclut une relation causale. C'est ce qu'on appelle un modèle de produit tensoriel.

Mais dans certaines situations, il n'est pas tout à fait clair si deux objets sont réellement isolés causalement l'un de l'autre. Par conséquent, les mathématiciens ont trouvé une manière plus générale de décrire l'indépendance causale.

Lorsque la séquence d'opérations sur les objets n'a pas d'importance, l'opération est considérée comme commutée: 3 x 2 donnera la même chose que 2 x 3. Dans le deuxième modèle, les particules sont enchevêtrées lorsque leurs propriétés sont corrélées, mais la séquence de mesures n'a pas d'importance. Mesurer la particule A pour prédire l'élan de la particule B, ou vice versa. Dans tous les cas, la réponse sera la même. C'est ce qu'on appelle un modèle d'enchevêtrement d'opérateurs commutés.

Les deux descriptions de l'intrication utilisent des tableaux de nombres organisés en colonnes et en lignes - matrices. Le modèle de produit tensoriel utilise des matrices avec un nombre fini de colonnes et de lignes. Le modèle d'enchevêtrement de l'opérateur de commutation utilise un objet plus général qui fonctionne comme une matrice mais qui possède un nombre infini de lignes et de colonnes.

Au fil du temps, les mathématiciens ont commencé à explorer ces matrices par leurs propres moyens, indépendamment de leur lien avec la physique. Dans le cadre de ce travail, le mathématicien Alain Conn en 1976 a émis l'hypothèse que de nombreuses matrices de dimension infinie pouvaient être approximées par des matrices de dimension finie. Ce fut l'une des conclusions de l'hypothèse de Conn de la nidification.

Dans la prochaine décennie, le physicien soviétique [dans le physicien d'origine, mais sur Wikipédia est répertorié comme mathématicien / env. trad.] Boris Tsirelson a proposé sa propre version de ce problème, qui a de nouveau été associé à la physique. Zirelson a suggéré que le produit tensoriel et les modèles d'opérateurs commutatifs décrivant l'intrication sont à peu près équivalents. Cela a du sens, car théoriquement, ce sont deux façons différentes de décrire le même phénomène physique. Les travaux ultérieurs ont montré qu'en raison de la connexion des matrices et des modèles physiques qui les utilisent, l'hypothèse de Conn sur l'imbrication et le problème de Zirelson se suivent: résolvez l'une et vous résolvez l'autre.

Cependant, la solution à ces deux problèmes est apparue dans une direction complètement différente.

Physique et jeux

Dans les années 1960, le physicien John Bell a proposé un test pour déterminer si l'intrication est un véritable phénomène physique ou simplement une idée théorique. Quelque chose comme un jeu a participé au test, dont le résultat a indiqué si quelque chose d'autre que la physique non quantique ordinaire a joué un rôle dans l'expérience.

Plus tard, les informaticiens se rendront compte que ce test d'intrication peut également être utilisé comme un outil pour valider des solutions à des problèmes très complexes.

Mais d'abord, pour comprendre comment ces jeux fonctionnent, imaginez deux joueurs, Alice et Bob, et une boîte 3x3. Le juge donne une ligne à Alice et lui suggère de mettre 0 ou 1 ligne dans chacune des cellules afin que la somme des nombres soit impaire. Bob se voit attribuer une colonne, et il doit remplir toutes ses cellules afin que la somme des nombres soit égale. Ils gagnent s'ils mettent le même nombre dans la même cellule - là où la ligne et la colonne sélectionnées se croisent. Mais en même temps, ils ne peuvent pas communiquer.

Dans des conditions normales, le mieux dont les joueurs sont capables est de gagner dans 89% des cas. Mais dans le monde quantique, ils peuvent améliorer ce résultat.

Supposons qu'Alice et Bob partagent une paire de particules enchevêtrées. Chacun d'eux prend des mesures de sa particule et utilise les résultats pour déterminer s'il faut écrire 0 ou 1 dans chaque cellule. Puisque les particules sont enchevêtrées, les résultats de leurs mesures seront corrélés les uns avec les autres, ce qui signifie que leurs réponses seront également corrélées - ce qui signifie , ils pourront gagner dans 100% des cas.

Donc, si vous voyez que deux joueurs gagnent souvent le jeu de manière inattendue, vous pouvez conclure qu'ils utilisent quelque chose en dehors de la physique classique. Désormais, les expériences de Bell sont appelées jeux «non locaux», se référant à la séparation des joueurs. Et les physiciens font de telles expériences en laboratoire.

"Les gens ont fait de telles expériences pendant des années, et il en résulte que cet effet effrayant existe vraiment", a déclaré Ewan.

Lors de l'analyse d'un jeu, vous pouvez avoir besoin d'informations sur la fréquence à laquelle les joueurs gagnent un jeu non local s'ils essaient de jouer de la meilleure façon possible. Par exemple, si vous prenez Solitaire Solitaire, vous pouvez calculer la probabilité avec laquelle le joueur qui joue parfaitement pourra gagner.

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 dans des jeux non locaux. Les chercheurs ont posé la question: est-il possible de prédire au moins grossièrement le pourcentage maximum de gains?

Les informaticiens ont cherché une réponse en utilisant deux modèles décrivant les subtilités. L'algorithme utilisant le modèle du produit tensoriel a déterminé la limite inférieure, ou la valeur minimale de la probabilité maximale approximative de gagner pour tous les jeux non locaux. Un autre algorithme qui a utilisé le modèle d'enchevêtrement avec un opérateur d'accès à distance a déterminé sa limite supérieure.

Plus ces algorithmes fonctionnent longtemps, plus le résultat qu'ils produisent est précis. Si la prédiction de Zirelson est vraie et que ces deux modèles sont vraiment équivalents, les limites inférieure et supérieure devraient progressivement se rapprocher, convergeant vers une valeur unique de la probabilité maximale approximative de gagner.

Mais si la prédiction de Cirelson est fausse et que les deux modèles ne sont pas équivalents, "les limites inférieure et supérieure resteront à jamais séparées", a déclaré Ewan. Il sera impossible de calculer même la valeur approximative de la probabilité maximale de gagner pour les jeux non locaux.

Dans le nouveau travail, cinq chercheurs ont utilisé ce sujet - si les limites inférieure et supérieure convergent et si l'hypothèse de Zirelson est vraie - pour résoudre une question distincte sur la possibilité de confirmer l'exactitude de la solution d'un problème de calcul.

Aide complexe

Au début des années 2000, les informaticiens ont pensé: comment la gamme de tâches changera-t-elle, dont les solutions peuvent être confirmées en interrogeant deux prouveurs avec des particules complexes?

La plupart ont décidé que l'enchevêtrement jouerait contre la confirmation. En effet, il sera plus facile pour deux suspects de construire un mensonge cohérent s'ils ont un moyen de coordonner les réponses.

Mais ces dernières années, les informaticiens ont réalisé que c'était en fait le contraire: en interrogeant les prouveurs, en divisant des paires de particules enchevêtrées, on peut confirmer des solutions à un éventail de problèmes beaucoup plus large que sans enchevêtrement.

"La confusion est un moyen d'obtenir une corrélation qui semble les aider à mentir et à tricher", a déclaré Vidik. "Mais vous pouvez réellement l'envelopper en votre faveur."

Pour comprendre comment cela est possible, vous devez d'abord évaluer la gamme presque surnaturelle des tâches dont vous pouvez vérifier les solutions avec cette procédure interactive.

Imaginez un graphique - un ensemble de points (sommets) reliés par des lignes (arêtes). Vous voudrez peut-être savoir s'il est possible de colorer les sommets avec trois couleurs afin qu'il n'y ait pas de paires de sommets de la même couleur, unis par un bord commun.

Si vous donnez à quelques personnes la preuve d'un très grand graphique et qu'ils disent qu'il peut être coloré en trois couleurs comme décrit, vous penserez: existe-t-il un moyen de vérifier cette réponse?

Les très grands graphiques ne peuvent pas être vérifiés directement. Au lieu de cela, vous pouvez demander à chaque prouveur de signaler la couleur de deux sommets reliés par une arête. S'ils signalent des couleurs différentes et donnent chaque fois des couleurs différentes lors de l'enquête sur d'autres sommets, votre confiance dans le fait que la peinture en trois couleurs fonctionne augmentera.

Mais une telle stratégie d'interrogation cesse également de fonctionner lorsque les graphiques deviennent vraiment grands - lorsque le nombre d'arêtes et de sommets commence à dépasser le nombre d'atomes dans l'Univers. Pour le vérificateur, même une tâche telle que poser une question spécifique («dites-moi la couleur du sommet XYZ») devient insupportable - la quantité de données nécessaires pour nommer un sommet particulier dépasse la mémoire de travail à sa disposition.

Cependant, la confusion permet aux prouveurs de poser eux-mêmes des questions.

«L'examinateur n'a pas besoin de comprendre les questions. L'inspecteur fait calculer les questions par lui-même », a expliqué Wright.

L'inspecteur a besoin des étalons pour lui dire les couleurs des sommets connectés. Si les sommets ne sont pas connectés, les réponses à la question ne diront rien sur la possibilité de colorier le graphique en trois couleurs. En d'autres termes, l'examinateur souhaite que le prouveur pose des questions connexes: un prouveur pose la question sur le sommet ABC et l'autre sur le sommet XYZ. Et j'aimerais que ces deux pics soient connectés, bien qu'aucun des prouveurs ne sache de quel pic l'autre parle. De la même manière qu'Alice et Bob espèrent mettre le même nombre dans le même carré, bien qu'aucun d'eux ne sache avec quelle ligne et colonne l'autre travaille.

Si chacun des deux prouveurs émettait une question complètement par lui-même, il ne pourrait pas être obligé de sélectionner des pics connectés ou corrélatifs, afin que l'examinateur puisse confirmer ses réponses. Cependant, l'intrication vous permet simplement de créer une corrélation.

«Nous allons utiliser la confusion pour vider tout le travail sur les étalons. Nous leur ferons choisir leurs propres questions », a déclaré Vidik.

À la fin de la procédure, chacun des étalons rapporte une couleur. Le réviseur vérifie leur correspondance. Si un graphique peut réellement être coloré en trois couleurs, les épreuves ne devraient jamais produire la même couleur.

"Si le décompte peut être peint en trois couleurs, les prouveurs peuvent vous en convaincre", a déclaré Ewan.

Il s'avère que cette procédure de confirmation est un autre exemple de jeu non local. Les prouveurs «gagnent» en vous convaincant de la justesse de leur décision.

En 2012, Vidik et Tsiyoshi Ito ont prouvé qu'il était possible, en jouant à divers jeux non locaux avec des preuves confuses, de confirmer les réponses à au moins le même nombre de tâches que lors de l'interrogatoire de deux ordinateurs classiques. Autrement dit, l'utilisation de prouveurs déroutants ne nuit pas à la confirmation de leurs ottètes. Et l'année dernière, Natarajan et Wright ont prouvé que l'interaction avec les prouveurs alambiqués étend en fait la classe des tâches validées.

Cependant, à ce stade, les informaticiens n'ont pas deviné la taille de la gamme complète des tâches, dont les solutions peuvent être confirmées de manière similaire.

Cascade de conséquences

Dans le nouveau travail, cinq informaticiens prouvent que l'interrogatoire des prouveurs alambiqués peut confirmer des solutions aux problèmes non résolus, y compris le problème d'arrêt.

"Les capacités de validation de ce modèle sont incroyables", a déclaré Ewan.

Cependant, le problème d'arrêt ne peut pas être résolu. Et ce fait est devenu la clé pour compléter la preuve.

Supposons que vous donniez un programme à quelques prouveurs déroutants. Vous leur demandez de dire si son exécution va s'arrêter. Vous êtes prêt à tester leur réponse à travers une variété de jeux non locaux: les prouveurs posent des questions et gagnent en fonction de la cohérence de leurs réponses.

Si le programme s'arrête vraiment, les prouveurs devraient pouvoir gagner ce jeu dans 100% des cas - comme dans le cas d'un graphique qui peut être coloré en trois couleurs, lorsque les prouveurs alambiqués n'ont pas à donner la même couleur pour deux sommets connectés. Si le programme ne s'arrête pas, les prouveurs ne devraient gagner que par hasard - c'est-à-dire 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 c'est impossible à résoudre. Ce qui signifie que la tâche de calculer la probabilité maximale approximative de gagner est insoluble, tout comme le problème de l'arrêt.

Et cela, à son tour, signifie que la réponse au problème de Zirelson est négative - les deux modèles d'intrication ne sont pas équivalents. S'ils l'étaient, il serait possible de réduire ensemble les limites inférieures et supérieures du score et de calculer la probabilité maximale approximative de gagner.

"Il ne peut pas y avoir un tel algorithme, donc les deux modèles doivent être différents", a déclaré David Perez-Garcia de l'Université Complutense de Madrid.

Le nouveau travail prouve que la classe de problèmes dont les solutions peuvent être confirmées en interagissant avec des prouveurs quantiques intriqués, MIP *, est complètement équivalente à la classe de problèmes qui ne sont pas plus compliqués que le problème d'arrêt, RE. Le titre de l'ouvrage décrit brièvement son essence: «MIP * = RE».

Dans le processus de recherche de preuves de l'égalité des deux classes de complexité, les informaticiens ont prouvé la fausseté de l'hypothèse de Tsirelson, ce qui, grâce aux travaux précédents, signifie la fausseté de l'hypothèse Conn sur l'emboîtement.

Ce fut un choc pour les chercheurs des domaines concernés que les réponses à des problèmes aussi complexes aient été identifiées au cours de preuves apparemment sans rapport avec le domaine de l'informatique.

"Quand j'ai vu un travail appelé MIP * = RE, je ne pensais certainement pas que cela avait quelque chose à voir avec mon travail", a déclaré Navazquez, co-auteur d'un travail précédent reliant l'hypothèse de Cirelson à l'hypothèse de Conn sur l'imbrication. «Cela m'a complètement surpris.»

Les spécialistes de la physique quantique et des mathématiques commencent tout juste à digérer cette information. Auparavant, les mathématiciens se demandaient s'ils pouvaient approximer les matrices de dimension infinie par de grandes matrices finies. Maintenant, connaissant la fausseté de l'hypothèse de Conn de la nidification, ils savent qu'ils ne peuvent pas.

"D'après leur résultat, c'est impossible", a expliqué Slofstra.

Les informaticiens eux-mêmes n'ont pas cherché à confirmer l'hypothèse de Conn sur l'imbrication, alors d'autres personnes devraient plutôt expliquer toutes les conséquences des réponses trouvées.

«Je ne suis pas moi-même mathématicien. Je ne comprends pas très bien la définition initiale de l'hypothèse de Conn au sujet de la nidification », a déclaré Natarajan.

Ils et leurs coauteurs suggèrent que les mathématiciens eux-mêmes traduiront le nouveau résultat dans la langue de leur domaine. Dans un article déclarant des preuves, Vidik a écrit: "Je ne doute pas que la théorie de la complexité ne sera plus nécessaire pour obtenir des résultats purement mathématiques."

Les preuves qui en résultent interrompent la longue chaîne de recherche qui y a conduit. Depuis plus de trois décennies, les informaticiens tentent de savoir jusqu'où mènera leur confirmation interactive. Maintenant, ils ont une réponse sous la forme d'un long travail avec un titre simple et des références à Turing.

"Il y a une assez grande liste d'ouvrages qui ont demandé quelles opportunités pourraient être" dans la procédure de confirmation avec l'aide de deux prouveurs confus, a déclaré Natarajan. «Maintenant, nous savons lesquels. L'histoire est terminée. "

Une preuve significative du théorème de l'informatique capture la physique avec les mathématiques