Urmila Mahadev a passé huit ans dans la magistrature à la recherche d'une réponse à l'une des questions les plus fondamentales de l'informatique quantique: comment savons-nous qu'un ordinateur quantique a fait au moins quelque chose au niveau quantique?
Au printemps 2017, Urmila Mahadev était en bonne position, du point de vue de la plupart des étudiants diplômés. Elle vient de résoudre le problème crucial de l'informatique quantique - le domaine de l'informatique, tirant ses capacités des lois étranges de la physique quantique. Avec ses travaux antérieurs, un nouveau résultat de Mahadev décrivant le soi-disant "L'informatique aveugle", a "rendu évident qu'elle était une étoile montante", a déclaré
Scott Aaronson , un spécialiste en informatique à l'Université du Texas à Austin.
Mahadev, qui avait alors 28 ans, était déjà en septième année à l'école doctorale de l'Université de Californie à Berkeley - beaucoup plus longtemps que la plupart des étudiants ne perdent patience et veulent déjà terminer leurs études. Et puis, finalement, elle a pu rédiger une «excellente thèse de doctorat», a déclaré
Umesh Vazirani , son conservateur à Berkeley.
Mais Mahadev n'a pas terminé ses études cette année-là. Elle ne considère même pas cette question. Elle n'a pas encore fini.
Pendant plus de cinq ans, elle a travaillé sur une autre tâche de recherche, que Aaronson a qualifiée de "l'une des questions les plus fondamentales qui peuvent être posées dans le domaine de l'informatique quantique". À savoir: si vous demandez à un ordinateur quantique de faire un calcul pour vous, comment savez-vous s'il suit vos instructions, et en effet, fait-il quelque chose au niveau quantique?
Cette question pourrait bientôt ne plus être purement académique. Les chercheurs espèrent que peu d'années se passeront et que les ordinateurs quantiques seront en mesure d'offrir une accélération exponentielle pour résoudre de nombreux problèmes, de la modélisation d'une situation près d'un trou noir à la simulation du repliement de grandes protéines.
Mais dès qu'un ordinateur quantique peut effectuer des calculs dont le classique n'est pas capable, comment sait-on qu'il les conduit correctement? Si vous ne croyez pas à un ordinateur ordinaire, vous pouvez en théorie étudier attentivement chaque étape de ses calculs vous-même. Mais les ordinateurs quantiques résistent intrinsèquement à de tels contrôles. Pour commencer, leur travail est extrêmement compliqué: pour enregistrer une description de l'état interne d'un ordinateur, composée de seulement quelques centaines de bits quantiques, ou qubits, vous aurez besoin d'un disque dur plus grand que l'Univers observé.
Et même si vous aviez un endroit pour écrire cette description, elle ne pourrait pas être démontée. L'état interne d'un ordinateur quantique est généralement une superposition de nombreux états non pas quantiques, mais classiques (comme le chat Schrödinger, qui est à la fois vivant et mort). Mais dès que vous mesurez un état quantique, il s'effondre immédiatement dans l'un des états classiques. Jetez un œil à l'intérieur d'un ordinateur quantique avec 300 qubits - et vous ne verrez que 300 bits, zéros et uns classiques, vous souriant poliment en retour.
"Un ordinateur quantique est puissant, mais mystérieux", a déclaré Vazirani.
Compte tenu de ces limites, les informaticiens se demandent depuis longtemps si un ordinateur quantique peut fournir une garantie absolument fiable qu'il a vraiment fait ce qu'il prétend être. "L'interaction entre les mondes quantique et classique sera-t-elle suffisamment forte pour permettre un tel dialogue?" Demanda
Dorit Akharonova , informaticienne à l'Université hébraïque de Jérusalem.
Au cours de la deuxième année de la magistrature, Mahadev a été capturée par cette tâche, et elle ne comprend même pas complètement pourquoi. Au cours des années suivantes, elle a essayé d'utiliser une approche pour elle, puis une autre. «J'ai eu beaucoup de ces moments où il m'a semblé que je faisais tout correctement, puis tout s'est cassé - soit très rapidement, soit après un an», a-t-elle déclaré.
Mais elle a refusé d'abandonner. Mahadev a montré un niveau de détermination immuable que Vazirani ne s'était jamais rencontré auparavant. "En ce sens, Urmila est absolument extraordinaire", a-t-il déclaré.
Et maintenant, après huit ans d'études supérieures, Mahadev a réussi. Elle a créé un protocole interactif avec lequel un utilisateur qui n'a pas de capacités quantiques peut néanmoins utiliser une cryptographie pour freiner un ordinateur quantique et le diriger n'importe où, en toute confiance que l'ordinateur quantique obéit aux ordres. L'approche Mahadev, a déclaré Vazirani, donne à l'utilisateur "un levier de pression dont l'ordinateur n'est pas capable de se débarrasser".
"C'est absolument stupéfiant", qu'un étudiant diplômé pourrait atteindre ce résultat seul, a déclaré Aaronson.
Mahadev, maintenant chercheur postdoctoral à Berkeley, a présenté son protocole en octobre 2018 lors du
Symposium annuel
sur l'informatique , l'une des plus grandes conférences informatiques organisées cette année à Paris. Le public a décerné à son travail les prix "meilleur travail" et "meilleur travail étudiant" - un prix rare pour un spécialiste en informatique théorique.
Dans un article de blog,
Thomas Widick , un spécialiste des TI au California Institute of Technology, qui avait travaillé avec Mahadev dans le passé, a décrit son résultat comme «l'une des idées les plus remarquables qui ont surgi à l'intersection de l'informatique quantique et de l'informatique théorique ces dernières années».
Les chercheurs dans le domaine de l'informatique sont ravis non seulement de ce dont le protocole Mahadev est capable, mais aussi d'une approche radicalement nouvelle qui aide à faire face à ce problème. L'utilisation de la cryptographie classique dans le domaine quantique est «une idée vraiment innovante», a écrit Vidik. "Je pense que de nombreux autres résultats se développeront sur ces idées."
Long chemin
Mahadev a grandi à Los Angeles, dans une famille de médecins, et a étudié à l'Université de Californie du Sud, où elle a déménagé d'une région à l'autre, convaincue au départ seulement qu'elle-même ne voulait pas être médecin. Elle s'est ensuite intéressée au cours d'informatique théorique, enseigné par Leonard Aidleman, l'un des créateurs du célèbre algorithme de chiffrement RSA. Elle est entrée à l'université de Berkeley, indiquant dans une note explicative qu'elle était intéressée par tous les aspects de l'informatique théorique - à l'exception de l'informatique quantique.
«C'était quelque chose de complètement étranger auquel j'avais la moindre idée», a-t-elle déclaré.
Mais, une fois à Berkeley, elle a rapidement changé d'avis sous l'influence des explications disponibles de Wazirani. Il l'a initiée à la recherche d'un protocole pour confirmer l'informatique quantique, et cette tâche "a vraiment fait travailler son imagination", a déclaré Vazirani.
"Les protocoles sont comme des énigmes", a expliqué Mahadev. "C'est plus facile pour moi qu'avec d'autres questions, car ici, vous pouvez immédiatement commencer à penser aux protocoles, les diviser en morceaux et regarder comment ils fonctionnent." Elle a choisi cette tâche pour son doctorat, s'engageant sur "un très long chemin", comme l'a dit Vazirani.
Si un ordinateur quantique peut résoudre un problème dont le classique n'est pas capable, cela ne signifie pas automatiquement que la solution sera difficile à vérifier. Prenons, par exemple, le problème de la factorisation de grands nombres - on pense qu'un grand ordinateur quantique peut le résoudre efficacement, mais en même temps il reste au-delà des capacités de n'importe quel ordinateur classique. Mais même si un ordinateur classique n'est pas en mesure de factoriser le nombre, il peut facilement vérifier si le résultat quantique est correct - il suffit de multiplier tous les facteurs et de voir s'ils donnent la bonne réponse.
Cependant, les informaticiens pensent (et ont récemment fait un pas vers la preuve) que de nombreuses tâches qu'un ordinateur quantique pourrait résoudre sont dépourvues d'une telle fonctionnalité. En d'autres termes, un ordinateur classique non seulement ne peut pas les résoudre, il ne peut même pas reconnaître si la solution proposée sera correcte. En conséquence, en 2004,
Daniel Gottsman , physicien théoricien au Waterloo Perimeter Institute, a demandé s'il était possible de trouver un protocole permettant à un ordinateur quantique de prouver à un observateur non quantique qu'il avait réellement accompli ce qu'il prétendait.
Depuis quatre ans, les chercheurs en informatique quantique trouvent une réponse partielle. Deux équipes différentes ont
montré qu'un ordinateur quantique peut prouver ses calculs, mais pas à un vérificateur purement classique, mais à celui qui a accès à un autre ordinateur quantique très petit. Les chercheurs ont ensuite amélioré cette approche en montrant que le testeur n'avait besoin que de la capacité de mesurer l'état d'un qubit à la fois.
Et en 2012, une équipe de chercheurs, dont Vazirani, a montré qu'un vérificateur entièrement classique peut vérifier les calculs quantiques s'ils étaient effectués par une paire d'ordinateurs quantiques qui ne communiquaient pas entre eux. Cependant, leur approche a été spécifiquement conçue pour un tel scénario, et la tâche semble aboutir à une impasse, a déclaré Gottsman. "Je pense qu'il y avait probablement des gens qui pensaient qu'il n'y avait aucun moyen d'aller plus loin."
A cette époque, Mahadev était confronté au problème de confirmation. Au début, elle a essayé de produire un résultat «inconditionnel», sans préciser ce qu'un ordinateur quantique peut et ne peut pas faire. Mais, après avoir travaillé sur la tâche pendant un certain temps sans succès, Vazirani a plutôt proposé la possibilité d'utiliser la cryptographie "post-quantique" - c'est-à-dire la cryptographie, dont la rupture, selon les chercheurs, dépasse les capacités même des ordinateurs quantiques, bien que cela soit sûr ils ne savent pas. (Les méthodes telles que l'algorithme RSA utilisé pour chiffrer les transferts en ligne ne sont pas post-quantiques - un grand ordinateur quantique peut les casser, car leur sécurité est basée sur la difficulté de factoriser de grands nombres).
En 2016, alors qu'ils travaillaient sur une autre tâche, Mahadev et Vazirani ont fait une percée, qui s'avérera décisive à l'avenir. En collaboration avec
Paul Cristiano , spécialiste informatique chez OpenAI, une société basée à San Francisco, ils ont conçu un moyen d'utiliser la cryptographie pour faire passer un ordinateur quantique dans un «état secret» - un état qui est décrit par un vérificateur classique, mais pas par l'ordinateur quantique lui-même. .
Leur procédure est basée sur une fonction de «piège» - facile à exécuter, mais difficile à inverser, à moins que vous n'ayez une clé cryptographique secrète. (À ce moment, les chercheurs ne savaient pas encore comment faire un piège approprié - cela est venu plus tard). La fonction doit également avoir la propriété «deux en un», ce qui signifie que pour chaque ensemble de données de sortie, il existe deux ensembles différents de données d'entrée. Par exemple, nous pouvons imaginer une fonction de mise au carré des nombres - en plus du nombre 0, pour chaque résultat (par exemple, 9) il y a deux nombres d'entrée correspondants (3 et -3).
Armé d'une fonction similaire, vous pouvez faire passer un ordinateur quantique dans un état secret comme suit. Tout d'abord, vous demandez à l'ordinateur la tâche de construire une superposition de toutes les données d'entrée possibles de la fonction (cela peut sembler une tâche difficile pour l'ordinateur, mais en fait c'est simple). Ensuite, vous dites à l'ordinateur d'appliquer la fonction à cette gigantesque superposition, créant un nouvel état qui est une superposition de toutes les sorties possibles de la fonction. Les superpositions d'entrée et de sortie seront confuses, ce qui signifie que la mesure de l'une d'entre elles affectera instantanément l'autre.
Ensuite, vous ordonnez à l'ordinateur de mesurer l'état final et de rapporter le résultat. Une mesure réduit l'état à l'un des ensembles possibles de données de sortie, et l'état d'entrée s'effondre pour y correspondre, car ils sont confus - par exemple, si nous utilisons la fonction carrée, alors si l'état de sortie est 9, l'entrée se repliera à la superposition 3 et -3.
Mais rappelez-vous que nous utilisons une fonction de piège. Nous avons une clé secrète pour le piège, nous pouvons donc facilement trouver les deux états qui composent la superposition d'entrée. Un ordinateur quantique ne peut pas. Et il ne peut pas simplement mesurer la superposition d'entrée pour savoir en quoi elle consiste, car une telle mesure la réduira encore plus, laissant l'ordinateur l'une des deux options, sans la possibilité de calculer l'autre.
En 2017, Mahadev a compris comment créer les fonctions de piège sur lesquelles la méthode de l'état secret est basée à l'aide de la cryptographie appelée
Learning with Errors (LWE). À l'aide de ces fonctions de piège, elle a pu créer une version quantique de l'informatique «aveugle», avec laquelle les utilisateurs de systèmes de cloud computing peuvent cacher leurs données afin que les ordinateurs du cloud ne puissent pas les lire, même s'ils effectuent des calculs avec eux. Peu de temps après, Mahadev, Wazirani et Cristiano se sont associés à Vidik et
Zwika Brackerski (de l'Institut Weizmann en Israël) pour améliorer encore la qualité de ces fonctions et utiliser la méthode de l'état secret pour développer un moyen garanti qu'un ordinateur quantique puisse générer
des nombres prouvés aléatoires .
Mahadev aurait pu déjà obtenir le diplôme sur la base de ces résultats, mais elle avait l'intention de continuer à travailler jusqu'à ce qu'elle ait résolu le problème de confirmation. «Je n'ai jamais pensé à une sortie parce que mon objectif n'était pas du tout une sortie», a-t-elle déclaré.
Parfois, l'incertitude dans la capacité de résoudre ce problème l'a mise sous pression. Mais, a-t-elle dit, "j'ai passé du temps à apprendre des choses qui m'intéressent, donc ce passe-temps ne peut pas être considéré comme un gaspillage."
Sculpté dans la pierre
Mahadev a essayé d'utiliser différentes approches de la méthode de l'état secret pour organiser un protocole de confirmation, mais pendant un certain temps, cela n'a abouti à rien. Et puis une idée lui est venue à l'esprit: les chercheurs avaient déjà montré que le testeur peut vérifier un ordinateur quantique s'il a la capacité de mesurer des bits quantiques. Par définition, le vérificateur classique n'a pas une telle opportunité. Mais que se passerait-il si un testeur classique pouvait en quelque sorte faire en sorte qu'un ordinateur quantique prenne des mesures par lui-même et rende honnêtement ses résultats?
La difficulté sera de savoir comment Mahadev a compris pour faire promettre à l'ordinateur quantique de prendre toute mesure spécifique avant de savoir quelle mesure l'inspecteur lui demandera - sinon, il sera très simple pour l'ordinateur de le tromper. C'est là que la méthode de l'état secret entre en jeu. Le protocole Mahadev nécessite un ordinateur quantique pour créer d'abord un état secret, puis le confondre avec l'état qu'il doit mesurer. Et c'est seulement alors que l'ordinateur sait quelle mesure doit être effectuée.
Puisque l'ordinateur ne connaît pas les détails internes de l'état secret connus de l'inspecteur, Mahadev a montré que l'ordinateur quantique ne pouvait en aucun cas tricher, ne laissant aucun doute à ce sujet. En fait, écrit Vidik, les qubits qu'un ordinateur doit mesurer sont "gravés sur une pierre cryptographique". Par conséquent, si les résultats de la mesure ressemblent à une preuve correcte, l'inspecteur peut être sûr que c'est le cas.
«C'est une si merveilleuse idée! - a écrit Vidik. "Elle me frappe à chaque fois qu'Urmila l'explique."
Le protocole de confirmation de Mahadev - avec un générateur de nombres aléatoires et un chiffrement aveugle - dépend de l'hypothèse que les ordinateurs quantiques ne peuvent pas casser LWE. Jusqu'à présent, LWE est largement considéré comme le principal candidat à la cryptographie post-quantique, et bientôt le National Institute of Standards and Technology peut l'approuver en tant que nouveau standard cryptographique, pour remplacer ceux qui sont susceptibles de se fissurer avec un ordinateur quantique. Mais cela ne garantit pas qu'il est réellement sans danger contre les ordinateurs quantiques, a averti Gottsman. "Mais jusqu'à présent, tout est clair", dit-il. "Personne n'a encore trouvé de preuves de la possibilité de le casser."
En tout cas, la confiance du protocole dans la LWE fait de Mahadev une œuvre gagnante en tout cas, écrit Vidik. La seule façon dont un ordinateur quantique peut tromper le protocole est que quelqu'un du monde de l'informatique quantique trouve comment pirater LWE, ce qui en soi sera une réussite remarquable.
Il est peu probable que le protocole Mahadev soit mis en œuvre sur un véritable ordinateur quantique dans un avenir prévisible. Jusqu'à présent, il a besoin de trop de puissance de calcul d'un point de vue pratique. Mais à l'avenir, cela pourrait changer à mesure que les ordinateurs quantiques se développeront, et les chercheurs rationaliseront ce protocole.
Il est peu probable que le protocole apparaisse dans, disons, les cinq prochaines années, mais «ce n'est pas une telle science-fiction», a déclaré Aaronson. "Sur ce sujet, il sera déjà possible de commencer à penser, si tout se passe comme il se doit, à la prochaine étape du développement des ordinateurs quantiques."
Et, compte tenu de la rapidité avec laquelle ce domaine se développe, cette étape peut commencer plus tôt que prévu. Après tout, il y a seulement cinq ans, a déclaré Vidik, les chercheurs pensaient que tant que les ordinateurs quantiques ne pourraient résoudre aucun problème dont les ordinateurs classiques ne sont pas capables, il faudra encore de nombreuses années. "Et maintenant," a-t-il dit, "les gens croient que cela arrivera dans un an ou deux."
Makhadev, ayant résolu son problème préféré, est restée dans un état quelque peu confus. Mahadev dit qu'elle aimerait comprendre ce qui a rendu ce problème si approprié pour elle. « - , ». , , , , , , .
« , , — . – ».