Cloud
Un ado sème le doute sur l’utilité du quantique
Par Laurent Delattre, publié le 06 août 2018
A 18 ans, il démontre qu’un ordinateur classique peut résoudre un problème de recommandation aussi rapidement qu’un ordinateur quantique…
L’informatique quantique est l’un des grands thèmes de l’année. Nombre d’expérimentations sont en passe de se concrétiser. Google, Intel, IBM et Microsoft investissent des sommes considérables en recherche et développement. Car certains problèmes aux réponses exponentielles ont besoin d’une telle technologie pour aboutir à leurs résultats en un temps humainement et industriellement exploitable. Mais l’un de ces problèmes jugés inaccessibles à l’informatique classique vient, grâce à un jeune mathématicien surdoué, de sortir du champ quantique et trouver une résolution avec nos moyens d’aujourd’hui.
Ce problème n’est autre que celui de la recommandation : des sites comme Amazon ou Netflix proposent à l’utilisateur des recommandations en fonction de ce qu’il a aimé et de ce que les autres utilisateurs ont aussi aimé. La difficulté à fournir de telles recommandations (autrement dit le temps nécessaire pour apporter des réponses) s’accroit exponentiellement avec le nombre d’utilisateurs et le nombre d’objets en vente.
En 2016, Iordanis Kerenidis et Anupam Prakash publièrent un algorithme quantique à même de résoudre les problèmes de recommandation exponentiellement plus rapidement que les algorithmes classiques. Cet algorithme QML (Quantum Machine Learning) est rapidement devenu un exemple typique d’un problème réel justifiant le besoin d’ordinateurs quantiques.
Mais c’était sans compter sur les recherches d’un jeune mathématicien de 18 ans dénommé Ewin Tang qui vient de publier sa thèse. Il y démontre que l’algorithme quantique QML de Kerenidis et Prakash n’apporte aucune accélération exponentielle sur son algorithme classique.
A la rentrée 2017, Edwin Tang s’inscrit aux cours de d’informatique quantique de Scott Aaronson à l’université d’Austin. Aaronson propose à son brillant élève de choisir un sujet de thèse parmi une sélection de différents problèmes. L’un d’eux consistait à démontrer qu’il pouvait exister un algorithme classique rapide pour résoudre les problèmes de recommandation. Tang reconnaît lui-même qu’il a choisi ce sujet parce que, même si le sujet s’avérait indubitablement difficile, il semblait néanmoins être le plus simple de la liste. Pourtant, son professeur lui-même pensait qu’il n’existait effectivement aucun algorithme classique à même de rivaliser avec celui quantique de Kerenidis et Prakash.
Ce qui est intéressant dans la démarche d’Ewin Tang, c’est qu’il s’est directement inspiré du fonctionnement de l’algorithme quantique pour élaborer sa méthode classique. Dans sa thèse, il démontre que les techniques d’échantillonnage quantique employées par Kerenidis et Prakash peuvent être répliquées par une approche classique. Comme l’algorithme QML, celui de Tang s’exécute dans un temps polylogarithmique, se révélant ainsi exponentiellement plus rapide que les algorithmes classiques jusqu’ici utilisés. Dès lors, l’utilité des ordinateurs quantiques pour ces problèmes prend du plomb dans l’aile. Toutefois, l’étudiant reconnaît volontiers qu’il ne serait probablement pas arrivé à ses fins si l’algorithme quantique n’avait pas été préalablement imaginé.
Il ouvre ainsi une nouvelle question : peut-être n’aurons-nous pas autant besoin des ordinateurs quantiques que nous le pensions, mais simplement d’une pensée quantique appliquée aux techniques traditionnelles…
