Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

À 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

151PARTAGES

22  0 
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

Une erreur dans cette actualité ? Signalez-le nous !

Avatar de onilink_
Membre expérimenté 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).
11  0 
Avatar de frfancha
Membre éclairé 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.
12  1 
Avatar de shadypierre
Membre actif https://www.developpez.com
Le 02/08/2018 à 0:21
Citation Envoyé par Juniper62 Voir le message
c'est très certainement parce que la mécanique quantique n'est pas abordable pour le 1er péquenaud venu ...
Il faut tout de même se sentir bien mal dans sa peau pour pondre ce genre de message
7  0 
Avatar de tpericard
Membre averti https://www.developpez.com
Le 01/08/2018 à 21:24
Hello,

Une excellente introduction à l'information quantique
http://dept-info.labri.fr/~ges/ENSEIGNEMENT/CALCULQ/polycop_calculq.pdf

Bonne lecture
4  0 
Avatar de vxlan.is.top
Membre éprouvé https://www.developpez.com
Le 06/08/2018 à 15:12
Ce qui est intéressant dans cette histoire, c'est que l'existence d'un algorithme quantique a permis d'améliorer toute une famille d'algorithmes classiques...

L'algorithmique quantique peut donc être utilisée comme modèle théorique pour stimuler la recherche.

-VX
4  0 
Avatar de clementmarcotte
Inactif https://www.developpez.com
Le 02/08/2018 à 0:14
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 ...
Quand on est diplômé d'université à 18 ans, on est particulièrement doué. Parce qu'avant d'accéder à l'université en Amérique du Nord, il faut normalement au moins 12 ans d'études. (14 ans au Québec.)

Donc, c'est plutôt (1/petit c**)
3  0 
Avatar de 4sStylZ
Membre éclairé https://www.developpez.com
Le 03/08/2018 à 17:44
Je trouve même pas ça tendancieux pour une fois. Le titre est clair c’est « un algorithme classique peut être aussi performant qu’un algo quantique » ce n’est pas un algo classique qui est plus rapide que l’ensemble des algos quantique…

Rien ne sous entend que ce ne soit pas un cas singulier.

Quant au reste, bravo au petit jeune qui a apporté bien plus que les jaloux ici haha.
3  0 
Avatar de tmcuh
Membre régulier 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"
3  1 
Avatar de 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/
3  1 
Avatar de frfancha
Membre éclairé 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 ;-)
5  3