Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1812.03584

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, Anupam Prakash

Published Dec 10, 2018• 170 citations
arXivHTMLPDF

Abstract

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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ 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.

DOI
10.48550/arxiv.1812.03584

Related papers

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)$ per iteration, where $\kappa(V)$ is the condition number, $\mu(V)$ is a parameter that appears in quantum linear algebra procedures and $\eta = \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $\eta$ and the error parameter $\delta$. 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.

•Jan 1, 2019•22 citations

Comparative Analysis of Classical and Quantum Approach for Unsupervised K-Means Algorithm

G. Murali, Paruchuri Pravallika, Narreddy Aravind Reddy +2 more

Quantum algorithms are being extensively researched nowadays, seeing the potential to provide exponential speedup compared to classical algorithm execution. This speedup can play a significant role in machine learning, where training a model is usually prolonged. Training a machine learning model requires compressing large vectors into small computational units, and quantum computers inherently are fast at compressing the large vectors into small computations and tensor products. The present work aims to compare the K-means, a classical machine learning algorithm, and Q-means, a Quantum algorithm. Here in this work, we use q-means, a quantum algorithm for clustering, a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means. [14]It outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. The experimental results are demonstrated, which show a significant difference between k-means and q-means algorithms.

•Jul 2, 2021•0 citations

Novel Enhanced Unsupervised Quantum Clustering Algorithm

Diptanshu Sikdar, Joe Clapis, Swetha Bhattacharya

Every day, humans generate approximately 2.5 billion gigabytes of new data. While this data is crucial in applications such as drug development and cybersecurity, it is mostly unstructured and unlabeled which makes it difficult to process effectively. Businesses and governments alike solve this problem by using machine learning algorithms to characterize the data and make decisions with it. However, conventional machine learning processes consume excessive computational resources and time: one of the most prominent, K-means clustering, has an approximate time complexity of O(n^2), where n is the input data size. This quadratic time complexity causes scalability problems with large datasets. In this project, I have created an improved, more scalable clustering algorithm by leveraging quantum computation. The approach (new Q-means) involves an Angle Embedding Feature Map, an d-dimensional SWAP Test, and a dynamic, threshold distance-based termination criteria. After implementing this algorithm using the IBM Qiskit SDK, the new Q-means algorithm was run several times on different dimensional datasets. On an average, the new Q-means performed 18% better than the K-means algorithm based on the Adjusted Rand Index. In terms of the simulation execution time, the new Q-means was about six times faster than the existing Q-means due to a multi-threaded implementation and faster convergence. The time complexity of the new Q-means without a Quantum Random Access Memory (QRAM) is O(n^2). While the existing Q-means algorithm, which utilizes QRAM, has a time complexity of O(n(log n)^p), the time complexity of the new Q-means with QRAM is significantly better—O(n).

Journal of Student Research•May 31, 2022•0 citations

A Quantum Approximation Scheme for k-Means

Ragesh Jaiswal

We give a quantum approximation scheme (i.e., $(1 + \varepsilon)$-approximation for every $\varepsilon > 0$) for the classical $k$-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset $V$ with $N$ points in $\mathbb{R}^d$ stored in QRAM data structure, our quantum algorithm runs in time $\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)$ and with high probability outputs a set $C$ of $k$ centers such that $cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})$. Here $C_{OPT}$ denotes the optimal $k$-centers, $cost(.)$ denotes the standard $k$-means cost function (i.e., the sum of the squared distance of points to the closest center), and $η$ is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of $(1+\varepsilon)$ for the $k$-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.

arXiv:2308.08167•Aug 16, 2023•5 citations

Quantum algorithms for supervised and unsupervised machine learning

Seth Lloyd, Masoud Mohseni, Patrick Rebentrost

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.

arXiv:1307.0411•Jul 1, 2013•1,080 citations

Do you know what q-means?

Arjan Cornelissen, João Fernando Doriguello, Alessandro Luongo +1 more

Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for $k$-means. This algorithm takes $n$ vectors $V=[v_1,\dots,v_n]\in\mathbb{R}^{d\times n}$ and outputs $k$ centroids $c_1,\dots,c_k\in\mathbb{R}^d$; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical $\varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity $\tilde{O}\big(\frac{\|V\|_F^2}{n}\frac{k^{2}d}{\varepsilon^2}(k + \log{n})\big)$, exponentially improving the dependence on the data size $n$ and matching that of the "$q$-means" quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19). Moreover, we propose an improved $q$-means quantum algorithm with time complexity $\tilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{3/2}d}{\varepsilon}(\sqrt{k}+\sqrt{d})(\sqrt{k} + \log{n})\big)$ that quadratically improves the runtime of our classical $\varepsilon$-$k$-means algorithm in several parameters. Our quantum algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states based on the current iteration's clusters and multivariate quantum amplitude estimation. Finally, we provide classical and quantum query lower bounds, showing that our algorithms are optimal in most parameters.

arXiv:2308.09701•Aug 18, 2023•7 citations
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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)κ(V)κ(V) is the condition number, μ(V)μ(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2η= \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm ηηη and the error parameter δδδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)\kappa(V)κ(V) is the condition number, μ(V)\mu(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2\eta = \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm η\etaη and the error parameter δ\deltaδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
Quantum algorithms are being extensively researched nowadays, seeing the potential to provide exponential speedup compared to classical algorithm execution. This speedup can play a significant role in machine learning, where training a model is usually prolonged. Training a machine learning model requires compressing large vectors into small computational units, and quantum computers inherently are fast at compressing the large vectors into small computations and tensor products. The present work aims to compare the K-means, a classical machine learning algorithm, and Q-means, a Quantum algorithm. Here in this work, we use q-means, a quantum algorithm for clustering, a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means. [14]It outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. The experimental results are demonstrated, which show a significant difference between k-means and q-means algorithms.
Every day, humans generate approximately 2.5 billion gigabytes of new data. While this data is crucial in applications such as drug development and cybersecurity, it is mostly unstructured and unlabeled which makes it difficult to process effectively. Businesses and governments alike solve this problem by using machine learning algorithms to characterize the data and make decisions with it. However, conventional machine learning processes consume excessive computational resources and time: one of the most prominent, K-means clustering, has an approximate time complexity of O(n^2), where n is the input data size. This quadratic time complexity causes scalability problems with large datasets. In this project, I have created an improved, more scalable clustering algorithm by leveraging quantum computation. The approach (new Q-means) involves an Angle Embedding Feature Map, an d-dimensional SWAP Test, and a dynamic, threshold distance-based termination criteria. After implementing this algorithm using the IBM Qiskit SDK, the new Q-means algorithm was run several times on different dimensional datasets. On an average, the new Q-means performed 18% better than the K-means algorithm based on the Adjusted Rand Index. In terms of the simulation execution time, the new Q-means was about six times faster than the existing Q-means due to a multi-threaded implementation and faster convergence. The time complexity of the new Q-means without a Quantum Random Access Memory (QRAM) is O(n^2). While the existing Q-means algorithm, which utilizes QRAM, has a time complexity of O(n(log n)^p), the time complexity of the new Q-means with QRAM is significantly better—O(n).
We give a quantum approximation scheme (i.e., (1+ε)(1 + \varepsilon)(1+ε)-approximation for every ε>0\varepsilon > 0ε>0) for the classical kkk-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset VVV with NNN points in Rd\mathbb{R}^dRd stored in QRAM data structure, our quantum algorithm runs in time O~(2O~(kε)η2d)\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)O~(2O~(εk​)η2d) and with high probability outputs a set CCC of kkk centers such that cost(V,C)≤(1+ε)⋅cost(V,COPT)cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})cost(V,C)≤(1+ε)⋅cost(V,COPT​). Here COPTC_{OPT}COPT​ denotes the optimal kkk-centers, cost(.)cost(.)cost(.) denotes the standard kkk-means cost function (i.e., the sum of the squared distance of points to the closest center), and ηηη is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of (1+ε)(1+\varepsilon)(1+ε) for the kkk-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.
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.
Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for kkk-means. This algorithm takes nnn vectors V=[v1,…,vn]∈Rd×nV=[v_1,\dots,v_n]\in\mathbb{R}^{d\times n}V=[v1​,…,vn​]∈Rd×n and outputs kkk centroids c1,…,ck∈Rdc_1,\dots,c_k\in\mathbb{R}^dc1​,…,ck​∈Rd; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical ε\varepsilonε-kkk-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity O~(∥V∥F2nk2dε2(k+log⁡n))\tilde{O}\big(\frac{\|V\|_F^2}{n}\frac{k^{2}d}{\varepsilon^2}(k + \log{n})\big)O~(n∥V∥F2​​ε2k2d​(k+logn)), exponentially improving the dependence on the data size nnn and matching that of the "qqq-means" quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19). Moreover, we propose an improved qqq-means quantum algorithm with time complexity O~(∥V∥Fnk3/2dε(k+d)(k+log⁡n))\tilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{3/2}d}{\varepsilon}(\sqrt{k}+\sqrt{d})(\sqrt{k} + \log{n})\big)O~(n​∥V∥F​​εk3/2d​(k​+d​)(k​+logn)) that quadratically improves the runtime of our classical ε\varepsilonε-kkk-means algorithm in several parameters. Our quantum algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states based on the current iteration's clusters and multivariate quantum amplitude estimation. Finally, we provide classical and quantum query lower bounds, showing that our algorithms are optimal in most parameters.