Quantum algorithms for four problems in density peak clustering
En palabras de los autores
Clustering is a fundamental task in unsupervised learning. The goal is to partition unlabeled data into clusters such that similar elements are assigned to the same cluster, while elements in different clusters are dissimilar. We propose a quantum Monte Carlo approach to density estimation, a key routine in density peak clustering. Building on this approach, we develop quantum algorithms for the full clustering problem and three related tasks: decision clustering, cluster counting, and heavy cluster counting. For each one, we establish a polynomial quantum query speedup under assumptions on the scaling of dataset-dependent parameters. Numerical experiments suggest that these conditions are satisfied for several practically relevant settings.
Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 26 pages, 8 figures, 1 table, 6 pseudo-codes