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.
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.
Abstract Clustering algorithms are of fundamental importance when dealing with large unstructured datasets and discovering new patterns and correlations therein, with applications ranging from scientific research to medical imaging and marketing analysis. In this work, we introduce a quantum version of the density peak clustering algorithm, built upon a quantum routine for minimum finding. We prove a quantum speedup for a decision version of density peak clustering depending on the structure of the dataset. Specifically, the speedup is dependent on the heights of the trees of the induced graph of nearest-highers, i.e. the graph of connections to the nearest elements with higher density. We discuss this condition, showing that our algorithm is particularly suitable for high-dimensional datasets. Finally, we benchmark our proposal with a toy problem on a real quantum device.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
We present quantum algorithms for performing nearest-neighbor learning and k--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
Data clustering consists of grouping data without prior training, a process known as unsupervised learning. Given the constant growth of database volumes, contemporary computers require significant computational time to perform this partitioning. To effectively address this challenge, quantum computing offers a promising perspective, as it could eventually provide more efficient resources for clustering massive datasets. However, current quantum computers are not yet mature; they are prone to noise, which limits their practical utility. In this context, we have designed a hybrid classical-quantum clustering algorithm tailored for the current Noisy Intermediate-Scale Quantum (NISQ) era. We evaluated this algorithm under various conditions and across different types of datasets, comparing it against several well-known clustering algorithms. Our results demonstrate that, under certain conditions, quantum noise can actually provide an advantage to our algorithm. Furthermore, we worked on deploying this algorithm on actual quantum processors and developed tools to optimize this deployment. Finally, to diversify the quantum architectures used, we extended our research to include neutral-atom quantum computers.
Machine-learning tasks frequently involve problems of manipulating and classifying large numbers of vectors in high-dimensional spaces. Classical algorithms for solving such problems typically take time polynomial in the number of vectors and the dimension of the space. Quantum computers are good at manipulating high-dimensional vectors in large tensor product spaces. This paper provides supervised and unsupervised quantum machine learning algorithms for cluster assignment and cluster finding. Quantum machine learning can take time logarithmic in both the number of vectors and their dimension, an exponential speed-up over classical algorithms.