L'univers des tâches contrôlées par ordinateur s'est élargi. Grâce à quel ingrédient secret est-ce arrivé? En raison de l'intrication quantique.
Imaginez que quelqu'un vienne à vous et vous dise qu'il a un oracle qui peut révéler les secrets secrets de l'univers. Cela pourrait vous intéresser, mais il vous serait difficile de le croire. Vous aimeriez trouver un moyen de confirmer que l'oracle dit la vérité.
C'est le principal problème de l'informatique. Certaines tâches sont trop difficiles à résoudre dans un délai raisonnable. Mais leurs décisions sont faciles à vérifier. Compte tenu de cela, les informaticiens veulent savoir: quelle est la complexité d'une tâche, dont la solution peut encore être vérifiée?
Il s'avère que la réponse à cette question est: presque inimaginablement complexe.
Dans un
article paru en avril 2019, deux spécialistes en informatique ont radicalement augmenté le nombre de tâches entrant dans la catégorie des «difficiles à résoudre, faciles à vérifier». Ils décrivent une méthode qui permet de vérifier des solutions à des problèmes d'une complexité presque incompréhensible. "Cela semble fou", a déclaré Thomas Widick, un informaticien du California Institute of Technology qui n'est pas impliqué dans ce travail.
L'étude est applicable aux ordinateurs quantiques effectuant des calculs selon les règles non intuitives de la mécanique quantique. Les ordinateurs quantiques sont à peine apparus, mais à l'avenir ils ont le potentiel de révolutionner l'informatique.
Le nouveau travail, en fait, nous donne un effet de levier sur cet oracle tout-puissant. Même si l'oracle promet de vous fournir des solutions toutes faites à des problèmes dont les possibilités de solution sont bien au-delà de vos capacités, il reste encore un moyen de vérifier si l'oracle dit la vérité.
Jusqu'au bout de l'univers
Lorsqu'un problème est difficile à résoudre, mais facile à vérifier, la recherche d'une solution prend beaucoup de temps, mais pas la vérification de l'exactitude d'une solution particulière. Par exemple, supposons qu'une personne vous montre un graphique - un ensemble de points (sommets) reliés par des lignes (arêtes). Une personne demande s'il est possible de colorer les sommets du graphique avec trois couleurs de sorte qu'il n'y ait pas deux sommets connectés ayant la même couleur.
La tâche des trois couleurs est difficile à résoudre. Dans le cas général, le temps nécessaire pour rechercher la coloration des sommets (ou pour déterminer qu'une telle coloration n'existe pas) augmente de façon exponentielle avec l'augmentation de la taille du graphique. Si, par exemple, la recherche d'une solution pour un graphe à 20 sommets prend 3 à
20 ns - c'est-à-dire quelques secondes, alors pour un graphe à 60 sommets cela prendra 3
60 ns, soit 100 fois l'âge actuel de l'Univers.
Mais disons que quelqu'un prétend avoir peint le comte avec trois couleurs. La vérification de cette application ne prendra pas beaucoup de temps. Il vous suffit de faire le tour de tous les sommets un par un, en étudiant les sommets qui leur sont associés. À mesure que la taille du graphique augmente, le temps de cette vérification augmente lentement - en tant que
polynôme . Par conséquent, un ordinateur ne prend pas beaucoup plus de temps pour vérifier la coloration d'un graphique de 60 sommets que pour vérifier un graphique de 20 sommets.
"Avec la bonne couleur en trois couleurs, il est facile de tester ses performances", a déclaré
John Wright , physicien au Massachusetts Institute of Technology, qui a écrit ce travail avec
Anand Natarajan de Caltech.
Dans les années 1970, les informaticiens ont déterminé une classe de tâches faciles à vérifier, même si certaines d'entre elles sont difficiles à résoudre. Ils ont appelé cette classe NP, le
temps polynomial non déterministe . Depuis, en informatique, la classe NP a été étudiée plus que d'autres. En particulier, les informaticiens aimeraient savoir comment cette classe change lorsque l'algorithme de test reçoit de nouvelles façons de vérifier l'exactitude de la solution.
Les bonnes questions
Avant les travaux de Natarajan et Wright, la puissance des inspections a augmenté en deux grands bonds.
Pour comprendre la première, imaginez que vous ne faites pas de distinction entre les couleurs. Quelqu'un place deux cubes sur la table devant vous et demande s'ils sont de la même couleur ou différents. Cette tâche vous est impossible. De plus, vous ne pouvez pas confirmer l'exactitude de la solution de quelqu'un d'autre à ce problème.
Cependant, vous êtes autorisé à poser des questions à cette personne qui a fait ses preuves. Supposons que le prouveur vous dise que les cubes sont de couleurs différentes. Vous appelez l'un d'eux "Cube A" et l'autre "Cube B". Ensuite, vous les cachez derrière votre dos et échangez accidentellement des endroits entre eux. Ensuite, vous ouvrez les cubes et demandez au prouveur de trouver le dé A.
Si les cubes sont de couleurs différentes, c'est une question très simple. Le prouveur reconnaîtra le cube A, s'il s'agit, par exemple, d'un cube rouge, et le déterminera correctement à chaque fois.
Cependant, si les cubes sont de la même couleur - et le prouveur s'est trompé en les appelant différents - le prouveur ne peut que deviner lequel est lequel. Par conséquent, il ne pourra déterminer correctement le Cube A que dans 50% des cas. En interrogeant constamment le prouveur sur sa décision, vous pouvez confirmer si elle est correcte.
Anand Natarajan et John Wright"L'examinateur peut envoyer des questions au prouveur", a déclaré Wright, "et peut-être qu'à la fin de la conversation, l'examinateur sera plus convaincu de la réponse."
En 1985, trois informaticiens ont prouvé que de telles preuves interactives pouvaient être utilisées pour confirmer des solutions à des problèmes plus complexes que des problèmes de NP. Leur travail a créé une nouvelle classe de tâches, IP, «temps polynomial interactif». La méthode utilisée pour confirmer les couleurs des cubes peut être utilisée pour confirmer les réponses à des questions beaucoup plus complexes.
La deuxième percée s'est produite au cours de la même décennie. Cela ressemble à la logique d'une enquête policière. Si vous avez deux suspects qui ont commis, à votre avis, un crime, vous ne les interrogerez pas ensemble. Vous les interrogerez dans différentes pièces, et vous comparerez les réponses de l'une avec les réponses de l'autre. En les interrogeant individuellement, vous pouvez révéler plus de vérité que si vous aviez un suspect.
"Les deux suspects ne seront pas en mesure de créer une histoire cohérente distribuée, car ils ne savent pas quelles sont les autres réponses", a déclaré Wright.
En 1988, quatre informaticiens ont prouvé que si vous demandez à deux ordinateurs de résoudre le même problème séparément et que vous les questionnez séparément, vous pouvez confirmer une classe de problèmes encore plus importante que l'IP: la classe MIP, des preuves interactives avec beaucoup de preuves.
En utilisant cette approche, il est possible, par exemple, de confirmer l'exactitude de la coloration d'un graphique en trois couleurs pour une séquence de graphiques dont la taille augmente beaucoup plus rapidement que les graphiques de NP. Dans NP, la taille des graphiques augmente de façon linéaire - le nombre de sommets peut passer de 1 à 2, jusqu'à 3, jusqu'à 4, etc. - de sorte que la taille du graphique n'est pas disproportionnellement supérieure à la durée nécessaire pour vérifier la coloration. Mais dans MIP, le nombre de sommets de graphe croît exponentiellement de 2
1 à 2
2 , 2
3 , 2
4 , etc.
En conséquence, les graphiques s'avèrent être trop volumineux, même pour tenir dans la mémoire de l'ordinateur, qui doit parcourir la liste des sommets et vérifier la coloration. Cependant, la coloration peut toujours être vérifiée en posant des questions aux deux étalons différentes mais liées.
Dans MIP, le testeur a suffisamment de mémoire pour exécuter un programme qui nous permet de déterminer si deux sommets du graphique sont connectés par un bord - et il peut vérifier les réponses des testeurs pour s'assurer que la coloration est correcte.
Élargir la liste des tâches difficiles à résoudre mais faciles à vérifier, des ordinateurs classiques au NP en passant par IP et MIP. Mais les ordinateurs quantiques fonctionnent très différemment. Et pendant plusieurs décennies, il n'était pas clair comment leur utilisation change cette image - est-il plus facile ou plus difficile de vérifier les solutions avec leur aide?
Le nouveau travail de Natarajan et Wright a la réponse à cette question.
Astuces quantiques
Les ordinateurs quantiques effectuent des calculs utilisant des bits quantiques, ou qubits. Ils ont une propriété telle que l'
enchevêtrement les uns avec les autres. Et lorsque deux qubits - ou même de grands systèmes de qubit - sont confondus, cela signifie que leurs propriétés physiques d'une certaine manière s'influencent mutuellement.
Dans leur nouveau travail, Natarajan et Wright envisagent un scénario qui inclut deux ordinateurs quantiques différents, avec les qubits de l'un confondus avec les qubits de l'autre.
Il semblerait qu'une telle configuration aggrave la qualité de la vérification des réponses. La pleine puissance des preuves interactives avec de nombreux prouveurs découle précisément du fait que vous pouvez interroger deux prouveurs séparément et vérifier leurs réponses. Si les réponses des prouveurs sont les mêmes, alors elles sont probablement vraies. Mais si les états quantiques de deux prouveurs sont confus, ils semblent avoir plus d'occasions d'insister constamment sur l'exactitude des réponses incorrectes.
En effet, lorsque le scénario avec deux ordinateurs quantiques intriqués a été
dévoilé pour la première
fois en 2003, les informaticiens ont suggéré que l'intrication réduirait la possibilité de vérification. "La réaction évidente de tout le monde, y compris la mienne, a été que les justificatifs dans ce cas avaient plus d'opportunités", a déclaré Vidik. «Ils peuvent utiliser la confusion pour lier leurs réponses.»
Mais, malgré le pessimisme initial, Vidik a passé plusieurs années à essayer de prouver le contraire. En 2012, lui et
Tsuyoshi Ito ont prouvé qu'il était possible de tester toutes les tâches du MIP à l'aide d'ordinateurs quantiques enchevêtrés.
Maintenant, Natarajan et Wright ont prouvé que la situation est encore meilleure: avec l'aide de la complexité, on peut prouver une classe de problèmes encore plus grande que sans elle. Il est possible d'inverser la connexion entre les ordinateurs quantiques intriqués au profit du vérificateur.
Pour comprendre comment procéder, rappelez la procédure du MIP pour vérifier la coloration des graphiques dont la taille croît de façon exponentielle. Le testeur n'a pas assez de mémoire pour stocker le graphique entier, mais il a suffisamment de mémoire pour déterminer deux sommets connectés et pour poser aux testeurs une question sur la couleur de ces sommets.
Dans la classe de problèmes considérée par Natarajan et Wright - appelée NEEXP, un temps non déterministe deux fois exponentiel - la taille des graphiques croît encore plus rapidement que dans MIP. Les graphiques dans NEEXP croissent au "double taux exponentiel". Au lieu de croître en degrés de deux - 2
1 , 2
2 , 2
3 , 2
4 , etc. - le nombre de sommets dans les graphiques augmente en degrés de deux - 2
2 1 , 2
2 2 , 2
2 3 , 2
2 4 , et ainsi de suite. En conséquence, les graphiques s'avèrent rapidement si énormes que l'inspecteur n'est même plus en mesure de trouver une paire de sommets connectés.
"Pour identifier le sommet, 2
n bits sont nécessaires, ce qui est exponentiellement plus que le vérificateur n'a en mémoire", a déclaré Natarajan. Cependant, Natarajan et Wright ont prouvé qu'il est possible de vérifier la coloration d'un graphe à double exponentielle en trois couleurs, même sans pouvoir déterminer quels sommets doivent être demandés. Le fait est que vous pouvez faire en sorte que les assistants choisissent eux-mêmes les bonnes questions.
L'idée d'amener les ordinateurs à s'interroger sur leurs propres décisions semble aussi raisonnable pour les informaticiens que demander aux criminels présumés de s'interroger est certainement une proposition stupide. C'est juste que Natarajan et Wright ont prouvé que ce n'était pas le cas. Et la raison en est la confusion.
"Les États enchevêtrés sont des ressources partagées", a déclaré Wright. «Tout notre protocole consiste à comprendre comment utiliser cette ressource partagée pour créer des problèmes interconnectés.»
Si les ordinateurs quantiques sont confus, leur choix de sommets sera corrélé et donnera juste le bon ensemble de questions pour vérifier la coloration en trois couleurs.
Dans le même temps, l'inspecteur n'a pas besoin que les deux ordinateurs quantiques soient entrelacés pour que leurs réponses à ces questions soient corrélées l'une à l'autre (ce serait similaire à la façon dont deux criminels présumés corrèlent leur faux alibi). Une autre caractéristique quantique étrange traite de ce problème. En mécanique quantique,
le principe d'incertitude nous interdit de connaître l'emplacement et le moment exact d'une particule en même temps - si vous mesurez une propriété, vous détruisez des informations sur une autre. Le principe d'incertitude limite considérablement votre connaissance de deux propriétés «complémentaires» d'un système quantique.
Natarajan et Wright l'utilisent dans leur travail. Pour calculer la couleur du sommet, ils forcent deux ordinateurs quantiques à prendre des mesures complémentaires. Chaque ordinateur calcule la couleur de son propre sommet et détruit ainsi toutes les informations sur l'autre. En d'autres termes, la confusion permet aux ordinateurs de poser des questions corrélatives, mais le principe d'incertitude leur interdit de conspirer pour y répondre.
"Nous devons faire oublier les prouveurs, et c'est la principale chose que Natarajan et Wright ont faite dans leur travail", a déclaré Vidik. «Ils forcent le prouveur à effacer les informations grâce à la mesure.»
Les conséquences de leur travail peuvent être qualifiées de quasi existentielles. Avant la publication des travaux, la limitation des connaissances que nous pouvons obtenir en toute confiance était bien moindre. Si on nous donnait une réponse à un problème de l'ensemble du NEEXP, nous n'aurions qu'à l'accepter de foi. Mais Natarajan et Wright ont dépassé ces limites et ont permis de confirmer les réponses d'un univers beaucoup plus vaste de problèmes de calcul.
Et maintenant qu'ils l'ont fait, il n'est pas clair où se situe la prochaine limite de vérifiabilité. «Cela pourrait aller beaucoup plus loin», a déclaré Lance Fortnau, spécialiste informatique au Georgia Institute of Technology. "Ils laissent l'opportunité de passer à l'étape suivante."