Quantum (Inspired) D2-sampling with Applications

D 2 -sampling is a fundamental component of sampling-based clustering algorithms such as k-means++. Given a dataset V ⊂ R d with N points and a center set C ⊂ R d , D 2 -sampling refers to picking a point from V where the sampling probability of a point is proportional to its squared distance from the nearest center in C. The popular k-means++ algorithm is simply a k-round D 2 -sampling process, which runs in O(N kd) time and gives O(log k)-approximation in expectation for the k-means problem. In this work, we give a quantum algorithm for (approximate) D 2 -sampling in the QRAM model that results in a quantum implementation of k-means++ with a running time Õ(ζ 2 k 2 ). Here ζ is the aspect ratio (i.e., largest to smallest interpoint distance) and Õ hides polylogarithmic factors in N, d, k. It can be shown through a robust approximation analysis of k-means++ that the quantum version preserves its O(log k) approximation guarantee. Further, we show that our quantum algorithm for D 2 -sampling can be dequantized using the sample-query access model of [Tan23]. This results in a fast quantuminspired classical implementation of k-means++, which we call QI-k-means++, with a running time O(N d) + Õ(ζ 2 k 2 d), where the O(N d) term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-k-means++ on large datasets with bounded aspect ratio. Finally, we use our quantum D 2 -sampling with the known D 2 -sampling-based classical approximation scheme to obtain the first quantum approximation scheme for the k-means problem with polylogarithmic running time dependence on N .