Quantum Clustering with k-Means: a Hybrid Approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917595368652800 |
|---|---|
| author | Poggiali, Alessandro Berti, Alessandro Bernasconi, Anna Del Corso, Gianna M. Guidotti, Riccardo |
| author_facet | Poggiali, Alessandro Berti, Alessandro Bernasconi, Anna Del Corso, Gianna M. Guidotti, Riccardo |
| contents | Quantum computing is a promising paradigm based on quantum theory for performing fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degree of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version, still obtaining comparable clustering results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06691 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Quantum Clustering with k-Means: a Hybrid Approach Poggiali, Alessandro Berti, Alessandro Bernasconi, Anna Del Corso, Gianna M. Guidotti, Riccardo Quantum Physics Emerging Technologies Machine Learning Quantum computing is a promising paradigm based on quantum theory for performing fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degree of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version, still obtaining comparable clustering results. |
| title | Quantum Clustering with k-Means: a Hybrid Approach |
| topic | Quantum Physics Emerging Technologies Machine Learning |
| url | https://arxiv.org/abs/2212.06691 |