En 1994, un mathématicien a découvert comment faire faire à un ordinateur quantique quelque chose qu'aucun ordinateur classique ordinaire ne pouvait faire. Les travaux ont révélé qu'en principe, une machine basée sur les règles de la mécanique quantique pourrait diviser efficacement un grand nombre en ses facteurs premiers - une tâche si difficile pour un ordinateur classique qu'elle constitue la base d'une grande partie de la sécurité Internet actuelle.
Une vague d'optimisme a suivi. Peut-être, pensaient les chercheurs, pourrions-nous inventer des algorithmes quantiques capables de résoudre une vaste gamme de problèmes différents.
Mais les progrès ont stagné. "Ça a été une trajectoire un peu décevante", a déclaré Ryan O'Donnell de l'Université Carnegie Mellon. "Les gens disaient : 'C'est incroyable, je suis sûr que nous allons avoir toutes sortes d'autres algorithmes incroyables.' Non." Les scientifiques ont découvert des accélérations spectaculaires uniquement pour une seule classe étroite de problèmes à partir d'un ensemble standard appelé NP, ce qui signifie qu'ils disposaient de solutions efficacement vérifiables, telles que l'affacturage.
Ce fut le cas pendant près de trois décennies. Puis en avril, les chercheurs a inventé un type de problème fondamentalement nouveau qu'un ordinateur quantique devrait être capable de résoudre de manière exponentielle plus rapide qu'un ordinateur classique. Cela implique de calculer les entrées d'un processus mathématique compliqué, basé uniquement sur ses sorties brouillées. Il reste à déterminer si le problème est isolé ou s'il est le premier d'une nouvelle frontière parmi tant d'autres.
"Il y a un sentiment d'excitation", a déclaré Vinod Vaikuntanathan, informaticien au Massachusetts Institute of Technology. "Beaucoup de gens pensent à ce qu'il y a d'autre là-bas."
Les informaticiens tentent de comprendre ce que les ordinateurs quantiques font de mieux en étudiant les modèles mathématiques qui les représentent. Souvent, ils imaginent un modèle d'ordinateur quantique ou classique associé à une machine à calculer idéalisée appelée oracle. Les oracles sont comme de simples fonctions mathématiques ou des programmes informatiques, prenant une entrée et recrachant une sortie prédéterminée. Ils peuvent avoir un comportement aléatoire, indiquant "oui" si l'entrée se situe dans une certaine plage aléatoire (disons, 12 à 67) et "non" si ce n'est pas le cas. Ou ils peuvent être périodiques, de sorte qu'une entrée entre 1 et 10 renvoie « oui », 11 à 20 donne « non », 21 à 30 produit à nouveau « oui », et ainsi de suite.
Disons que vous avez un de ces oracles périodiques et que vous ne connaissez pas la période. Tout ce que vous pouvez faire est de lui donner des chiffres et de voir ce qu'il produit. Avec ces contraintes, à quelle vitesse un ordinateur pourrait-il trouver la période ? En 1993, Daniel Simon, alors à l'Université de Montréal, a découvert qu'un algorithme quantique pouvait calculer la réponse à un problème étroitement lié de manière exponentielle plus rapide que n'importe quel algorithme classique.
Le résultat a permis à Simon de déterminer l'un des premiers indices de la supériorité spectaculaire des ordinateurs quantiques. Mais lorsqu'il a soumis son article à une conférence de premier plan, il a été rejeté. L'article a cependant intéressé un membre junior du comité du programme de la conférence - Pierre Shor, qui était à l'époque aux laboratoires Bell dans le New Jersey. Shor a ensuite découvert qu'il pouvait adapter l'algorithme de Simon pour calculer la période d'un oracle, s'il en avait un. Puis il s'est rendu compte qu'il pouvait adapter l'algorithme une fois de plus, pour résoudre une équation qui se comporte de manière similaire à un oracle périodique : l'équation qui décrit la factorisation, qui est périodique.
Le résultat de Shor était historique. L'algorithme quantique qu'il a découvert pourrait rapidement réduire des nombres gigantesques à leurs facteurs premiers constitutifs, ce qu'aucun algorithme classique connu ne peut faire. Dans les années qui ont suivi, les chercheurs ont découvert d'autres algorithmes quantiques efficaces. Certains d'entre eux, comme l'algorithme de Shor, offraient même un avantage exponentiel, mais personne ne pouvait prouver un avantage quantique spectaculaire sur un problème NP qui n'était pas périodique.
Ce manque de progrès a conduit deux informaticiens, Scott Aaronson de l'Université du Texas, Austin, et Andris Ambainis de l'Université de Lettonie, pour faire une observation. Les preuves de l'avantage quantique semblaient toujours dépendre d'oracles qui avaient une sorte de structure non aléatoire, telle que la périodicité. En 2009, ils conjecturé qu'il ne pouvait pas y avoir d'accélérations spectaculaires sur les problèmes NP aléatoires ou non structurés. Personne n'a pu trouver d'exception.
Leur conjecture a mis une limite aux pouvoirs des ordinateurs quantiques. Mais il disait seulement qu'il n'y avait pas d'accélérations spectaculaires pour un type spécifique de problème NP non structuré - ceux avec des réponses oui ou non. Si un problème impliquait de trouver des réponses quantitatives plus spécifiques, ce que l'on appelle un problème de recherche, la conjecture ne s'appliquait pas.
Dans cet esprit, les chercheurs Takashi Yamakawa des laboratoires d'informatique sociale de NTT et Marc Zhandry de NTT Research et l'Université de Princeton ont décidé d'expérimenter un problème de recherche spécifique, introduit en 2005 par Oded-Regev.
Imaginez un ensemble de girouettes pointant toutes dans la même direction. Donnez à chacun d'eux une poussée mesurée, puis laissez un vent en rafales influencer leur direction. Regev voulait déterminer, sur la base de leurs directions finales, où ils pointaient tous au départ. Des problèmes comme celui-ci ont été appelés "apprentissage avec erreurs", car la poussée et le vent agissent comme une source d'erreur aléatoire sur la direction d'origine. Il est prouvé qu'il est difficile à résoudre pour les algorithmes classiques et quantiques.
Yamakawa et Zhandry ont peaufiné la configuration. Ils ont modifié la force de ces poussées de départ, les rendant plus prévisibles. Ils ont également fait déterminer le vent par un oracle aléatoire afin qu'il soit encore plus aléatoire dans certains cas mais complètement endormi dans d'autres.
Avec ces modifications, les chercheurs ont découvert qu'un algorithme quantique pouvait trouver efficacement la direction initiale. Ils ont également prouvé que tout algorithme classique doit être plus lent d'un facteur exponentiel. Comme Shor, ils ont ensuite adapté leur algorithme pour résoudre une version réelle du problème, qui remplace l'oracle par une véritable équation mathématique.
Les informaticiens travaillent toujours pour comprendre et développer le problème. Vaikuntanathan le compare à un autre qui survient lors de la compression des données : lorsque les informations sont comprimées, deux bits peuvent accidentellement être comprimés au même endroit, les écrasant. Le problème de la prévision de ces collisions à l'avance, afin de pouvoir les éviter, présente une certaine ressemblance. "C'est une classe de problèmes qui ressemblent fondamentalement à ceci", a-t-il déclaré. "Peut-être que ces problèmes peuvent être résolus de manière quantique."
On espérait qu'un problème non structuré comme le nouveau pourrait être résolu même sur les versions naissantes d'ordinateurs quantiques d'aujourd'hui, fournissant ainsi un moyen de les tester. L'idée était que les problèmes non structurés pourraient nécessiter moins de ressources pour être programmés ou être moins sensibles au bruit, car ils sont déjà aléatoires. Mais jusqu'à présent, le nouveau problème semble encore trop avancé pour être résolu par les ordinateurs quantiques existants. « C'est un problème bizarre. Je n'avais pas pensé à le définir », a déclaré Aaronson. "Mais rétrospectivement, il a de très belles fonctionnalités."
Le résultat fournit le premier exemple d'avantage quantique spectaculaire sur un problème NP non structuré. Pourrait-il y avoir beaucoup d'autres problèmes que le monde quantique passe de pratiquement insolubles à solubles ? Il y a maintenant plus de raisons de le penser.
"Cela a quelque peu renversé nos croyances sur les types de problèmes auxquels les ordinateurs quantiques pourraient être bons", a déclaré O'Donnell.
