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
