À 18 ans, il montre qu'un algorithme classique peut être aussi performant qu'un algorithme quantique
Et relance le débat sur la suprématie quantique

Le , par Christian Olivier, Chroniqueur Actualités
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


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse Signaler un problème

Avatar de tmcuh tmcuh - Membre du Club https://www.developpez.com
le 01/08/2018 à 13:50
Je pense qu'il faut toujours du sang frais pour faire avancer la science.
On le voit souvent dans l'analyse, un regard extérieur est toujours différent, même si on tend à prouver que ce qu'on dit est juste, il existe d'autres pistes qui peuvent donner lieu au même résultat.
Il y a fort à parier qu'il ira loin ce "petit"
Avatar de Matthieu76 Matthieu76 - Membre éclairé https://www.developpez.com
le 01/08/2018 à 13:57
Personnellement, je ne vois toujours pas ce qu'un algorithme quantique à de plus qu'un algorithme classique.
Avatar de Olomius Olomius - Membre à l'essai https://www.developpez.com
le 01/08/2018 à 14:12
Et les autres problématiques (diversité (pour un utilisateur, ou pour l'ensemble des utilisateurs), nouvel utilisateur, ...) ?
Avatar de Anselme45 Anselme45 - Membre éprouvé https://www.developpez.com
le 01/08/2018 à 14:33
Citation Envoyé par Matthieu76 Voir le message
Personnellement, je ne vois toujours pas ce qu'un algorithme quantique à de plus qu'un algorithme classique.
Le Buzz, mon ami... Le Buzz!

Il va du "quantique" comme de l'intelligence artificielle (IA) ou du BlockChain... Tu peux l'appliquer à n'importe quoi, même aux couches culottes de ton petit dernier, cela ne serre pas toujours à quelque chose, mais cela fait toujours parler de toi...
Avatar de Juniper62 Juniper62 - Membre à l'essai https://www.developpez.com
le 01/08/2018 à 15:18
c'est n'importe quoi, la suprématie du calcul quantique a largement été prouver pour les énormes calcul ... mais en effet pour les petites opérations à la cons, le gain est négligeable et peut-être même qu'il n'y a pas de gain du tout, voir de la perte ...
un peu comme en informatique avec le ++ avant ou après l'entité à incrémenter ... sur les types primitifs, il y a perte de temps mais sur les objets + importants, le gain en se passant de la copie n'est même pas discutable ...
en effet, à l'instar de l'IA ...

bref ce petit c** a voulu faire le buzz et vous avez marché dedans, vous avez même couru ...
Avatar de Juniper62 Juniper62 - Membre à l'essai https://www.developpez.com
le 01/08/2018 à 15:19
Citation Envoyé par Matthieu76 Voir le message
Personnellement, je ne vois toujours pas ce qu'un algorithme quantique à de plus qu'un algorithme classique.
c'est très certainement parce que la mécanique quantique n'est pas abordable pour le 1er péquenaud venu ...
Avatar de onilink_ onilink_ - Membre éprouvé https://www.developpez.com
le 01/08/2018 à 16:11
Citation Envoyé par Matthieu76 Voir le message
Personnellement, je ne vois toujours pas ce qu'un algorithme quantique à de plus qu'un algorithme classique.
Eh bien il s'agit d'un paradigme différent, qui permet de faire des choses différentes, tout simplement.

Tu devrais regarder l'algorithme quantique le plus connu, l'algorithme de Shor:
https://fr.wikipedia.org/wiki/Algorithme_de_Shor

Alors bien sur, on peut simuler un algorithme quantique sur une machine classique, mais la différence c'est que ça va coûter très cher en performance, et n'apportera alors aucun intérêt.
Sur un ordinateur quantique en revanche, l'algorithme de Shor permettra de factoriser des nombres bi-premiers très rapidement, avec une complexité algorithmique totalement différente de celle avec un algorithme classique.

Citation Envoyé par Juniper62 Voir le message
bref ce petit c** a voulu faire le buzz et vous avez marché dedans, vous avez même couru ...
Non, c'est le titre qui est tendancieux. Cet étudiant a réussi a faire un algorithme classique aussi performant qu'un algorithme quantique pour une même tâche, ce qui est quand même très intéressant.
Cela ne veut pas dire qu'il est possible de faire de même pour tous les algorithmes quantiques, loin de la... car si c'était le cas on aurait déjà de gros problème avec les algorithmes de chiffrement actuels (vu qu'il existe l'algorithme de Shor permettant de factoriser des gros nombres bi-premier avec une complexité algorithmique tout a fait viable... sur un ordinateur quantique).
Avatar de vanskjære vanskjære - Membre averti https://www.developpez.com
le 01/08/2018 à 16:38
Citation Envoyé par Anselme45 Voir le message
Tu peux l'appliquer à n'importe quoi, même aux couches culottes de ton petit dernier, cela ne serre pas toujours à quelque chose
Je t'assure que les premiers jours c'est de la matière noire. Un vrai concentré de quantique!!!



Sinon pour la route : http://www.commitstrip.com/fr/2018/07/05/one-talk-to-rule-them-all/
Avatar de frfancha frfancha - Membre confirmé https://www.developpez.com
le 01/08/2018 à 16:41
Citation Envoyé par Anselme45 Voir le message
même aux couches culottes de ton petit dernier, cela ne serre pas toujours
De toute façon c'est mieux si les couches ne sont pas trop serrées, cela fait des marques rouges sur les hanches, sinon. Bourreau d'enfant ;-)
Avatar de frfancha frfancha - Membre confirmé https://www.developpez.com
le 01/08/2018 à 16:43
Citation Envoyé par Juniper62 Voir le message
bref ce petit c** a voulu faire le buzz et vous avez marché dedans, vous avez même couru ...
Clair. Heu t'es qui exactement pour savoir que ce diplomé en math et info à 18 ans est un petit con.
Contacter le responsable de la rubrique Accueil