À 18 ans, il montre qu'un algorithme classique peut être aussi performant qu'un algorithme quantique

Ewin Tang, jeune diplômé en mathématiques et en informatique de l’Université du Texas (Austin), n’a que 18 ans. Mais il est déjà connu pour ses travaux sur les algorithmes. Il est en passe de démontrer que les ordinateurs ordinaires sont capables de résoudre un problème informatique important, qui jusque-là était considéré comme hors de leur portée, avec des performances potentiellement comparables à celles d’un ordinateur quantique.

Ce problème concernait les algorithmes de filtrage et de recommandation qui sont en général utilisés par les plateformes de vente en ligne comme Amazon, eBay ou Netflix afin de déterminer et suggérer aux consommateurs des produits qu’ils sont susceptibles d’apprécier en se basant sur leurs choix antérieurs et sur ceux des autres clients ou groupes de personnes.

En 2016, Iordanis Kerenidis et Anupam Prakash, deux chercheurs en informatique, ont publié un algorithme quantique qui résolvait le problème de la recommandation de façon exponentiellement plus rapide que tous les algorithmes classiques connus. De ce fait, les informaticiens considéraient ce problème comme l’un des meilleurs cas justifiant la théorie de la suprématie quantique attestant que pour la résolution de problèmes bien spécifiques, il peut être plus efficace, voire même indispensable, de disposer d’un système de calcul quantique, plutôt que d’un ordinateur traditionnel.

Mathématiquement, il existe de nombreuses manières de déterminer les utilisateurs les plus proches et de prédire des notes. La représentation usuelle repose sur une matrice sur laquelle chaque ligne correspond à un utilisateur et chaque colonne à un produit. En outre, chaque case de la matrice de coordonnées (i, j) contient la note que l’utilisateur « ;i ;» a attribué à l’objet « ;j ;».


Au lieu de remplir toute la matrice et d’identifier le meilleur produit à recommander, Kerenidis et Prakash ont développé un moyen de classer les utilisateurs dans un petit nombre de catégories (préfèrent-ils ceci ou cela ;?) et d’échantillonner les données existantes afin de générer une recommandation suffisamment bonne.

Kerenidis et Prakash ont certes démontré la suprématie quantique dans le cadre de la résolution du problème de recommandation, ils n’ont cependant pas prouvé qu’un algorithme classique tout aussi performant ne pouvait exister.

Au printemps 2017, Tang a suivi un cours sur l’informatique quantique dispensé par Scott Aaronson, éminent chercheur en informatique quantique. Ce dernier a fini par devenir le conseiller de Tang sur un projet de recherche indépendant qui tournait autour des algorithmes de recommandation. Dans le cadre de ce projet, ils se sont donné pour mission d’appuyer les résultats obtenus par Kerenidis et Prakash en démontrant de leur côté qu’il n’existe pas d’algorithme de recommandation classique qui pourrait être aussi performant que son homologue quantique.

Malgré son scepticisme au départ, Tang a commencé à penser qu'un tel algorithme était possible après tout : « ;J’ai commencé à croire qu’il existait un algorithme classique rapide, mais je ne pouvais pas vraiment le prouver parce que Scott semblait penser qu’il n’y en avait pas, et qu’il avait le dernier mot ;», a dit Tang. Il s’est ensuite employé à démontrer son point de vue à Aaronson qui a fini par le soutenir dans son entreprise.


L’algorithme classique élaboré par Tang qui offrait des performances comparables à son homologue quantique était directement inspiré de l’algorithme quantique mis au point par Kerenidis et Prakash deux ans plus tôt. Tang a brillamment montré que la technique d’échantillonnage quantique utilisée par ses prédécesseurs pouvait être reproduite dans un cadre classique.

Ces deux algorithmes fonctionnent en temps polylogarithmique, le temps de calcul proportionnel au logarithme des caractéristiques comme le nombre d’utilisateurs et de produits dans l’ensemble des données, et sont exponentiellement plus rapide que tous les algorithmes classiques antérieurement connus.

Lors d’un atelier sur l’informatique quantique organisé à l’Université de Californie, à Berkeley, en juin dernier, Aaronson a introduit Tang et les résultats de ses travaux auprès d’éminents chercheurs qui participaient à l’évènement, y compris Kerenidis et Prakash. Tang a d’abord présenté son algorithme de manière informelle dans les jours suivant la fin de la conférence officielle. Les 18 et 19 juin, il a donné deux conférences, tout en répondant aux questions du public. Un consensus s’est finalement dégagé : l’algorithme classique de Tang semblait correct et fait désormais l’objet d’un examen formel par les pairs avant sa publication.

L’expérience de Tang est une preuve supplémentaire de l’interaction fructueuse entre l’étude des algorithmes quantiques et classiques. Elle encourage l’idée selon laquelle le fossé séparant ces deux univers n’est peut-être pas aussi grand qu’il n'y parait.

Source : Quanta Magazine, Cornell University Library

Et vous ?

Qu’en pensez-vous ?

Voir aussi

Des chercheurs de Harvard ont créé un nouvel algorithme d'optimisation qui augmente de manière exponentielle la vitesse de calcul des ordinateurs

Une équipe de scientifiques russo-américaine présente le premier ordinateur quantique à 51 qubits, il dépasse largement les prototypes précédents

Une puce quantique photonique de 49 qubits et une nouvelle solution pour booster la puissance des systèmes de calcul quantique analogiques

Chiffrement quantique : des chercheurs créent un système de distribution de clés quantiques jusqu'à dix fois plus performant que tous les précédents