Do you know what q-means?

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=[v1,dots,vn]∈ℝd× n and outputs k centroids c1,dots,ck∈ℝ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 tildeObig(frac|V|F2nfrack2dvarepsilon2(k + logn)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 tildeObig(frac|V|F√nfrack3/2dvarepsilon(√k+√d)(√k + logn)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.