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})} \eta^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 $\eta$ 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.

我们给出了在 QRAM 模型中，对于经典 k - 均值聚类问题的量子逼近方案（即对于每个 ε>0，具有（1+ε）- 逼近），其运行时间只有数据点数量的对数多项式依赖。具体而言，对于存储在 QRAM 数据结构中的包含 N 个在 R^d 中的点的数据集 V，我们的量子算法以时间 Γ(O)((2^(Γ(O)(k/ε)))η^2d) 运行，并且以高概率输出一个包含 k 个中心的集合 C，其中 cost (V, C) ≤ (1+ε)・cost (V, C_OPT)。这是第一个具有对 k - 均值问题具有（1+ε）可证逼近保证且具有多项式对数运行时间的量子算法。此外，与先前的无监督学习方法不同，我们的量子算法不需要量子线性代数子程序，并且其运行时间与出现在这些过程中的参数（例如条件数）无关。