Vous entrez dans une grotte. Au bout d'un couloir sombre, vous rencontrez une paire de chambres scellées. À l'intérieur de chaque chambre se trouve un sorcier omniscient. La prophétie dit qu'avec l'aide de ces oracles, vous pouvez apprendre les réponses aux problèmes sans réponse. Mais il y a un hic: les oracles ne disent pas toujours la vérité. Et bien qu'ils ne puissent pas communiquer entre eux, leurs réponses apparemment aléatoires à vos questions sont en fait liées par le tissu même de l'univers. Pour obtenir la réponse que vous cherchez, vous devez d'abord concevoir … les questions.
Les informaticiens bourdonnent à propos d'une nouvelle preuve mathématique qui propose un système enchevêtré quantique un peu comme celui décrit ci-dessus. Il semble réfuter une Conjecture de 44 ans et détaille une machine théorique capable de résoudre le fameux problème d'arrêt, qui dit qu'un ordinateur ne peut pas déterminer s'il sera jamais en mesure de résoudre un problème qu'il essaie actuellement de résoudre.
le Épreuve de 150 pages, intitulé simplement «MIP * = RE», traite du sujet ésotérique de la complexité informatique. S'il est sous surveillance, il démontre un lien profond entre la physique quantique, le calcul et les mathématiques. Il montre qu'une classe théorique de dispositifs informatiques – un vérificateur interrogeant les oracles enchevêtrés quantiques – peut vérifier certains des problèmes informatiques les plus complexes imaginables.
Sur le côté gauche du signe égal se trouve la classe de calcul théorique MIP *. Les chercheurs depuis les années 1980 ont analysé une classe de problèmes appelée IP, ou temps polynomial interactif, une liste de problèmes pouvant être résolus par des preuves interactives. Il s'agit d'une sorte de preuve dans laquelle un vérificateur (un ordinateur ordinaire qui résout essentiellement les problèmes en retournant des pièces, c'est-à-dire en utilisant des bits) essaie de vérifier si une réponse est correcte. Pour ce faire, il peut poser des questions à un observateur omniscient mais pas nécessairement honnête, appelé le prouveur.
Si vous connaissez les classes de complexité, vous avez peut-être entendu parler de P, une catégorie de problèmes pouvant être résolus en temps polynomial, ce qui signifie une quantité de temps égale à la taille de l'entrée élevée à un exposant constant (n'importe quel nombre). Ensuite, il y a les problèmes NP, ceux pour lesquels on ne sait pas combien de temps il faudra pour résoudre le problème, mais étant donné une solution potentielle, il ne faut que du temps polynomial pour vérifier cette solution. Un exemple célèbre d'un problème de NP est le problème de coloration des graphes: Étant donné une série de points reliés par des lignes (que les mathématiciens appellent un graphique), comment utilisez-vous trois couleurs pour peindre les points de telle sorte qu'aucune couleur ne se touche? Des chercheurs des années 1980 et du début des années 1990 ont montré que ces preuves interactives peuvent vérifier tous les problèmes de NP ainsi qu'un ensemble au moins aussi compliqué de problèmes qui peuvent être résolus en utilisant une quantité de mémoire polynomiale.
D'autres chercheurs ont élargi la classe de problèmes pouvant être résolus avec une preuve interactive dans la classe MIP: que se passerait-il si le vérificateur était capable de poser des questions à une paire de prouveurs omniscients mais pas nécessairement honnêtes, comme une paire de suspects criminels séparés dans des pièces insonorisées? Un tel système de vérification peut vérifier efficacement des problèmes encore plus difficiles, tels que le temps nécessaire pour vérifier augmente de façon exponentielle avec la taille de l'entrée, comme un graphique en trois couleurs de plus en plus exponentiellement.
Maintenant, les chercheurs explorent une classe encore plus puissante, appelée MIP *. Dans ce cas, imaginez la même paire d'oracles omniscients assis dans des pièces séparées, mais ils sont empêtrés via les règles de la mécanique quantique. La mécanique quantique est le système mathématique qui décrit la façon dont les particules subatomiques interagissent, mais ses mathématiques ressemblent à une version plus complexe de la probabilité. Enchevêtrer les prouveurs dit que bien qu'ils soient séparés, les choses qui peuvent sembler aléatoires lorsque vous parlez à un seul prouveur sont en fait corrélées entre les deux.
Ouf, donc, pour revoir: MIP est une sorte de système de preuve hypothétique où un compu régulierter demande questions de deux "oracles" omniscients mais pas nécessairement honnêtes qui ne peuvent pas communiquer entre eux. Ce type de système de preuve peut vérifier efficacement les réponses à des problèmes extrêmement complexes problèmes. Les scientifiques tentent maintenant devoyez à quel point cette méthode de preuve serait puissante quand ils étendent MIP à MIP * – les oracles ne peuvent toujours pas communiquer, mais ils sont maintenant quantiques empêtré, donc les réponses qu'ils fournissent sont plus corrélées qu'elles ne le seraient autrement.
Un chercheur de CalTech, Anand Natarajan, a déjà entendu un jour un informaticien Scott Aaronson donner des cours sur le MIP * et s'est rendu compte que la classe était étonnamment méconnue. "C'était l'une de ces rares situations dans la théorie de la complexité où vous avez un large éventail de possibilités de ce que la vérité peut être réellement", a déclaré Natarajan, l'un des auteurs de l'étude, à Gizmodo. Le chercheur du MIT, John Wright, a expliqué à Gizmodo qu'il y avait déjà des définitions pour IP et MIP – et maintenant c'était à eux de comprendre MIP *.
"Il s'agit d'une déclaration fondamentale qui, en fait, nous ne pouvons vraiment pas connaître la réponse à certaines choses."
L'année dernière, Wright et Natarajan ont rédigé une preuve montrant que la connexion fantasmagorique dans la classe MIP * donne au vérificateur interrogeant les prouveurs enchevêtrés le pouvoir de vérifier des problèmes encore plus difficiles (ceux dont la complexité augmente de façon exponentielle avec la taille de l'entrée). L'enchevêtrement supplémentaire donne plus de connaissances au vérificateur pour poser de meilleures questions aux prouveurs (les oracles). Pendant ce temps, un autre principe de la mécanique quantique, le principe d’incertitude, brouille les mesures des prouveurs à chaque fois que le vérificateur demande une des deux propriétés complémentaires, ce qui rend difficile pour eux de tromper le vérificateur.
Ces travaux de Wright, Natarajan, Zhengfeng Ji de l'Université de technologie de Sydney, Thomas Vidick de CalTech et Henry Yuen de l'Université de Toronto, ont prouvé que la puissance de la classe MIP * éclipse l'épreuve de l'an dernier. Ils postulent que MIP * pourrait vérifier efficacement tous les problèmes de la «classe récursivement énumérable» ou RE, essentiellement tous les problèmes pour lesquels il faudrait un temps limité pour calculer si la réponse était «oui»; une réponse «non» pourrait prendre un temps infini pour calculer. MIP * = RE.
Fondamentalement, ce dispositif MIP * théorique peut résoudre de nombreux problèmes très complexes, y compris le fameux problème d'arrêt, où un ordinateur est demandé si un programme en cours d'exécution se terminera jamais, a déclaré Wright. La preuve MIP * = RE a des implications importantes en mathématiques et en physique.
"En bref, je pense que c'est un résultat remarquable", a déclaré à Gizmodo Bill Fefferman, professeur adjoint en informatique à l'Université de Chicago, non impliqué dans l'étude. «Ce résultat est un excellent exemple de la façon dont les outils de la communauté de l'information quantique peuvent être utiles dans de vastes domaines scientifiques et conduire à des solutions dans ce qui semble être des domaines complètement distincts. C’est pourquoi je suis le plus enthousiasmé par ce résultat. "
La preuve à elle seule fait une déclaration importante sur tout ce que vous pouvez savoir en mécanique quantique, a déclaré à Gizmodo Stephanie Wehner, professeur en information quantique à l'Université de technologie de Delft. Les scientifiques se sont demandé à quel point la corrélation entre les systèmes quantiques intriqués peut être forte au sens le plus général. Mais comme effet secondaire de la machinerie de la preuve et de la relation entre les oracles et le vérificateur, il s'avère que cette question est incalculable.
"Il s'agit d'une déclaration fondamentale qui, en fait, nous ne pouvons vraiment pas connaître la réponse à certaines choses", a déclaré Wehner à Gizmodo. "C'est ce que je trouve personnellement intéressant à propos de cette preuve."
UNEs un sous-produit de cette incalculabilité, la preuve géante réfute une conjecture de 44 ans en algèbre abstraite appelée conjecture d'intégration de Connes, une déclaration mathématique ésotérique qui s'est avérée être logiquement équivalente à d'autres déclarations dans d'autres sujets mathématiques et physiques. Beaucoup de gens ont espéré que la conjecture de Connes serait vraie, a déclaré le physicien du MIT, Aram Harrow, à Gizmodo, car cela prouverait un certain nombre de faits et d'outils utiles pour les mathématiciens du monde entier. Pour les physiciens en particulier, prouver que la conjecture d'intégration de Connes est erronée signifie que deux objets mathématiques distincts autrefois considérés comme équivalents dans la façon dont ils peuvent expliquer la mesure des systèmes enchevêtrés ne sont en fait pas équivalents. Certaines approximations des systèmes infinis aux systèmes finis ne fonctionnent plus, comme les physiciens le supposaient autrefois.
Ce n'est pas un véritable appareil qui existera jamais – vous ne pouvez pas relier ensemble des oracles omniscients, ni un oracle omniscient. Mais les chercheurs utilisent ces scénarios abstraits pour comprendre les véritables limites de ce que les ordinateurs peuvent et ne peuvent pas faire. Peut-être que des versions simplifiées des oracles, comme des ordinateurs enchevêtrés qui dépendent des mathématiques de la mécanique quantique pour effectuer leurs calculs, pourraient avoir un pouvoir au-delà de ce que les physiciens attendaient auparavant.
Wright a averti que les examinateurs n'avaient pas encore tenté de vérifier le travail présenté dans la preuve, et qu'un long processus d'examen par d'autres mathématiciens devait encore suivre. Ils espèrent que c'est correct.
GIPHY App Key not set. Please check settings