Quantum speed-up for unsupervised learning

Esma Aïmeur 1 Gilles Brassard 1 Sébastien Gambs 2, 3
2 CIDER
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique , CentraleSupélec
Abstract : We show how the quantum paradigm can be used to speed up unsupervised learning algorithms. More precisely, we explain how it is possible to accelerate learning algorithms by quantizing some of their subroutines. Quantization refers to the process that partially or totally converts a classical algorithm to its quantum counterpart in order to improve performance. In particular, we give quantized versions of clustering via minimum spanning tree, divisive clustering and k-medians that are faster than their classical analogues. We also describe a distributed version of k-medians that allows the participants to save on the global communication cost of the protocol compared to the classical version. Finally, we design quantum algorithms for the construction of a neighbourhood graph, outlier detection as well as smart initialization of the cluster centres.
Type de document :
Article dans une revue
Machine Learning, Springer Verlag, 2013, 90 (2), pp.261-287. 〈10.1007/s10994-012-5316-5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00736948
Contributeur : Sébastien Gambs <>
Soumis le : lundi 1 octobre 2012 - 02:11:48
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Lien texte intégral

Identifiants

Citation

Esma Aïmeur, Gilles Brassard, Sébastien Gambs. Quantum speed-up for unsupervised learning. Machine Learning, Springer Verlag, 2013, 90 (2), pp.261-287. 〈10.1007/s10994-012-5316-5〉. 〈hal-00736948〉

Partager

Métriques

Consultations de la notice

1067