q-means: A quantum algorithm for unsupervised machine learning

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}\leftk d fracη{δ²}κ(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}\leftk² d frac{η^2.5}{δ³} + k^2.5 frac{η²}{δ³} rightper iteration, which is linear in the number of featuresd, and polynomial in the rankk, the maximum square normηand the error parameterδ. Both running times are only polylogarithmic in the number of datapointsN. Our algorithm provides substantial savings compared to the classicalk-means algorithm that runs in timeO(kdN)$ per iteration, particularly for the case of large datasets.