A 18 ans, il rend obsolète un algorithme quantique
par Bernard Dugué
vendredi 3 août 2018
La technologie offre la possibilité de construire deux catégories de computer, l’un classique, que l’on trouve dans tous les ordinateurs et l’autre, possible ou fantasmé, reposant sur les qbits, autrement dit les bit quantiques faits de superposition d’états et pouvant prendre plusieurs valeurs entre 0 et 1. Alors qu’un computer classique ne connaît que le 0 ou le 1.
Il existe des problèmes que peut résoudre en un temps raisonnable un computer quantique alors qu’un computer classique peut ramer pendant des siècles. L’un des problèmes les plus connus appartenant à la catégorie quantique est celui de la recommandation. Il intéresse de près les géants du Net et l’on comprend pourquoi. A partir des achats effectués, un algorithme permet de calculer vos goûts et vous présenter d’autres produits pouvant vous satisfaire. Amazon pourra vous proposer des livres capables se satisfaire vos préférences connues lors de vos précédents achats, un roman, un essai, un livre sur les champignons… Pareil pour Netflix qui pourra vous proposer un film présentant les motifs et thèmes présents dans ceux que vous avez visionnés.
Les ordinateurs quantiques n’ont pas encore été utilisés à ces fins ; en revanche, des spécialistes ont planché sur les algorithmes car pour résoudre un problème, il faut le coder en algorithme pour que le computer daigne s’y coller. En 2016, deux spécialistes en la matière ont publié un algorithme pour résoudre le problème de la recommandation. Cet algorithme présentant un avantage indéniable et même exponentiel en termes de temps de convergence vers le résultat adéquat. A cette époque, la recommandation était l’un des rares cas dans lesquels le computer quantique l’emporte largement sur son homologue classique.
Or, en 2018, Ewin Tang a habilement montré qu’un algorithme classique pouvait faire aussi bien sinon mieux. Tang s’était intéressé à ce défi en vue de réaliser des travaux pour obtenir un PhD. Son superviseur fut prudent et vérifia si la démonstration tenait la route et pouvait être publiée dans une revue à comité de lecture. Puis il propulsa son brillant élève dans un congrès sur les computers à Berkeley qui eut lieu les 18 et 19 juin 2018. Après sa planche, les participants cogitèrent pour établir un verdict acquis après quatre heures de réflexions. Tang ne s’était pas trompé et ses calculs étaient corrects. Son algorithme classique fait mieux que l’algorithme quantique. Ce qui laisse ouvert le débat sur les avantages du computer quantique.
Un détail étonnant. Les conférenciers ne connaissaient pas l’âge d’Ewin Tang, auteur d’une prestation déjà professionnelle et mature. Tang n’a que 18 ans !
A lire ici