Do you know what q-means?
João F. Doriguello Alessandro Luongo Ewin Tang
Clustering is one of the most important tools for analysis of large datasets,
and perhaps the most popular clustering algorithm is Lloyd's iteration for
$k$-means. This iteration takes $N$ vectors $v_1,\dots,v_N\in\mathbb{R}^d$ 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 an overall improved version of the "$q$-means" algorithm,
the quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and
Prakash (2019) which performs $\varepsilon$-$k$-means, an approximate version
of $k$-means clustering. This algorithm does not rely on the quantum linear
algebra primitives of prior work, instead only using its QRAM to prepare and
measure simple states based on the current iteration's clusters. The time
complexity is $O\big(\frac{k^{2}}{\varepsilon^2}(\sqrt{k}d + \log(Nd))\big)$
and maintains the polylogarithmic dependence on $N$ while improving the
dependence on most of the other parameters. We also present a "dequantized"
algorithm for $\varepsilon$-$k$-means which runs in
$O\big(\frac{k^{2}}{\varepsilon^2}(kd + \log(Nd))\big)$ time. Notably, this
classical algorithm matches the polylogarithmic dependence on $N$ attained by
the quantum algorithms.