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.

改进版的 q-means 量子算法和 dequantized 算法，分别以 O ((k^2)/(ε^2)(√k*d + log (Nd))) 和 O ((k^2)/(ε^2)(kd + log (Nd))) 的时间复杂度在近似 k-means 聚类中取得优化，其中 k 代表簇数量，ε 代表误差率，N 代表向量数量，d 代表向量维度。