Overblog
Editer l'article Suivre ce blog Administration + Créer mon blog
4 août 2018 6 04 /08 /août /2018 11:57

Le 19 juin 2018, une jeune femme de 18 ans, Ewin Tang, a présenté à Berkeley une preuve qu'elle pouvait faire mieux, avec un algorithme classique, qu'avec un algorithme quantique. On dit souvent que l'avenir de l'informatique est aux ordinateurs quantiques, c'est-à-dire dont la logique n'est plus binaire (bits de 0 ou 1) mais quantique (qbits). Ce n'est pas si sûr. Voici la publication scientifique qui présente les travaux de la jeune mathématicienne, soumise le 10 juillet 2018.

Titre : A quantum-inspired classical algorithm for recommendation systems
Auteur : Ewin Tang
(Submitted on 10 Jul 2018)

Résumé :
A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an m×n matrix of small rank k. We give the first classical algorithm to produce a recommendation in O(poly(k)polylog(m,n)) time, which is an exponential improvement on previous algorithms that run in time linear in m and n. Our strategy is inspired by a quantum algorithm by Kerenidis and Prakash: like the quantum algorithm, instead of reconstructing a user's full list of preferences, we only seek a randomized sample from the user's preferences. Our main result is an algorithm that samples high-weight entries from a low-rank approximation of the input matrix in time independent of m and n, given natural sampling assumptions on that input matrix. As a consequence, we show that Kerenidis and Prakash's quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not in fact give an exponential speedup over classical algorithms.

Comments : 35 pages
Subjects : Information Retrieval (cs.IR); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Quantum Physics (quant-ph)
Cite as : arXiv:1807.04271 [cs.IR]
(or arXiv:1807.04271v1 [cs.IR] for this version)
Submission history
From: Ewin Tang
[v1] Tue, 10 Jul 2018 20:57:24 GMT (31kb)

Cliquer sur le lien pour télécharger la publication scientifique (fichier .pdf) :
https://arxiv.org/pdf/1807.04271

SR

http://rakotoarison.over-blog.com/article-srb-20180710-publi-algorithme-quantique.html


 

Partager cet article
Repost0

commentaires

F
Petite erreur dans votre article: Ewin Tang est *une jeune mathematicienne* de 18 ans<br /> https://www.forbes.com/profile/ewin-tang/?list=30under30-science#5d88337118c6
Répondre


 




Petites statistiques
à titre informatif uniquement.

Du 07 février 2007
au 07 février 2012.


3 476 articles publiés.

Pages vues : 836 623 (total).
Visiteurs uniques : 452 415 (total).

Journée record : 17 mai 2011
(15 372 pages vues).

Mois record : juin 2007
(89 964 pages vues).