A Quantum Approximation Scheme for k-Means
Ragesh Jaiswal
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.