Quantum (Inspired)  $D^2$-sampling with Applications
Authors: Poojan Chetan Shah
Ragesh Jaiswal
Venue: ICLR 2025 Poster (2025)
Keywords: quantum
clustering
k-means++
Primary area: optimization

Abstract: $D^2$-sampling is a fundamental component of sampling-based clustering algorithms such as $k$-means++. 
Given a dataset  $V \subset \mathbb{R}^d$ with $N$ points and a center set $C \subset \mathbb{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(Nkd)$ 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 $\tilde{O}(\zeta^2 k^2)$. 
Here $\zeta$ is the aspect ratio ( i.e., largest to smallest interpoint distance) and $\tilde{O}$ 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 Tang (PhD Thesis, Ewin Tang, University of Washington, 2023). This results in a fast quantum-inspired classical implementation of $k$-means++, which we call  QI-$k$-means++, with a running time $O(Nd) + \tilde{O}(\zeta^2k^2d)$, where the $O(Nd)$ 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$.

Published as a conference paper at ICLR 2025
QUANTUM (INSPIRED) Di-SAMPLING WITH APPLICATIONS
Poojan Chetan Shah and Ragesh Jaiswal Department of Computer Science and Engineering Indian Institute of Technology Delhi
{cs1221594, rjaiswall @cse. iitd. ac. in
ABSTRACT
Da-sampling is a fundamental component sampling-based clustering algorithms such k-means+t. Given dataset V C I with N points and center set C C R., samsamngnng refers to picking a point from V where the sampling probability of point is proportional to its squared distance from the nearest center in C. The popular k-means++ algorithm is simply a k-round D²-sampling process, which runs in (Nddd time and gives Oloo k) apaproxxxmttionn in expectation for the k-means problem. In this work, we give quantum algorithm for (approximate) D2 sammangg the QRAM model that results quantum implementation of k-means++ with running time Ō((² Here Ç the aspect ratio (i.e., largest smallest interpoint distance) and Ô hides polylogarithmic factors in N, d, can be shown through robust approximation analysis of k--mean+++ that the quantum version preserves its (log k) approximation guarantee. Further, we show that our quantum algorithm for 1 -a-samlinng can be dequantized using the sample-quee query access model of Tang (2023). This results in a fast quantum-inspires classical implementation o k-means++, which call Q--k-means++ with a running time ( + O(c2k2d), where the O(Nd) term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-k- means++ large datasets with bounded aspect ratio. Finally, we use our quantum D²- sampingg with the known se--smmlling-base classical approximation scheme obtain the first quantum approximation scheme for the k-means problem with polylogarithmic running time dependence on N.
INTRODUCTION
Data clustering and the k-meaas problem, in particular, have many applications in data processing. The k-means problem is defined as: given set of N points V {ei, ..., UN ) C Rd and positive integer k. find a set C' C. IRd of l centers such that the cost function.
4(V.C) C) = Σ min (v. CEC
is minimised. Here, c( 1 is the Euclidean distance between points and e. Partitioning the points based the closest center in the center set C' gives natural clustering of the data points. Due to its applications in data processing, lot of work has been done in designing algorithms from theoretical and practical standpoints. The k-means problem is known be NP-hard, so is unlikely to have polynomial time algorithm. Much research has been done on designing polynomial time approximation algorithms for the k-means problem. However, the algorithm used practice solve k-means instances is heuristic, popularly known as the k-means algorithm (not to be confused with the k-means problem). This heuristic, also known as Lloyd's iterations Lloyd (1982), iteratively improves the solution in several rounds. The heuristic starts with an arbitrarily chosen set of & centers. In every iteration, (i) partitions the points based on the nearest center and (ii) updates the center set to the centroids of the k partitions. In the classical computational model, it is easy to that every Lloyd iteration costs (Nkd) time. This hill-climbing approach may get stuck at a local minimum or take huge amount of time converge, and hence, it does not give provable guarantees

---

Published as a conference paper at ICLR 2025
on the quality of the final solution or the running time. In practice, Lloyd's iterations are usually preceded by the k-means++ algorithm Arthur Arthur & Vassilvitskii (2007). a fast sampling- basedd approach for picking the initial & centers that also gives approximation guarantee. So, Lloyd's iterations, preceded by the k-means++ algorithm, give the best of both worlds, theory and practice. Hence, it is unsurprising that lot of work has been done these two algorithms. The work ranges from efficiency improvements in specific settings to implementations in distributed and parallel models. With the quantum computing revolution imminent, it is natural talk about quantum versions of these algorithms and quantum algorithms for the k-means problem in general.
Early work on the k-means problem within the quantum setting involved efficiency gains from quantizing Lloyd's iterations. In particular, Aīmeur et al. (013 gave an O Vk
/ time algorithm
for executing single Lloyd's iteration for the Metric A k-median clustering problem that is similar to the k-means problem. This was using the quantum minimum finding algorithm of Durr & Hoyer (1999). Using quantum distance estimation techniques assuming quantum data access. [Looyd et al. (011)) gave an O(kN log d) time algorithm for the execution of a single Lloyd's iteration for the k-means problem. More recently, Kerenidis et al. (2019) gave an approximate quantization of the k-means++ method and Lloyd's iteration assuming QRAM data structure Kerenidis & Prakash (2017) access to the data. Interestingly. the running time has only a polylogarithmic dependence on the size N of the dataset. The algorithm uses quantum linear algebra procedures, and hence, there is dependence on certain parameters that appear in such procedures, such as the condition number <(V). Since Lloyd's iterations do not give an approximation guarantee, its quantum version is also a heuristic without a provable approximation guarantee. A quantum implementation of k-means++ was also given in Kerenidis al. (2019). Note that k-means++ gives an approximation guarantee of Ollog k) in expectation for the k-means problem. However, this approximation guarantee does not immediately extend to the quantum implementation of k-means++ since the quantum procedure introduces D2 sampling errors, and one must show that the approximation analysis is robust against those errors. This was indeed missing from Kerenidis al. (2019). D2 Da-samlinng is fundamental component of k-means+++ Given the dataset V and a center set C, D2 D2-sampling refers to picking a point from V such that the sampling probability is proportional to its squared distance from the nearest center in C. Starting with C' = } and D²-sampling and updating C' in k rounds is precisely the k-means++ algorithm. In recent line of work Bhattacharya et al. (2020a); Grunau et al.. (2023). robust version of k-means++ has been analyzed where the Da-samlling probability has multiplicative (1 + E) error. This is called noisy k-mmens+++, and it is now known Grunau et al.. (2023) that this algorithm gives Olog k) approximation. This shows that k-means++ is indeed robust against small relative D -amampinng errors. This further means that the quantum implementation of k-means++ in Kerenidis et al. (201)) gives an approximation guarantee of Ollo k).
In this work, we design quantum and clustering algorithms. We start with k-means++. Quantizing" k-means++ reduces to quantizing the D2 D2-sampling step. Most of the ideas for quantizing D2 D2-sampling such as coherent amplitude estima- tion, median estimation, distance estimation, minimum finding, etc., have already been developed in previous works on quantum unsupervised learning (see Wiebe et al.] (2015) for examples of several such tools). In particular, Kerenidis et al. (2019) used these tools give quantum implementation of Da-sampling. We provide a similar quantum algorithm and then combine this with the known Ollo k) approximation guarantee for noisy k-means++ to state the following result.
classical algorithms for Da-sampling-bass -bsed
Theorem 1. There is a quantum implementation of k-means++ that runs in time Ō({²k²) and gives an Oloo k)) factor approximate solution for the k-means problem with a probability of at least 0.99. Here, Ô hides log" (Nd) and log" (kd) terms
Dependence on aspect ratio Ç: Note that the running time depends on the aspect ratio Ç. which is defined to be the ratio of the maximum to the minimum interpoint distance. For the remaining discussion, it is important understand that the k-means problem remains NP-hard to approximate
'Quantizing is that is used to refer to designing quantum version of algorithm with significant efficiency advantage over the corresponding classical algorithm.
'The output of k-means++ is a subset of data points, which can be stated as a subset of indices. If the description of centers is the expected output, the running time will also include factor of d.
2

---

Published as a conference paper at ICLR 2025
(beyond a fixed constant) even when restricted to instances where Ç upper bounded by small constant. See Awasthi et al. (2015) for such an hardness reduction
The above result is another addition to the growing area of Quantum Machine Learning (QML) where the goal is to design quantum algorithms for machine learning problems with large speed-ups over their classical counterparts. There was flurry of activity in QML where significant speedups were shown for problems such as recommendation systems Kerenidis & Prakash] (2017). However, was not clear whether such speedups could entirely be attributed to the quantum data access model (QRAM) upon which these works were built. The works of Tang (2019) 2022 2023) gave much clarity on this aspect. These works showed that similar speedups (up to some polynomial factors) are achievable in the classical model using a classical counterpart of QRAM, now popularly known as the sample-query (SQ) access data structure. In other words, most QMI. algorithms could be dequantized. Interestingly, by setting up the sample-query access data structure, the dequantized algorithms give rise to quantum muantum-inspired classical algorithms. The interesting property of such a quantum-inspiree algorithm is that apart from the linear time spent on setting up the sample-query access data structure, which can be thought of as preprocessing time, the algorithm is extremely fast (otherwise, it would not have given the quantum speedup). Our second contribution is dequantize D2 sammling using Tang's SQ model. This turns out to be simple since the sample-query access model primarily involves sampling vectors based squared & norms, which is how De-sampling also works. Based on this, we give a mantum--nssiire classical implementation of k-means++. The following theorem formally states our main result on this.
Theorem 2. There is a classical implementation of k-means++ + (which we call Ql-k-means++) that runs in time O d) + k22 log k log Nd). With probability at least 0.99, QI-k-means++ outputs k centers that give Olog k) aapproximiaioon in expectation for the k-means problem.
Note that the ((Nd) term in the running time is for setting up the SQ data structure, which can be thought of as a preprocessing operation. This setting of the data structure can easily be parallelized on multi-core processor. Once the data structure is available, the running time is sublinear in N. The linear dependence on the dimension d can also be changed to sublinear at the cost of worsening the dependence on Ç. This is through implementing a small relative error Da-sampling procedure, which gives an implementation of the noisy k-means++ which we know also gives Ollog k) aapproximmaion. Since the aspect ratio Ç can be efficiently computed in advance Shamos & Hoey (1975); ; Dietzfelbinger et al. (1997), we can appropriately choose between the algorithms in Theorem 2 and Theorem 3 We state this result formally below.
Theorem 3. There is a classical implementation of noisy k-means++ (which call Ql-noisy- k-means++) that runs in time ((N)) + O( log k log Nd). With probability at least 0.99, Q1- moisy-k-means++ outputs ls centers that give Ollog appproxiimatoon in expectation for the k-means problem.
Finally, we design quantum approximation scheme for the k-means problem with polylogarithiic dependence on the size N of the data set. We do this by quantizing the highly parallel, D2 Da-sampling- based approximation scheme Bhattaachaaa et al. (0200). An approximation scheme is an algorithm that, in addition to the dataset and k, takes an error parameter > O as input and outputs solution with a cost within (1 + z) factor of the optimal. The k-means problem is NP-hard to efficiently approximate beyond an approximation factor of 1.07 Cohen-Chhdaaa & C.S. (2019). The tradeoff in obtaining this fine- fine-grained approximation of (1 + E) that the running time of our algorithm has an exponential dependence on le and error parameter s. In the classical setting, such algorithms are categorized as Fixed Parameter Approximation Schemes (fpt-AS). Such (1 + aaapprooxnottoon algorithms can have exponential running time dependence on the parameter (e.g.. the number of clusters & in our setting). The practical motivation for studying -are-marreeter Tractability (FPT) for computationally hard problems is that when the parameter is small (e.g., number of clusters k ~ 5). the running time is not prohibitively large. We state our main result as the following theorem, which we will prove in the remainder of the paper.
'The harduess of approximation argument in Awasthi et al. (2015) goes through the vertex cover problem. For a given graph = (V, EE. the k-means instance includes [ points in a |Vl-dimessional space. The point corresponding to edge (i, has 1 in coordinates i,j and O everywhere else. It is clear that v2 in this case.
3

---

Published as a conference paper at ICLR 2025
Theorem 4. Let < 1/2 be the enror parameter. There is a quantum algorithm that, when given QRAM data structure access to dataset V E &RNxd, runs in time Ô (20()) and outputs k center set C' E BRxx such that with high probability &VV C) < (1++) OPT. Here, Ç is the aspect ratio, ie.. the ratio of the maximum to the minimum distance between two given points in V
We end the note that the above quantum approximation scheme can also be dequantized in the sample-query-access model of Tang (202)).
1.1 COMPARISION WITH PREVIOUS WORK
There have been several fast classical implementations of k-means++, These implementations are fast under certain assumptions on the data set or achieved through trading efficiency with an approximation guarantee or both. [Bachem et al. (2016b) gave Monte Carlo Markov Chain (MCMC) based implementation of k-means++. However, this algorithm, called K-MC², preserves the Olog k) approximation guarantee of k--mans+++ only when the dataset satisfies some strong properties that are NP-hard to check. The MCMC- -asee algorithm was improved by the same authors in |Bachem et al.) (2016a), but the approximation guarantee of this algorithm had an additive term (in addition to the multiplicative (log k) factor), which could possibly be large. More recently, fast implementation based on the multi-tree embedding of the data was given by Cohen-Addad et al. (2020)
Algorithm
Time Complexity
Approx. Guarantee
Key Parameters
QI-k-means++ (This Work)
((Nd) + O o( log Nd)
Ollog k
Ç is the aspect ratio
K-MC²
07 k3),, 'O(k'd dog N log kB)
(logk))08r
maxeey (a.pp
Bachem et al.
OPT
is the dataset mean.
(016b)
AFK-MC2
O(Na) O (4 :) *O(Nd) O (k* ('llkg
0llogk)0 storr
(0, 1) controls time solution quality tradeoff
Bachem et al
(2016a)
RejectionSampling O(N(d + log (kc2 log C(N log ()(()))))
+ Olc"log kor
is the aspect ratio. > controls runtime- so- lution quality tradeoff
Cohen-Addad
(020))
Table Comparison fast implementations of k-means+++ Vör7 represents the optimal k-means cost of the dataset. i represents the runtime under the assumptions described in Bachem et al. (20166).
Let us now compare algorithm with K-MC² AFK-MC2 and RejectionSampling
Pre-processing, Ql-k-means++ takes O(Nd) to setup the SQ data structures. AFK-MC2 and RejectionSamplig also require similar pre-processing cost for computing the initial distribution of the markov chain and for performing the multi-tree embedding respectively. An advantage of the SQ data structure is that it is very efficient to update, i.e., add or delete point which costs Olog N) time. This is useful in scenarios where new data points get added periodically, and one needs to recluster the data.
Runtime. K-MC² AFK-MC have runtime which is sublinear in N under certain assumptions. Their runtimes depend on the parameters 7 and E respectively, which can be thought of as being analogous Ç. It is important to note that computing an estimate involves solving the k-means problem itself, while ( is efficiently computable, Even under assumptions, Ql-k-means++ has a better dependence on i (R:2 vs 1-3). We see that Ql-k-meanst+ and RejectionSampling have a tradeoff between N (log N vs (O(1))2) and Ç (52 vs (log 1) +0(1/c2)) Moreover, RejectionSampling has better dependence on is (k2 vs k) but worse dependence d (d d²).
So, in cases where the aspect ratio is not large (c.g., binarized data such as MNIST Deng 2012)) and A is reasonably small, our implementation should be expected to fast and give good solutions.
*The Ô notation hides logarithmic factors in N. In the exponent, it hides logarithmic factors in k and 1/e.
4

---

Published as a conference paper at ICLR 2025
Note that unlike RejectionSampling and AFK-MC our results have tradeoff between efficiency and approximation ratio. Even though our work mainly theoretical nature, we conduct some experimental investigations to see the running time advantage of Ql-k-meanser over k-means++ (the classical implementation).
1.2 RELATED WORK
We have already discussed past research works on quantum versions of the k-means algorithm (i.e., Lloyd's iterations). This includes Aimeur et al. (2013). [Llyyd et al. (2013), and [erenidis et al. (2019). All these have been built using various quantum tools and techniques developed for various problems in quantum unsupervised learning, such as coherent amplitude and median estimation, distance estimation, minimum finding, etc. See Wiebe et al. (2015) for examples of several such tools. We have also discussed previous works fast implementations of the k-means++ algorithm. Other directions on quantum k-means includes adiabatic algorithms (e.g.. -...d et al. (0013) and
algorithms using the QAOA framework (e.g.. Otterbach et al. (2017); Farhi et al. (2014) ). However, these are without provable guarantees. A recent work of Doriguello et al. Doriguello et al. al. (2023)
improves the results of Kerenidis al. (2019) on Lloyd's iterations and obtains quantum algorithm with better running time dependence and removes the dependence on the data matrix dependent parameters such the condition number. They also dequantize their algorithm in the sample-query access model of Tang TTng (2023). However, since Lloyd's 's iterations do not give any approximation guarantee, their algorithms also do not have a provable approximation guarantee. In another recent work Kumar et al. (2023), the quantum algorithm of Kerenidis et al. (2019) is used in a supervised setting to construct decision trees.
2 QUANTUM (INSPIRED) D2-SAMPLING
In this section, we discuss the key ideas the design of our quantum algorithm for D2 D2-sampling and its dequantization in the sample-query (SQ) access model of Tang Tang (2023). Let us first look at the main ideas of our quantum algorithm in the following subsection.
2.1 QUANTUM D²-SAMPLING
We will work under the assumption that the minimum distance between two data points is which can be achieved using scaling. This makes the aspect ratio Ç simply the maximum distance between two data points. We will use for an index into the rows of the data matrix V E Nxd, and j for an index into the rows of the center matrix C E Rmxd We would ideally like to design quantum algorithm that performs the transformation:
|1) (5) (0) - 10) 15) ((),,c)))
(I)
The known quantum tools such swap test followed by coherent amplitude estimation, and median estimation allow one to obtain a state that is an approximation of the ideal state that shown on the right in ( Moreover, this can be done in time that has only polylogarithmic dependence on the input size. The details are provided in the Appendix. For the current high-level discussion, we will assume that the ideal state be prepared. We would like perform sampling from the D distribution over V with respect to the center set C. This means that we would like to sample an index i E [N] with probability:
minjelm) D(vi, e2)²
Pr[1]
(2)
Σ EveNy] minje[m] D(vr.
So, if we can prepare the state:
Σ KE[N]
min D(v,, ))) jE[m]
then we can obtain a good estimate of the denominator of the right expression in 2 which is basically the k-means cost with respect to the current center set C. This follows from the fact that measuring the second register the above state gives the distance of a random data point to its closest center in C. Repeatedly preparing the state and measuring helps obtain close estimate of
5

---

classical algorithm for Published as a conference paper at ICLR 2025
the k-mmaass cost. Now that the k- k-means cost (i.e., the denominator of (2) is known, using few more standard quantum transformations (controlled rotations), we can pull out the state of the second register part of the amplitude of an ancilla qubit. In other words, an approximate version of the following quantum state can be prepared:
Σ N
10) (3.10) V1 11
where B, = 1/2 minje[m] (( Cÿ) and Z is some appropriate normalization term. So, by measuring the above state and doing rejection sampling (ignoring the measurement when the ancilla qubit is 1), obtain -a-sapple. Some of the quantum states shown above are 'ideal' quantum states that we have used to convey the main ideas of the quantum algorithm. The real states will be close approximations of these states, and need carefully account for all the errors introduced. All the details are given in the Appendix. Finally, note that this also gives a quantum implementation of the k-means++ algorithm since the algorithm simply performs -amsmplinng in k: iterations while updating the center set.
In the following subsection, we discuss how to dequantize this quantum algorithm in the sample- query access model of Tang Tang 2003). This gives a D2 -aasamnling.
2.2 QUANTUM INSPIRED DASSAMLIING
Ewin Tang's 's thesis Tang (203) nicely categorizes quantum machine learning (QML) algorithms into ones where the quantum advantage (i.c., polylogarithmic running time) is solely because of the quantum access to the data and the ones where it is not (e.g., the HHL algorithm
SeerrthhmHHrroww Harrow et al.) (2009)). Quantum access means that a (normalized) data vector v = (v(1), .... (dd)) can be loaded onto the quantum workspace in (1) time as (u) u(1) [1) +... + v(d) (d))- One implication of e(1)
having the quantum state (v) is that can be sampled with probability Σn "(y) T by simply making a measurement in the standard basis. One of the key insights in Tang's Thesis TTng (2023) is that QMI. algorithms that benefit soiely from the quantum data access can be "dequantized if we work with an appropriate classical counterpart of the quantum data access that allows sampling access of the kind described above (in addition to the classical access to the data). This is called sample-query access, or SQ access in short. Dequantization means that a classical algorithm can simulate the steps of the quantum algorithm using SQ access with similar running time dependence. The nice property of the SQ access data structures is that it can be constructed classically in linear time. Note that linear time means that we lose the quantum advantage. However, if we keep this aside and count the SQ access data structure construction as preprocessing, the remaining computation has similar advantage as that of the quantum algorithm. This level playing field with the QML algorithm that allows fair comparison, specifically given that setting up quantum access (called QRAM also takes linear time. Such classical algorithms obtained by dequantization are called quantum inspired algorithms. Our quantum algorithms based on D2-sampling fall into the category of QML algorithms that can be dequantized in Tang's SQ access model. This section discusses the quantum-inspired classical algorithm we obtain by dequantizing our quantum algorithm using the SQ access data structure. Naturally, we start the discussion by looking at the definition of the SQ access data structure.
Definition 1 (Query access, Definition 1.1 in Tang (2023)). ). For vector ū C", we have query access to U, denoted by Q(T), for all i E [n], we can query for ((i). We use q(0) to denote the time (cost) of such a query.
Definition 2 (SQ-access to a vector, Definition 1.2 in Tang (203)). For a vector J E C", we have sampling and query access to denoted by SQ(Ø), if we can:
1. query for entries in T as in QT).. The time cost is denoted by q(ū).
2. obtain independent samples i E [ri] where the probability of sampling i is distribution is denoted by Dz. The time cost is denoted by s(ū).
20)2
T 7. This
3. query for [| The time cost is denoted by n(T).
Let sq( = max (Q) S(ū), n(T) denote the time cost of SQ-access.

---

Published as a conference paper at ICLR 2025
||:112
[0(1) + (0(2)}
|a(3)
(P(4))2
()))
1²(2))
[=(3)
(0(4))
1
1
F(1)
#(2)
0(3)
D(4)
Figure 1: A tree data structure to enable sample-query access to example vector of dimension n = 4. Index can be sampled with probability Σ, 10,7 tree.
18, in Oloo n) time by traversing down the
A simple tree-based data structure (see Figure matrices. The details can be found in Tang 2023) various operations.
supports sample-query access for vectors and
Here, we give summary of the running time of
Lemma 1 (Remark 4.12 in Tang 2023
There is a data structure for storing a vector i e TR
supporting the following operations:
Reading and updating an entry of i in O(log n) time. So, q( OOlog n).
2. Finding || in (1)) time. So, n (T) (1))
3. Sampling from D3 in Ologg) time. So, s( Olognn
It follows from the above that sq( = O(log n). Moreover, the time required to construct the data structure is On)).
Let us outline the key ideas in the quantum-inspired classical algorithm in the SQ access model defined above. Let ui,..., UN denote the data vectors, i.c., 2/2 Vi.... Suppose we have set up SQ access for the vectors U1, .i., UN. ([|e) 2 :..., || || 13" (together denoted by SQ(V)), and m centers C1,..., Sm (denoted by SQ(()), .... (Q(m))) Our goal is set up SQ access for the vector w defined as:
min D(v ((v1,)),,.. min D(uN.s)) jE(m]
5E(m]
The reason is that have SQ access, SQ(w), sampling query returns index with distribu-
tion Dw., which is precisely the D sampling distribution. We enable SQ access for w a sequence of steps:
(1) SQ(V), (Q(A), SQ(cm) (2) SQ( SQ(um) (3)SQ(w).
Here uy is the vector defined as:
Vi E [N,,,5( = D(vs, 0j)
|0 ccll
the vector of distances of N data points from the jth center. The above steps are gross simplification of the real steps to understand the high-level ideas and draw parallel to the corresponding quantum steps. In actual implementation, we may be able to enable sample-query access for w but something known oversampling and query access, which is generalization SQ access. Much of the technical effort spent designing these oversampling query accesses. These details are given in the Appendix.
Let us draw a parallel to the quantum algorithm to see that the above SQ-based algorithm is indeed quantum-inspiree The relevant quantum states involved in the D²-sampling algorithm are given below:
(1) Vi, (1), VV.
(1) (x))
(2)
Ji) D(v, c1), DDv,, cm))
(3)
Σ (1)
min D(u; (v),)))) jE(m]
(4)
Σ SE[N]
(1) (0) + v 1 11)

---

Published as a conference paper at ICLR 2025
The correspondence between quantum states and SQ accesses is apparent. So, every step in the quantum algorithm can be simulated using oversampling query access, which leads to a quantum- inspired classical algorithm since the SQ access framework is completely classical. Let now discuss some key elements of the quantum-inspired classical implementation of k-means++ that results from the above quantum-inspired classical D
2.3
If we use the quantum-inspired classical D2 Dessampling iteratively in l rounds to pick & centers, the resulting algorithm is quantum-inspired classical implementation of k-means++, which we call the QI-k-means++ algorithm. This can be seen as a fast implementation of k-means++. We give high-level outline of the algorithm and discuss some of its important properties.
Algorithm Ql-f-meens+++(V,
1: Sctup sample-query query access for dataset V
2: C' f random data point in V
3: for i = 2 to & do
4: Use sample-query access for w (which uses sample-query access for u1,.., U4-1, which in turn uses sample-query access for V and C1, to DD-sample center The vectors
and u1, Ug are as defined and
5: C CCCufch
6: end for
7:
return C
Setting up the sample-query access for the dataset V E xd costs O(Nd) time. This can be thought of the preprocessing time. Setting up the sample-query access is highly parallelizable, seen from the tree-based data structure in Figure [ On a shared memory, multi-processor system with M processing units, the task can be done ((N//M) time, After the preprocessing step (I), the cost of the remaining sa-sampling steps & Here, again, it is possible to parallelize on multi- processor system since much of the time in D²-sampling is spent on waiting for rejection sampling to succeed. The rejection sampling can performed independently on multiple processors until one of the processing units succeeds. This cuts down the time to Ō x22 d/M). We implement the QI-k-means++ algorithm to compare the k-means cost and time with the classical implementation of k-means++ that has a running time ONkd).
be
A QUANTUM APPROXIMATION SCHEME
We convert the D2-sampling- based approximation scheme of Bhattacharya al. (2020b) Quantum version. The approximation scheme is simple and highly parallel, which can be described in few lines.
Algorithm 2 Approximation Scheme
Input: Dataset V, integer A >> O. and error > 0
Output: A center set with (V, C") < (1 +)OPT
(Constant approximation) Find a center set C that is constant factor approximate solution. An (a, (3 pseudo- -pprddd-pproximmtee solution, for constants a, 3, also works.
- (D2 -ammplig)) Pick a set T of poly( points independently from the dataset using D2-sampling with respect the center set C.
(All subsets) Out of all k-tuples (S,,...,SS Sk) of (multi)subsetts of 7 (copies of points in C}, each S, of size O ), return (p(S1),.., ((x))) that gives the least k-means cost. Here, ((S.) denotes the centroid of points in S..
We will discuss the quantization of the above three steps of the approximation scheme of Bhattacharya al. 2020b),, thus obtaining a quantum approximation scheme.
SSteps (2) and (3) in the algorithm are within loop for probability amplification. For simplicity, this loop skipped in this high-level description.
8

---

Published as a conference paper at ICLR 2025
(Constant approximation) The first step requires finding a constant factor approximate solution for the k-means problem. Even though several constant factor approximation algorithms are known, we need one with quantum counterpart that runs in time that is polylogarithmic in the imput size N. One such algorithm is the k-means++ seeding algorithm Arthur & Vassilvitskii (2007). Kerenidis et al. (2019) give approximate quantum version of D2-sampling The approximation guarantee of the +-means++ algorithm is (log k) instead of the constant approximation required in the approximation scheme of Bhattacharya et al. (2020b). It is known from the work of Aggarwal al. (2009) that if the D2 sammlingg in k-means++ is continued for 2k steps instead of stopping after sampling k centers, then we obtain a center set of size 2k that is a (2, ((1))-(seudo approximate solution. This means that this 2k-size center set has k-means cost that is some constant times the optimal. Such pseudo-approximan solution is sufficient for the approximation scheme of Bhattacharya et (2020b)) to work. We show that the neeudo-aprroximatio guarantee of Aggarwal et al. (2009) also holds when using the approximate quantum version of the D sampling procedure.
(D2 (D*-sampling) The second step of (Bhattacharya et al. (0200)) involves D²-sampling, which we already discussed how to quantize. This is no different than the D²-sampling involved in the k- means++ algorithm of the previous step. The sampling in this step is simpler since the center set
C, with respect to which the DP-sampling is performed, does not change (as is the case with the k-means++ algorithm.)
(All subsets) Since the number of points sampled in the previous step is poly(?), we need to Sk) defines (u(Si),.... (()))))...()) We need to compute the k-means cost for every & center set in the list and then pick the one with the least cost. We give quantization of the above steps.
consider a list of (b) O(t)) tuples of subsets, each giving a k-center set (a tuple
Note that the quantization of the classical steps of Bhattacharya et al. (2020b) will incur precision errors. So, we first need to ensure that the approximation guarantee of Bhattacharya et al. (20206) is robust against small errors in distance estimates, De-sampling probabilities, and k-means cost estimates. We must carefully account for errors and ensure that the quantum algorithm retains the (1+ E) approximation guarantee of the robust version of Bhattacharya et al. (2020b). We give the detailed analysis in the Appendix.
4 EXPERIMENTS
We provide an experimental investigation of the Ql-k-means++ algorithm. We implemented our code in C++ for both k-means++ and Ql-k-means++ and the results are averaged over 5 runs. No pre- processigg/dmennionnall
reductions were done on any of the datasets used. The experiments were AMD Ryzen 9 5900HX 4.68 GHz 8 Core processor (parallelization was not used). We must set up the sample and query data structure for the dataset only once to be able to perform seeding for any value of k with each run taking time only polylogarithmic in N. Specifically, if we wanted to perform seeding for q different values of k. say (k1, ..., kg J. then the total runtime for QI-k- - would be ((Nd) + Od jE((]] k3) as compared to O(Nd E se(g kj) for k-means++. This is reason to consider the O(Nd) term as preppocesssing
performed
multicore
We study the runtime (including setup time for the sample and query data structure) of QI-k- + on two extreme types of datasets demonstrate its possible use cases. The first binarized MNIST Salakhutdinov & Murray 2008) (70,000 data points, each being a 28 x 28 pixel image Each pixel has value of either 0 or opposed the original MNIST, which had values from 0 to 255) and the second is IRIS Fisher 1988) (150 data points with four feature values). The plots in Figures 2 and 3 show the cumulative runtime (i.e., the total time for setting up and calculating cluster centers for all values of k up to a certain value).
Ad Advataggeuss regime: For a dataset with large number of points and small aspect ratio (for example. binary MNIST), we find that for one iteration of seeding, our algorithm performs slower but quickly catches up to be significantly faster when we require seeding to be done for multiple
'ote that when picking the center set with the least cost, we can get quadratic improvement in the search for the best k-center set using quantum search. Given that the search space is of size (5) o( this results only in a constant factor improvement in the exponent. So, for simplicity, we leave out the quantum search from the discussion.

---

Published as a conference paper at ICLR 2025
values of & (which is generally the case in practice since in the unsupervised setting, the optimal value of is not known beforehand). This is because most of the time is spent in setting up the data structure, after which the sampling becomes significantly faster. For example, see the left plot for the MNIST dataset. Notice that the cumulative runtime for Ql-k-means++ is almost constant, while for k-means++, it does not scale well due to the multiplicative dependence on N.
Disadvantageous regime: For a dataset with a small number of points and a large aspect ratio, we find that the runtime is dominated by the sampling term and due the quadratic dependence on and Ç. Ql-k-means++ may not scale well. For example, see the right plot for the IRIS dataset.
We give additional experiments larger datasets and comparative analysis with AFKMC² Bachem ct al. (2016a) in Section F of the Appendix.
Oi ki-mmersse-
O--kmatno--
0.000
berounss+4
0.0005
10-
0.0004
09002
0.0000
Figure 2: Cumulative runtime plot for MNIST
Figure 3: Cumulative runtime plot for IRIS
k
2
4
5
7
8
9
10
Ql-K-means++
8.43
8.13
7.81
7.43
7.29
7.09
6.79
6.78
6.66
k-means++
8.35
8.10
7.74
7.38
7.44
7.17
7.12
6.91
6.83
Table 2: Clustering cost for hinarized MNIST (costs are scaled down hy a factor of 10")
k
2
6
10
Ol-k-means++
538.82
253.41
112.53
96.04
83.72
64.92
58.62
56.25 53.99
49.92
k-means++
773.26
227.50
115.33
93.45
83.21
60.14
57.98
50.35
Table 3: Clustering for IRIS (costs are rounded to decimal places)
CONCLUSION AND FUTURE WORK
In this work, we used D2- -aammmping framework to design quantum algorithms for the k-means problem. We also gave their classical counterparts obtained through the dequantization framework of Taag (2023). These algorithms have logarithmic dependence on the number of points in the dataset after appropriate linear time pre-processing for the classical ones. Our algorithms depend on the parameter Ç, which is the aspect ratio of the dataset. Our algorithm Ql-k-means+++ an addition to the collection of fast implementations of the k-means++ seeding. Interestingly, the performance of all these algorithms depend on certain aspect ratio like quantities. Even for a simple dataset where the clusters are located very far apart from each other, the parameter Ç (for Ql-k-means++ and RejectionSampling) and the ratio of optimal 1-means cost to the optimal k-means cost (for K-MC² and AFK-MC" can become quite large. We think that improving the dependence on these quantities and understanding the tradeoff between them and the data size are interesting open problems.
ACKNOWLEDGEMENTS
This work was partially supported by the CSE Research Acceleration Fund of IIT Delhi.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ankit Aggarwal. Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means cluster- ing. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX '09 RANDOM '09, pp. 15-28, Berlin, Heidelberg, 2009. Springer- Serlag. ISBN 100077
9783642036842. doi: 10. 1011007777----44--006666 978-3 642-00635--2
URL
Esma Aimeur, Gilles Brassard, and Sébastien Gambs, Quantum speed-up for unsupervised learning. Machine Learning, 90:261-287 2013.
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In Proceed- ings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pp. 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In Lars Arge and János Pach (eds.), 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceed- ings in Informatics (LIPlcs), pp. 754-767, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz- doi: http://dx. de wwapps/voolleeee
Zentrum fuer Informatik. ISBN 978- 978-3-939897-83-5 2015.754. URL http:tt::40 //rrps
Olivier Bachem, Mario Lucic, Hamed Hassani, and Andreas Krause. Fast and provably good seedings for k-means. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016a. URL https: http::::pppppppceeeeeee www.ses....ppppp.peeeeeeeeeeeeee file/
neurips cc/paper files/paper:2016/
33 .dff
Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Feb. 2016b. doi: 10.1609/aai..v v3011.10255 URL https:///jjs aaai AAAI/art htAT/article/vvw/////aa
Anup Bhattacharya, Jan Eube, Heiko Röglin, and Melanie Schmidt. Noisy, Greedy and Not so Greedy k-Means++. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders (eds.), 28th Annual European Symposium
Algorithms (ESA 2020), volume 173 of Leibniz Inter- national Proceedings in Informatics (LIPlcs). pp. 18:1-18:21, Dagstuhl, Germany, 2020a. Schloss Dagstuhl Seibniz-Zentrun für Informatik. ISBN 978-3-95977-162-7. doi: 10.4230/LIPIcs. ESA.2020.18. 18. URL httpt:httt:s/otttt devopps--vv.... http://oww....oooooooo...oeeaaaa 4230 1230/LIPICSS R.SA.2020.11
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. On Sampling Based Algo- rithms for k-Means. In Nitin Saxena and Sunil Simon (eds.), 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), vol- ume 182 of Leibniz International Proceedings in Informatics (LIPles), pp. 13:1-13:11 Dagstuhl, Germany, 2020b. Schloss
Lea--LLeeiiiizzitieee für Informatik. ISBN 978- 378-3-95977-174- URL httpps://ddrop.ooo da dwg.tuu.ssuu..oo.o..o wtt.ggstttl.../e/puu.eeees
0. doi: /textt//20201325//
vol 1 tteteeeeee222
Rich Caruana, Thorsten Joachims, and Lars Backstrom. Kdd-cup 2004: results and analysis. SIGKDD Explor Newsl, 6(2):95-108 dec 2004. ISSN 1931-0145. doi: 10.1145/1046456.1 1046470. URL
https://doi.coe
104447
Vincent Cohen-Addad and Karthik C.S. Inapproximability of clustering in metries. In 2019 IEEE 60th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 519-539, 2019, doi: 10. 10.11000OCSS.209900000
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard Christian Sohler, and Ola Svensson. Fast and accurate k-means+ via rejection sampling. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural In- formation Processing Systems, volume 33, pp- 16235-16245. Curran Associates, Inc.,
11

---

Published as a conference paper at ICLR 2025
2020. URL https://ppoeediisss.nnno////o//p http:/apppr.aeeeaaaaaaaeaeeaa Filess/paper//220/ File/ BLLp://afftteeeeeSSaeeeccca-----
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 14114224 2012.
Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable ran- domized algorithm for the closest-pair problem. J. Algorithms, 25(1):19 51, October 1997. ISSN 0196-6774. doi: 10. 11.000/jaam.1997.0088 1997. 0873
org wwwp/o......o....oooooo 1000//
João F. Doriguello, Alessandro Luongo, and Ewin Tang. Do you know what q-means?, 2023.
Christoph Durr and Peter Hoyer. A quantum algorithm for finding the minimum, 1999.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014.
R. A. Fisher. Iris. UCI Machine Learning Repository, 1988. DOL: https///bi.ogg/102444///6666
Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. FPT Approximation for Constrained Metric k-Median/Mcamn In Yixin Cao and Marcin Pilipczuk (eds.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), volume 180 of Leibniz International
Proceedings in Informatics (LIPles), pp. 14:1-14:19, Dagstuhi, Germany, 2020. Schloss Dagstuhl- Leibniz-Zentrum für Informatik. ISBN 978-3-95977-11226 doi: 10.4230/LIPIcs IPEC.2020. URL https: /attps://drops..
Christoph Grunau, Ahmet Alper Özüdoğru, and Václav Rozhoñ. Noisy k-Means++ Revis- ited. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman (eds.), 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leib- niz International Proceedings in Informatics (LIPlcs), pp. 55:1-55:7, Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz-Zentrun für Informatik. ISBN 978-3-95977-295-2. doi:
10.4230LLIIIs.BBAA.22235555 URL battps:/arros-deee dev. dagstuhl document 4230 www.:s/III.I..c........ ESA 2023.55
wttp://rooo-eeee...gsuuu.uuu... waagssuuh..deeenitiiee. de/entiiies//////
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 50502, Oct 2009. doi: 10.1 10.1103/PhssRel..e 103. 150502. URL
https:///l aps org/ /o1/ 11 1103 www.hyysew..et.t..ommmome 103. 150522
Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted Voronoi diagrams and randomization to variance-basee k-clustering: (extended abstract). In Proceedings of the tenth annual symposium on Computational geometry, SCG '94, pp. 332-339, New York, NY, USA, 1994. ACM. ISBN 0-89791-6483 doi: 10. 10.1145/177424.1288 178042. URL http::ttt/// /tctp://doi..
org 10. 101111111112221 178042
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple D2-sampling based PTAS for k-means and other clustering problems. Algorithmica, 70(1):22 46, 2014. ISSN 0178-4617. doi: 1007/ (00453-013-9833 URL_attp::/axx.oii.. http://///o..oooooooo//////////0 9833--33----99-3-----99-----333- 9833-9
Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In Christos H.
Papadimitriou (ed.), 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 49: 1-9:11, Dagstuhl, Germany, 2017. Schloss Bagstuhl-Leibniz-eenttu fuer Informatik. ISBN 978-3-95977- 029-3. doi: 10.42300LIPIcs.ITCS..111 Volltexte/2217/6155
URL http:: dagst wt. de/
Jordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q- means: A quantum algorithm for unsupervised machine learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnet (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL http://s//ppppoeeinnnnneeerrrrre papppppeeprrr.ppppsppppappe fwwesfilapppaee fi1ees/papee/2/119/
12

---

Published as a conference paper at ICLR 2025
Niraj Kumar, Romina Yalovetzky, Changhao Li, Pierre Minssen, and Marco Pistoia. Des-q: quantum algorithm to construct and efficiently retrain decision trees for regression and binary classification, 2023.
S. Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982.
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning, 2013.
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Di- dier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised machine learning on a hybrid quantum computer, 2017.
Ruslan Salakhutdinov and lain Murray, On the quantitative analysis of deep belief networks. In Proceedings of the 25th international conference on Machine learning, pp. 872-879. ACM, 2008.
Michael lan Shamos and Dan Hoey. Closest-poine problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp. 151-162, 1975. doi: 10.1 D0.100/SFCS.1177
E. Tang. Dequantizing algorithms to understand quantum advantage in machine learning. Nat Rev Phys, (692-693,, 2022. http://...eeeee/oo...rro///////2
Ewin Tang. A quantum insiiirinniiddddi classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 217?228, doi: URL/ttps:: 1ttp://:://....rg1....1.... http://i...r11111111/11111111111 1tte://...14//331222222 1111/1133327..33111111 3316310
New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 450367055,
10.1145/3313276.33366
Ewin Tang. Quantum machine learning without any quantum. PhD thesis, University of Washington, 2023.
Daniel Whiteson. SUSY.
UCI
Machine
Learning Repository, 2014.
DOI:
http:://b...rr//1.2444////4
Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest-neighhor
methods for supervised and unsupervised learning. Quantum Info. Comput., 15(3-4):1663366
mar 2015. ISSN 1533-7146.
A QUANTUM PRELIMINARIES
In this section. we briefly describe the notions of quantum computing and refer to Nielsen & Chuang (2010) for a more formal and complete overview of quantum computing.
A qubit (quantum bit) is represented by a unit vector (xb) Okg (0) + a (1) where ag: 01 E C are represent the standard basis of the vector space C²(C) i.e, the vector space whose elements are pairs of complex numbers with the underlying field being C.
) and [1]
complex numbers such that |ao|² |ai 12 1 and (0)
Similar to single qubit, an n-qubit system is represented by a unit vector in (C²(C) Sn i.e, as (1)) = Σド"o" a, Ij) where the amplitudes are complex numbers satisfying Σj- |a,12 = 1.
quantum algorithm performs computation qubits by applying quantum gates which repre- can perform the -1
(1
1
sented as unitary matrices. For example, the hadamard gate H
1
mapping (0) J/2 (10) + [1)) and [1) + +/2 (10) [1))-
13

---

Published as a conference paper at ICLR 2025
A quantum state can also be measured in the standard basis. For example, when (جb) du (0) + an (1)
is measured, we obtain with probability jao| and 1 with probability |a1l². Similarly, when (2)
مر aj lj) is measured, we observe the outcome joJi ... In-1, the binary representation of j with probability layl".
2-
In the context of QML, the input data is assumed to be provided in the QRAM data structure. We refer to Kerenidis Prakashi (2017) for the specific details of QRAM implementation. Any vector
v E Idd can be encoded as a quantum state using [log df qubits as ()) = Tiil Σ 2 lj)-
B QUANTUM D2 (PROOF OF THEOREM
We will work under the assumption that the minimum distance between two data points is 1, which can be achieved using scaling. This makes the aspect ratio ( simply the maximum distance between two data points. We will use for an index into the rows of the data matrix V E IR- and j for an index into the rows of the center matrix C E Rexd We would ideally like to design a quantum algorithm that performs the transformation:
( (5) 10) - 11) 1b) (p),
Let us call the state on the right y "eaa)). This is an ideal quantum state for us since | ideat) helps to perform Da-sampling and to find the k-means cost of clustering, which are the main components of the approximation scheme of |Bhattacharya et al. (2020b) that we intend to use. One caveat is that we will only be able to perform the following transformation (instead of the abovementioned transformation)
(x) 1b) 10) + (6) l5) ((ba))
where ((sgg) is an approximation for [D(us, c;)) in a sense that we will make precise below. We will use (reat) to denote the state (t) (j) ()a.)) This state is prepared using tools such as swap test followed by coherent amplitude estimation, and median estimation. Since these tools and techniques are known from previous works Wiebe et al. (213)); Lloyd et al. (2013); Kerenidis et al. (2019), we summarise the discussion (see Section 1 and 4.2 in Kerenidis al. (2019)) in the following lemma.
Lemma 2 Kerenidis et al. 2019) and Wiebe et al. 22155). Assume for data matrix V E R xd and a center set matrix C R that the following unitaries: (i) [i} [0) - (t) (u.). (ti) (5) 10) + ( lcz)
can be performed in time T and the norms of the vectors are known. For any A >> 0, there is
(oogg 3
quantum algorithm that in time O
computes:
(5) 10) + (8) 15) W(ra)
where (bb,)) satisfies the following two conditions for every E [N] and j e [t]:
(i) (Wa)) - |00e) (((r,r))) V2A, and
(ii) For every i, D(u, 9j) E c) Cj),
In the subsequent discussions, we will use T as the time to access the QRAM data structure Kerenidis & Prakash (2117), i.e., for the transitions (i) |0) + (0) (ea) and [j) 10) - lj) (e,) as given in the above lemma. This is known to be T = O(log 2 (Nd). Moreover, the time to update each entry in this data structure is also T = (log" (Nd)). This is the logarithmic factor that is hidden in the Ô notation. In the following subsections, we discuss the utilities of (reat) for the various components of the approximation scheme of Bhattacharya et al. (2020b). During these discussions, it will be easier to see the utility first with the ideal state V ideat) before the real state reat) that can actually be prepared. We will see how (reat) is sufficient within reasonable error bound.
B. FINDING DISTANCE TO CLOSEST CENTER
Let us see how we can estimate the distance of any point to its closest center in a center set C' with t t l centers. We can use the transformation (t) (5) [0) (t) l5) D(e,, c,)) to prepare the following state for any i:
{i) (D(,,, c1)) D D v., 02)) ((v,,.)))
14

---

Published as a conference paper at ICLR 2025
We can then iteratively compare and swap pairs of registers prepare the state (t) [minje|]] ( cz)). If apply the same procedure to [t) (b),1) ... (Vs,,)) then with probability at least (1 2 the resulting state will be {i) minje({] D cj)). So, the contents of the second register will be an estimate of the distance of the 1th point its closest center in the center set C. This further means
that the following state can be prepared with probability at least (1 -22) No
18) min D(ve, P(vr.Gs) [E((
This quantum state can be used find the approximate clustering cost of the center C, which we discuss in the following subsection. However, before we do that, let us summarise the main ideas of this subsection the following lemma.
Lemma 3. There quantum algorithm that, with probability least (1 222) prepares the quantum state ( c) in time O (Tllog 1
B.2 D2 SAMMLLING
D² -ammpining from the point set with respect to a center set E Rxtd with t centers, samples V with probability proportional to minje({) (v,, sy). Let see if we
state [Vc)
-m= [i) minseeq D(e,, cs) useful perform this sampling. If we can pull out the value of VN
the second register as the amplitude, then the measurement will give us close D2-sampling. This is possible since we have an estimate of the clustering cost from the previous subsection. We can use controlled rotations on an ancilla qubit to prepare the state:
N
V sample)
()) (3:10) + VI 111111111))
where B, = gin D(w)ees) 2(
Note that B, S since Ç is the aspect ratio, and by scaling, we assume that ming.j D(c;, 02y) 1 Note that this suggests must know the aspect ratio (or upper bound on the ratio), which should be considered an input parameter. This a standard assumption in parameterised quantum machine learning algorithms such ours (for example, in the HILL algorithm, a bound on the condition number of the matrix is used as a parameter). The probability of
measurement of (i, 0) is minjety D(viey)²
Z SNÇZ. Since we do rejection sampling, ignoring (., 1)'s
AN-C²
that are sampled with probability S (1 (1-82) we end up sampling with a distribution where the 8Ç²
conditional probability of sampling i minzego D(v,,)))? E (1 min D(n,,)) Moreover, +(V.C)
+(V.C)
the rejection sampling gives us a usable sample with high probability in m = O( In 10N) rounds of sampling. This means that points get sampled with probability close to the actual D2-sampling
probability. As mentioned earlier, this is sufficient for the approximation guarantees of Bhattacharya et al. (2020b) to hold. We summarise the observations of this section in the next lemma.
Lemma 4. Let O 8 < 1 and let 2 In 10N. Given a dataset V E R and center set Ce Rixd in the QRAM model, there is a quantum algorithm that runs in time Ô (Tomloog 1 and
with probability at least (1 1/5N) the distance function D 8-close D.
Ntm outputs a sample with DD distribution such that
Proof. The proof follows from Lemma 3 and the preceding discussion.
"The state prepared is actually VN ΣN 10) (a (almingeja) D(v., c,)) (G) with |a/" 2 NA
However, instead of working with this state, subsequent discussions become much simpler if we assume that [Vc) prepared with probability |a|2.
In case scaling only ensures min;,j D(v, m5) 2 (e.g., vectors with integer coordinates), we bound on max,,; D(v, U2) as the parameter instead of the aspect ratio.
15

---

Published as a conference paper at ICLR 2025
The above lemma says that for A Ö NiÇ² ), we obtain the required Da-sample with probability
2 (1 (1-12 1/N). We can now give proof of Theorem [ assembling the quantum tools for D2 -ammlingg in this section. Note that we obtain samples from D distribution such that D is close to D. Using our quantum sampling algorithm to pick & centers in l rounds is not the classical k-means++ algorithm that requires that the samples be picked with D2 distribution and not something close. The resulting algorithm, however, has been analysed in the literature. If the sampling distribution is within (1 d: e) of the D2 distribution, then the algorithm is called the noisy-k +-iissk--eans++++ algorithm Bhattacharyal
it al. (2200a); Grunau ct al. (202)). )). We will use the following result in Grunau et al. (2023).
Theorem 5 (Theorem 1.1 in Grunau et al. (2033 ) The noisy-k-meanst algorithm is O k)
approximate, in expectation.
Theorem I restated below, follows from the above theorem and Lemma Note that the running time of the quantum implementation is Σ, Ō{(²t) = k2)
Theorem (Restatement of Theorem D. There is quantum implementation of k-means++ that runs
in time Ö({² and gives an Ollog k)) factor approximate solution for the k-means problem with a probability of at least 0.99. Here, Ô hides log² (Nd) and log" (kd) terms
C QUANTUM INSPIRED D?-SAMPLING
Ewin Tang's 's thesis Tang (003) nicely categorizes quantum machine learning (QML) algorithms into ones where the quantum advantage (i.e., polylogarithmic running time) is solely because of the quantum access to the data and the ones where is not (e.g., the HHL algorithm Harrow et al. (. Quantum access means that (normalized) data vector 전 == (ø(1), ...., did))" can be loaded onto the quantum workspace in O(1) time as Iu) Ti) [1] + .......... + ((d) d). In this section, we will use the overhead arrow notation for vectors since we would want distinguish between vectors and their approximations using different overhead symbols. One implication of having the quantum
state (u) is that é can be sampled with probability Σ, #G)= by simply making measurement in the
[())2
standard basis. One of the key insights in Tang's 's Thesis Tang (2023) is that QML algorithms that we work with an appropriate classical counterpart of the quantum data access that allows sampling access of the kind described above (in addition to the classical access to the data). This is called sample-que quell- access, or SQ access in short. Dequantization means that classical algorithm simulate the steps of the quantum algorithm using SQ access with similar running time dependence. The nice property of the SQ access data structures is that can be constructed classically linear time. Note that linear time means that we lose the quantum advantage. However, if we keep this aside and count the SQ access data structure construction as preprocessing, the remaining computation has similar advantage as that of the quantum algorithm. This is level playing field with the QML algorithm that allows fair comparison, specifically given that setting up quantum access (called QRAM) also takes linear time. Such classical algorithms obtained by dequantization are called quantum inspired algorithms. Our quantum algorithms based on D2 De-sampling fall into the category of QML algorithms that can be dequantized in Tang's SQ access model. This section discusses the quantum quantum-inspired classical algorithm we obtain by dequantizing our quantum algorithm using the SQ access data structure. Naturally, we start the discussion by looking at the definition of the SQ access data structure.
benefit solely from the quantum data access can be 'dequantized"
Definition 3 (Query access, Definition 1.1 in Tang (002)).. For a vector T E C", we have (ŪT), query access to V, for all i [m]. we can query for (i). The time (cost) of such a query denoted by q(T).
Definition 4 (SQ-access to a vector, Definition 1.2 in Tang 2023 For a vector T E CD, we have SQ(T), sampling and query access to T, if we can:
1. query for entries in T as in Q(T). The time cost is denoted by q(T).
2. obtain independent samples i E [n]] where the probability of sampling i is distribution is denoted by Dz. The time cost is denoted by S(ū).
#() TØ This
Thhe output of k-means++ is a subset of data points, which can be stated as subset of indices. If the description of centers is the expected output, the running time will also include factor of d.
16

---

Published as a conference paper at ICLR 2025
3. query for ||0|| The time cost is denoted by n(ū).
Let (Q = max (q(T), } denote the time cost of SQ-access.
In quantum computation an n-dimensional state vector (b)) evolves using unitary transformations (bi)= - (oo), where U is 2n x 2" unitary matrix. To be able to simulate such operations within the SQ-access model, we must make sure that SQ-access available for intermediate states of the quantum operation. This means that we must (i) define appropriate SQ-access notion for matrices and (ii) show closure properties for SQ-access. Fortunately, this has been shown in Tang's ' Thesis Tang (2023. A more flexible version of SQ-access is needed to show closure properties. This is called oversampling SQ-access. SQ-access for matrices and oversampling SQ-access is defined below.
Definition 5 (SQ-access to a matrix). For a matrix A Cm we have SQ(A) if we have (Q((()))) for all E [m]] (i.e,, SQ-access to the row vectors), and SQ(ā), where ā is the vector of row norms of A (i.e.,
(IA(1, I)I,, .... || )))""), The complexity of operations on matrix is defined as: ((A) max {q(A(ti, -),, (()),, n(A) = n(ā), s(A) max (s(A(i,) ()) s),,) }. and
sq(A) == max {A),, n(A), s(A)
Definition 6 (Oversampling and query access: Definition 4.4 in Tang (023 For i E C and e 2 I, we have (Q²( d-oversampling and query access to 8 (Ø-OSQ access, in short), if
have ((T) and SQ()) for e C vector satisfying (i) || क|[لا and (ii) (ō(1)) 2 [8(1))2 for all E [n]. Denote (T) == s(i), (ū) = ( n (7) = n(o), and sq (T) = max (V), 90 (()) (v))
Note that Dj for ū be seen as oversampling distribution of Dz by factor of d. This is because the sampling probability of index i is given by
(()) |
(0)12 2
T()) 2 De(1) "|ج
(1(1)
<-OSQ access also allows one to sample from D3 and find |ل by paying small time penalty (as function of and allowed error). This is captured in the following lemma from Tang (2023).
Lemma 5 (Lemma 4.5 in Tang 2023)). Let < 8 S. 1 and 0 < 1. Suppose we given (Q) Then can sample from Da with proability at least (1 5) in time O (Ø (g) loog 2)) We can also estimate time.
|| within (1 + a) factor with probability least (1 (1-5) O 2 sq log }
We can also define oversampling query access to a matrix.
Definition 7 (Oversampling and query access for matrix). For matrix A E CNxd and Φ 2 1, we have SQ&(A), d-oversampling and query access to A (ø-OSQ access, in short), if we have ((A) and SQ(A) for Á E Nxx satisfying
|
l|Al and (A( 2 [A( for all (i,5) E [N] x [d]. The d-oversampling complexity is given by sq (A) = max sq(A))s((A))
There is a simple tree-based data structure that supports sample-query access for vectors and matrices. The details can be found in Tang (2023). Here, we give summary of the running time of various operations.
Lemma (Remark 4.12 in Tang 2023 ) There is data structure for storing a vector ō e E2 with supporting the following operations:
1. Reading and updating an entry of in Ollogn) time. So, q Ologn).
2. Finding || in O(1) time. So, n( (T) (1).
3. Sampling from De in O n) time. So, s(ū) = (logn)
It follows from the above that sq(T) O(logn). Moreover, the time to construct the data structure
is (n).
similar lemma holds for storing matrices.
17

---

Published as a conference paper at ICLR 2025
Lemma 7 (Remark 4.12 in Tang 2023 For any matrix A Rmxn, let À denote the vector of row norms of A, L.e., the 8th entry of A, denoted by A(i), is [|A(i,))]|: There is data structure for storing a matrix A E Imxx with supporting the following operations:
1. Reading and updating an entry of Olog mn) time.
2. Finding A(i) in Ollog m) time.
3. Finding || in O(1) time.
4. Sampling from D A and D Dat..) in Ollog mn) time.
The time to construct the data structure is ((m)).
Let us now see how De-sampling can be done using the above SQ-access data structures. Let V E RNxd xd be the data matrix with the row vectors "., UN as data points. Let C E R be the center set matrix with the centers being the row vectors č ... Gn. Consider D2-sampling a point from V with respect to the center set C. The probability of sampling the tt point is given by:
miDee(m]
1 - all
Pr[
Consider vectors wi;;.. .. Wm E R-W defined
T == (1 1|1. 11 - Gll,..,, 1 Z,)T"
The first step towards samplingg using the SQ-access data structure for matrices V and C is to check whether SQ-access for vectors wi,.... Fm can be made available. In the next lemma, we show that d-oversampling SQ-access for appropriately chosen value of á is possible.
Lemma 8. Let a-oversampling SQ access to the data matrix V E N be available as SQa (V) and let 3 oversampling SQ access be available for a vector E e Rdd as SQ,(C). The we have ? oversampling SQ access, SQ, (w)), for vector w (I)V - c .... IIV =Tl with 7 + NN Moreover, the complexity related as sq, (17) d. (sq. (V)+sq((C)
Proof. (V) means that Q(V) and SQ(V) available for matrix V such that (i) ||t||/=
a||V]| and (ii) (V1,))) 2 (V(,))) for all (i.j) E [N] x [d]. Similarly, SQ means that Q(2) and (Z) are available for a vector ē such that (i) ||ā]| B||c| and (ii) |ē(t) 2 lé(t)) for all t e [d). To show SQ,(w), we first need to show Q(w)). This is simple since the jth coordinate of w can be found using all the coordinates of V (j..) and ē which are available since we have Q(V) and Q(c). So, q(w)= d (q(V) + q())). We now need to show 5Q( for an appropriately chosen w.
We consider:
m - - 2 (I/CG.)) + (lal
Before we see why SQ access to vi is possible, let us first observe that SQ( would give 7- oversampling SQ access to W. Towards this, we note that
|| Σ |0)) Σ (1V6..) + +Tale)
2 | (allVI2+ -331017)-11 =
Moreover, we have:
| = -|V - $ IV -||| < V
s V (1123.)) >I + [1a)2) |()(
Finally, we must show SQ( Coordinates of à can be found using | and ||ब|| which
are available through oversampling access to V and こ || is available through ||0|1" and ||ā]|
18

---

Published as a conference paper at ICLR 2025
|
Finally, Da can be sampled by first selecting V with probability
+M]ial or with probability
NiJ@ and then sampling from Dj or [[j] (uniform distribution over [N]), respectively. Given
this, the probability of sampling works out to be:
((..)
2
1
i(1)² |011² (i)
pr(
|
|
N N
From the above discussion, it follows that sq, (w, S d (sqa (V) + Scg
The previous lemma gives a way obtain oversampling query access distances from single center. In -ammmpiinng, we have a set C' of m centers, and we sample a point based on the squared distance from the nearest center. To enable this operation in the SQ framework, query access to a vector where the jth coordinate is the distance of 7th data point to the nearest center in C. In the following lemma, we show how to do this. The proof closely follows Lemma 4.6 of Tang (2023).
need sample and
Lemma 9, Let 1n Um E (IR2U)N and @1y Om R22 Let
min Th (1), min (2) min (.)) (E(m)
iE(m]
sE(m)
Suppose have SQ (17,) for every i [m]] Then there d-oversampling query access, SQo(T) for o- Eigim dh d.11%;11 Eietml 9s. (it,), no n m||10 after a single-time pre- pre-processing cost of Eie(m) no: (T,)-
The complexity is give by: q(ı) = Eie(m) q(ū,), qg(w)) Eielm no. (ū,)) The sampling complexity is s (ī)) max4e(m] So. (1,).
Proof. We need to show Q (w) and SQ(w) for an appropriate w. We can respond to each coordinate of w by querying ū. and taking the minimum. This gives q Eie(m) q(ū.). Let u1 ..., Um be the vectors corresponding to the oversampling access SQ (ūn). SQ am (im) For oversampling query access, consider:
(i)
1
Σ (1)2. JE(m)
Each coordinate of w can be found by querying u, 's and computing the above expression. So, have Qw)) and qs (iT) = Eie(m) 9s. (1t). The norm of w is given by:
|
Σ
Σ 2,()1) = m
Σ JELm]
Σ , L
|| = 00 [|]
m
m ml|wul|
JE(m]
JE[m]
So, we can query the norm of Ø by querying the norms ūz's. Hence, no(w7) Eje(m) nøy (7y( Now, we need to show that (i) upper bounds wii). We have:
(
1
10PP>
Σ min by (1) min (i) > min (i) wi)). j'E(m]
j'(mm]
JELM
jElm]
Now we describe how to sample from D.a We first query the norms of यر. We pick a j E [m]] ||,,||
with probability Eye(m) | and then sample an index i E [N] from the distribution Dū,- The
probability of sampling an index i is given by:
|
(i) |
m E Eje(m) 1,y(1)2 ( 1
Pr[j Σ
jE(m] E, Ey |1
E
| 1
||
m
This is the correct probability for sampling from Da- Note that from the description, the sampling complexity is sı(w) maXic[m] So. (u,), after single-time processessnngg cost of Eie(m) no, (ū,)
n
19

---

Published as a conference paper at ICLR 2025
We now have all the basic tools to perform D2 sampling in the SQ access model and evaluate its time complexity. In the remaining discussion, we will assume that the origin is centered at one of the data points that the maximum norm of data vector is upper bounded by the maximum interpoint distance.
Theorem 6. Let O < < Let V E Nxd be the datasel and let Gi.-.,.mm Em E RRd be m arbitrary centers from the dataset and let SQ(V) and SQ(ā),.... SQ((m)) be available. Let denote the aspect ratio of the dataset (i.e., the ratio of the maximum to minimum interpoint distance). Then there is a classical algorithm that with probability at least (1 8) outputs a sample from the D²-distribution (i.e., DD-sample) of V with respect to centers {T,,..., ..... Eml which runs in time 2) log Nd).
Proof. Let dnorm be the maximum norm of a data point. Let dmin and dmaw be the minimum and maximum distance between two data points, respectively. Then, we have Ç =
dmsse.
2 dgarm. Let us dmnin
dmin
define vectors .i.. tm where (i) == []V -5yl- Using Lemma g
we can enable SQ,, (ū₂)
for every j E [m]. for Φj = || 2 (IV 2 + Ni 11 Lemma gives a way to define SQ where
T. is defined as (i) == min JT, (t) and Φ Σj " Note that for the w defined, Di is precisely the D2 distribution over V with respect to centers č .... Cm and from Lemma m
m 1t
we know how to use (Qo(w)) to sample from Dar with probability at least (1 - 6) in time Oe sq. (7) log $
For calculating the complexity, we first get a bound on dz
Eje(m)
O5 الااي m||
EjE(i |o (IIVI2 + N |1 1|
2 | |
2N
m||05||
JE[m]
The tt coordinate of it is the least distance of (i.,.) from a center. This gives us || 2
(N m) di Also, ||V S N and 11 I dh norm Putting these bounds in the above
equation (and that m S N/2), we get Φ S 8 norm
de
S 8C2. From Lemmas and we have
d2
(V) O(log (ī = Ollog d). From Lemma
g we have sq (ū,)
(sq(V)
sq(T)) = Od Nd) for every j E [m]] From Lemma we have sq (w) Σ, jm(mm sqs, (T,) =
Omd Nd). So, from Lemma the complexity of D -ammling point is 0(0-sq (w) log $)
mddloo )) log Nd).
The k-means++ algorithm is simply D²-sampling centers iteratively while updating the list of centers. We summarise the discussion of this section by giving the complexity of the k-means++ algorithm and the proof of Theorem 2
We restate the theorem for ease of reading.
Theorem (Restatement of Theorem 2 There is a classical implementation of k-means++ + (which we
call Ql-kk-mens++)) that runs in time ((Nd) + Ō((²k²d). Moreover, with probability at least 0.99, Ql-k--means++ outputs is centers that give Ollog k) -apprxximation in expectation for the k-means problem.
Proof. The Nd term in the running time expression is for setting up SQ(V), the sample-query access to the data matrix V. This may also be regarded as the preprocessing step. This is followed by D2 D?-sampling & centers iteratively while updating the set of centers by including the new centers sampled. From the previous theorem, we know that when we have m centers, the cost of obtaining a Damsample is O(("md((og 4) log Nd) with probability at least (1 - 8). To obtain an overall probability of success of 0.99, we need to have success probability of at least 1 O(1/k) in each iteration. This makes the overall D2 -ampling cost xf d log & log Nd). So, the overall time complexity of Ql-k-means++ is O (Nd) + 22 Since with probability at least 0.99, we obtain k perfectly D2 -ammled center, the approximation guarantee remains the same that of k-means++ which is O k) 10
What happens with the remaining 0.01 probability? D²-sampling in the SQ model succeeding with probability at least (1 - 8) means that with probability at least (1 - 6) center is sampled with 2 distribution, and with the remaining probability, no point is sampled.
20

---

Published as a conference paper at ICLR 2025
C.I QUANTUM INSPIRED APPROXIMATE D2- SAMMPLING
Sampling from a distribution that is E-close to the D distribution is sufficient to obtain (log k) approximation. This follows from the analysis of the noisy-k-means++ algorithm Grunau et al. (2023). This relaxation (without any approximation penalty beyond constant factors) allows to shave off the factor of from the time complexity of the quantum-inspired algorithm. However, as we will see in the analysis of this section, it is at the cost of worsening the dependence on the aspect ratio. So, the algorithm in this section should be used for high-dimensional cases where the aspect ratio is small. The factor of d in the sampling component of Ql-k-means++ appears because for enabling the oversampling and query access for the vector ui == (I)V(1,, .) e .... [V.... =ll" (E's a center), we need to access the d coordinates of (i...) and Eo be able to answer the query access to the zth
index of ni, which is [V( T Note that [V((,,) ল = VIV
||ा (i,
where (V, Z) denotes the dot product. The terms [V )1 and || are available in O(1) time. The dot product term costly and adds a factor of d. So, the key idea in eliminating the factor of d is to replace the dot product term with appropriate approximation that requires much smaller access time. This uses the standard sampling trick randomly sample a subset indices, compute the dot product restricted to these indices of the subset, and scale (see Lemma 5.17 in Tang (2023). ). The number of indices we need to sample to ensure that the resulting approximation within (1 E) of (i, こ for every i with probability at least (1 -1- 6) Ô
log (1/0)
| [V()))--
δ 5* (1"lng log 1/66 The remaining steps are the same as those in the exact version, except that replaced with Ô (1llog ) This results in the overall running time O(Nd) + Ô (5
D A QUANTUM APPROXIMATION SCHEME (PROOF OF THEOREM
We start the discussion with the Damsampiing method. In particular, we would like to check the robustness of the approximation guarantee provided by the D²-sampling method against errors in estimating the distances between points. We will show that the D D?-sampling method gives constant pseudo- aaaddoo-ppoiittionn even under sampling errors.
D.1 PSEUDOAPPROXIMATTION USING D7-SAMPLING
Let the matrix V E Nxd denote the dataset, where row i contains the zth data point U; E Rdd Let the matrix C E Rxd denote any t-center set, where row i contains the 8th center G; Rd out of the / centers. Sampling a data point using the D distribution w.r.t. (short for with respect to) a center set C' means that the datapoint v; gets sampled with probability proportional the squared distance to its nearest center in the center set C. This is also known as D2 sampling w.n.t. center set D' C)) Σ, D" (v,, where Du C) = mineec D2 (v, c). For the special case C' = 0. D2 sampling is the same as uniform sampling. The k-means++ seeding algorithm starts with empty center set C and, over k iterations, adds a center to C' in every iteration by D2 sampling w.r.t. the current center set C. is known from the result of Arthur & Vissilvitskii (2007) that this k-means++ algorithm above gives Olog k) approximation in expectation. It is also known from the result of Aggarwal et al. (2009) that if 2 centers are sampled, instead of k (i.e., the for-loop runs from to 2k), the cost with respect to these 2k centers is at most some constant times the optimal k-means cost. Such an algorithm is called a pseudo approximation algorithm. Such a pseudo approximation algorithm is sufficient for the approximation scheme of Bhattacharya et al. (2020b). So, we will quantize the following constant factor approximatooiiiiooonn algorithm.
D²(w).))
C. More formally, data points are sampled using the distribution [E DE,,,c,
In the quantum simulation of the above sampling procedure, there will be small errors in the sampling probabilities in each iteration. We need to ensure that the constant approximation guarantee of the above procedure is robust against small errors in the sampling probabilities owing to errors in distance estimation. We will work with relative error of (1 + 6) for small 8. Following is a crucial lemma from Arthur & Vassilvitskil (2007) that will need to show the pseudo approximation property of Algorithm I.
21

---

Published as a conference paper at ICLR 2025
Algorithm 3 A pseudo-approximation algorithm based on D Dsmmmpiing.
Input: (V.k) C+ 0
for to 2k: do Pick e using Di-sampling w.r.t. center set C
:= {c}
end for return C
Lemma 10 (Lemma 3.2 in Arthur Vassilvitskii (2007)). ) Let be an arbitrary optimal cluster, and let C' be arbitrary set of centers. Let c be center chosen from A with Da-sampling with respect to C. Then [lcoos(A, {c}) S 8 < (A)..
The above lemma used as a black box in the analysis of Algorithm in Aggarwal al. (2009). The following version of the lemma holds for distance estimates with relative error of (1 + 6) and gives a constant factor approximation guarantee. Since Lemma i0 is used as a black box in the analysis of Algorithm 1, replacing this lemma with Lemmal IT also gives constant factor approximation to the k-means objective. We will use the following notion of the closeness of two distance functions.
Definition distance function D1 is said to be 8-close to distance function D2, denoted by D1 ~ D2, if for every pair of points z, y E Rd, (1(x, y) E (1 D2(2z, y) [1]
Lemma 11. Let 0 < 8 S 1/2. Let A be arbitrary optimal cluster and C be an arbitrary set of centers. Let e be a center chosen from A with DD -asmpling with respect to C, where D mug D. Then Elcost(A, A, U [c})] < 72 OPT(A).
Proof. Let D(a) denote the distance the point from the nearest center C and let D(a) denote the estimated distance. We have D(a) D(a) =1=6), The following expression gives the expectation:
Σ Da(n))
Σ min ((dd
RDEA EaEA (2(
a'EA
Note that for all a E A, D(ao) < D(a) + D(a,aa),
This gives D(ao) <
I-3 D(a)
1+5
(1 + 6) D(ao, a). which further gives D2 (ao) 2
[-8
1+0
D²(a) 2(1 + 8)2 D2 a) and
(²)( S [ (1²) EaEs (a) + 2 (1 + 8)3 E.EA D² a). We use this to obtain the
A
following upper bound on the expectation [E[oos(AA (c])]:
(au
Σ
Σ min (2''a')
EOEA
(2(
a'EA
SHEEDD(()) A 1-8
min (dda +
EnEA (a)
A
a'EA
2 + 8)2
EnE D2 D2(00,
min (D²(a'), (d')
EeEA (a)
A
a'EA
<
Σ
Σ
2
1 1+0
(2' an) + Σ
11+0) 2
D(ao, a)²
A
1-8
A
1 1-
apEAd A'EA
an EEEA
4
1+0
Σ
Σ
(a a)
=
A
1-8
AEEA
We use the notation that for positive reals P,Q, P (000000000000000(0000-0000--0000
22

---

Published as a conference paper at ICLR 2025
1+8 2
8
1-8 (PT(A)
s 72. OPT(A).
This completes the proof of the lemma.
We will use this lemma in the approximation scheme of Bhattacharya al. (2020b). However, this lemma may be of independent interest as this gives a quantum pseudo approximation algorithm with a constant factor approximation that runs in time that is polylogarithmic in the data size and linear in and d. We will discuss this quantum algorithm in the next section.
D.2 APPROXIMATION SCHEME OF BHATTACHARYA ET AL.
2020B
high-level description of the approximation scheme of Bhattacharya et al. (020b) was given in the introduction. A more detailed pseudocode is given in Algorithm In addition to the input
Algorithm 4 Algorithm of Bhattacharya et al. (0206). For our Quantum application, we will replaces
D with 5-close D.
1: Input: (V, k, E, Cinit), where V is the dataset,
is the number of clusters, 0 is the parameter, and Cinat is a k center set that gives constant (pseudo)approximattin
2: Output: A list [ of k center sets such that for at least one C² E C, (V, s (1 ()) OPT.
3: Constants: p ( ( O+
4: L + 0; count +-
5: repeat
6: Sample multi-set M of pk points from V using D'-sampling wrt center set Cinit
7: . +- M U (Tk copies of each element in Cinit)
8:
for all disjoint subsets Si..., S5 of M such that |S: do
9:
C Lu (u(Si),.... (((x))
10: end for
11: count++
12:
until count < 2
13:
return
instance (V, k) and error parameter e, the algorithm is also given a constant approximate solution Cinit, which used for Damsampling. pseudoapproximate solution Cinit is sufficient for the analysis in BBhatatcharya et al. (2020b). The discussion from the previous subsection gives robust algorithm that outputs a pseudoapproximate solution even under errors in distance estimates. So, the input requirement of Algorithm 4 can be met. Now, the main ingredient being D*-sampling, need to ensure that errors in distance estimate do not seriously impact the approximation analysis of Algorithm 4 We state the main theorem of of BBhattccharya al. (2020b) before giving the analogous statement for the modified algorithm where D is replaced with 2 that is d-close to D.
Theorem (Theorem 1 in Bhattacharya et al. (020b)). Let < E S 1/2 be the error parameter, V N be the dataset, k be positive integer, and let Cinit be constant jaseudo)approxingg solution dataset V. Let C be the list returned by Algorithm oon input (V, k, Cinst) using the Euclidean distance function D. Then with probability least 3/4, L contains a center C such that (VV C) < (1) OPT. Moreover, |C|= Ô (20(t) and the running time of the algorithm is (l)
We give the analogous theorem with access to the Euclidean distance function D replaced with a function D that is 8-close D.
Theorem 8. Let 0 < 1/2 be the error parameter, << 5 1/2 be the closeness parameter, VE E Nxd be the dataset, k be a positive integer, and let Cinit be constant (psendo))aproxiimat solution for dataset V. Let L be the list returned by Algorithm 4 input (V, k. e, Crast) using the distance function DD that is 8-close to the Euclidean distance function D. Then with probability at
least 3/4, C contains a center set such that (VV C) & (1 (e) z). OPT. Moreover, [C] = 20(5) and the running time of the algorithm is O(N
23

---

Published as a conference paper at ICLR 2025
The proof of the above theorem closely follows the proof of Theorem 7 of Bhattacharya al. (2020b). This is similar to the proof of Theorem thhtt we saw earlier, closely following the proof of Lemma I0 The minor changes are related to approximate distance estimates using D instead of real estimates using D. The statement of Theorem Biss not surprising in this light. Instead of repeating the entire proof of Bhattaccaa using D instead of D as the distance function. The analysis of Bhattacharya et al. (2020b) works by partitioning the points in any optimal cluster X; into those that are close to Cinit and those that are far. For the far points, it is shown that when doing D2 Ds-sampling, far point will be sampled with probability at least 7 times the uniform sampling probability (see Lemma 21 in Goyal et al. (2020), which is a full version of BBhattacharya D² -amslede points will contain uniform sub-sample. A combination of the uniform sub-sample along with copies of points in Cinat gives good center for this optimal cluster Xj. Replacing D with D decrease the value of y by multiplicative factor of (1-8)²
al. (2020b), we point out the one change in their argument caused by
al. (2020b)). It then argues that reasonable size set of
(1+0)2 2 (1 5)2. This means that the number of points sampled should increase by a factor of O (1- ). This means that the list size
Note that when < 1. the list size and running time retain the same form as that in Bhattacharya al. (2020b) (i.e., [ = 2015) and time O(Nd) A detailed proof of Theorem 8 is provided in the next section of the Appendix.
increases to Ô
D.3 THE QUANTUM ALGORITIIM
The main idea of the quantum version of the approximation scheme Bhattachaaa et al. (2020b) is to DP-sample set S of poly(k/e) points with respect to a center set Cinit that gives constant approximation to the k-means objective. We then try out all various subsets of possibilities for the k center set out of S and Canit and then find the one with the least cost. Centt is itself found quantumly by iteratively De-sampling 2k points. So, most of the quantum ideas developed for the quantum version of k-means++ can be reused in the quantum approximation scheme. An additional effort is in to calculate the k-means cost of a list of I, = 20(t) k-center sets and pick the one with the least cost. Here, instead of adding the relevant steps only, we add all the steps of the quantum algorithm for better readability.
We will work under the assumption that the minimum distance between two data points is which can be achieved using scaling. This makes the aspect ratio ( simply the maximum distance between two data points. We will use for an index into the rows of the data matrix V E N and j for an index into the rows of the center matrix C E 22kxd, We would ideally like to design quantum algorithm that performs the transformation:
10) 15) 10) + 10) (P)
Let us call the state on the right V i. This is an ideal quantum state for since | (Videa)) helps to perform Da-sampling and to find the k-means cost of clustering, which are the main components of the approximation scheme of Bhattcharya et al. (20205) that we intend to use. One caveat is that we will only be able to perform the following transformation (instead of the abovementioned transformation)
18) 15)) 10) + 10) 15) ((
where (&/gg) is an approximation for (D(us, c3)) in a sense that we will make precise below. We will use (reett) to denote the state (o) (i)) (v.s)) This state is prepared using tools such as swap test followed by coherent amplitude estimation. and median estimation. Since these tools and techniques are known from previous works Wiebe et | (2015): Lloyd et al. (201)); Kerenidis et al. (2019), we summarise the discussion (see Section 4.1 and 4.2 in Kerenidis et al. (2019) in the following lemma.
Lemma 12 (erenidis et al. 2019) and Wiebe al. (2015). Assume for a data matrix V e R x and a center set matrix C E ka that the following unitaries: (i) (E) |O) + (i) (u.), (ii) l5) (0) + (5) lc,) can be performed in time T and the norms of the vectors are known. For any A > there
quantum algorithm that in time O
Tlog *
computes:
10) b)) 11)
where (ibe)) satisfies the following two conditions for every E [N] and j [1]
24

---

Published as a conference paper at ICLR 2025
(i) [(a.s) - (o8r) ((())))))))))))))))))) v2A, and (ii) For every i, D( 9j) E (1 -((,,,))
In the subsequent discussions, we will use T as the time to access the QRAM data structure Kerenidis Prakash ). i.e. for the transitions (t) [0) + (8) (oa) and (5) (0) + (à) lcy) as given in the above lemma. This is known to be T = O(log (Nd)). Moreover, the time to update each entry in this data structure is also T = (log (Nd)). This is the logarithmic factor that is hidden in the O notation. In the following subsections, we discuss the utilities of (reat) for the various components of the approximation scheme of Bhattacharya et al. (2020b). During these discussions, it will be easier to see the utility first with the ideal state L sdeat) before the real state | reat) that can actually be prepared. We will see how reat) is sufficient within a reasonable error bound.
D.4 FINDING DISTANCE TO CLOSEST CENTER
Let us see how we can estimate the distance of any point to its closest center in a center set C = Canit with /. == 2k centers. We can use the transformation (i) l5) 10) (i) li) (y),, to prepare the following state for any
(i) (vs, et)) (D(,, ... ((v,,
We can then iteratively compare and swap pairs of registers to prepare the state (i) mmnneey D(v,, Gy)). If we apply the same procedure to |i} ( )) l(br,), then with probability at least (1 - 2A);, the resulting state will be [i) minje(1) D(v, cz))- So, the contents of the second register will be an estimate of the distance of the 2th point to its closest center in the center set C. This further means
that the following state can be prepared with probability least (1 222 N2
NV
1
min D(vi, e)). jEM
11)
This quantum state can be used to find the approximate clustering cost of the center set C, which we discuss in the following subsection. However, before we do that, let us summarise the main ideas of this subsection in the following lemma.
Lemma 13. There is quantum algorithm that, with probability at least - 1-2) prepares the Ti log
quantum state () in time O
D.5 COMPUTING COST OF CLUSTERING
Suppose want to compute the k- k-means cost, $(V,C) = minzet1) D² Cj), of the cluster- ing given by a / center set C. We can prepare m copies of the state (V)) and then estimate the cost of clustering by measuring m copics of this quantum state and summing the squares of the second registers. If m is sufficiently large, we obtain close estimate of (V,CC). To show this formally, we will use the following Hoeffding tail inequality.
Theorem 9 (Hoeffding bound). Let X1,..., -.. Xm be independent, bounded random variables such that X, E [a, b). Let S., = X1 +... + Xm Then for any O > O, we have:
Pr[[Sm E[S 0 < 2- m()-ay=
Let XI...., Xm, denote the square of the measured value of the second register in (ee) These are random values in the range x", where X max:,j (v,, <;) E (1 + e) maxi,j D(v, vy). Note So, X can be upper bounded in terms of
that by scaling, we assume that min;,; D(v,, v,) the aspect ratio Ç as X S 20 First, we note the expectation of these random variables equals
Σ (V) (<e minneet ((v..c)) 8|G)) with |a| (1 N1 However, instead of working with this state, subsequent discussions become much simpler if we assume that [Pc) prepared with probability ja|?. II cases scaling only ensures min;,j D(v, v.)) > 1 (e.g., vectors with integer coordinates), we m D(v vy) the parameter, instead of aspect ratio.
Thee state prepared is actually
/
25

---

Published as a conference paper at ICLR 2025
((V.C) N where ((VC))= = Ein gingett D(u, Sm. X1 + X2 ... + Xm and apply the Hoeffding bound on these bounded random variables to get a concentration result that can then used.
$(V, C). We define the variable e)² (1 (1
(
( la (1 then we have:
Lemma 14. Let amm = Sm and > 0. m== =
Pr|am E (1 a) (V, 21 5L
Proof. We know that [[S..]] m N (V,C) From the Hoeffding tail inequality, we get the following:
Pr[[Sm E[Sm]] 2 E [m
S 2 e
mc
2. 2 (5x))2
2 Ia (10L) 5 5L
This implies that:
1
Pr[lam- 6(VC)) ((V
3T.
This completes the proof of the lemma.
So, conditioned on having m copies of the state (V,., we get an estimate of the clustering cost within
relative егrоr of (1 + e) with probability at least (1 5T. Removing the conditioning, we get the
estimation technique to calculate the cost for a list of center sets C1 .... Cr, and then pick the center set from the list with the least cost. We must apply the union bound appropriately to do this with high probability, We summarise these results in the following lemma. Let us first set some of the parameters with values that we will use implement the approximation scheme Bhattacharya al, (2020b).
same with probability at least (1 2A)Nkm. (1 ) )- We want to the above
L denotes the size of the list of k-center sets will iterate over to find the with the least cost. This quantity is bounded as L = O(5)
m is the number of copies of the state <* In (101) where ( (1 8) maxi.j D(v,, -²
( made to estimate the cost of the center set C.
This, as given Lemma 14 is m
Lemma 15. Let I. T= (+) 0($) m (100)) and A= ( Given point set V and a list of center sets Ci...., Ct in the QRÅM model, there is a quantum algorithm that runs in time ò (20(ETCC) and outputs an index I such that (VV Ct) S (1 + e)s minjer. $(V, C2) with probbaility at least z.
Proof. The algorithm estimates the cost of Ci,... Cr. using m copies each of | ,.., (ey) and Plugging the values of L, m, and
picks the index with the minimum value in time O (TemL log c
A we get the running time stated in the lemma.
Let us bound the error probability of this procedure. By Lemma 3 the probability that we do not have the correct m copies each of (V,)...., ...., (V,,) ) is bounded by (1 22 2 Conditioned on having [V,)) ...., Vc,)). ). the probability that there exists an index j E [Z]. where the estimate
off by more than (1 + ) factor is upper bounded by by the union bound. So, the probability that
the algorithm will find an index such that (VV, Ct) (1 + e)3 minje((] ΦVV, C₁) is upper bounded
by (1 22) 2A)NAmL Nkmz + This probability is at most g since O wk-zz) This completes the
proof of the lemma.
D.6 D2-SAMPLING
D2 samslingg from the point set V with respect to a center set E Rixd d with t centers, samples e with probability proportional minje(g D2 (v cz). Let see if we our state (Vc)
(1),,)))
26

---

Published as a conference paper at ICLR 2025
1. -E=100 jin D(e,,))) is useful to perform this sampling. If we can pull out the value of VN the second register as the amplitude, then the measurement will give us close to Damsampling. This is possible since we have estimate of the clustering cost from the previous subsection. We can use controlled rotations on an ancilla qubit to prepare the state:
v @eampte)
Σ
( (3x10) + VI 18//111).
where B; minjete D(v..e)) So, the probability of measurement of (i, is minjeld D(vr,es)) Since 4ç2-b(V,C)
we do rejection sampling, ignoring (.,1)' that are sampled with probability S (1 as²) we
end up sampling with a distribution where the probability of sampling i is minjejy D(ui,e,) +(V.C)
(1 =)+ minzels D(el.e)) Moreover, we get a usable sample with high probability in at most +(V.C)
O(ς2 log 10.N) rounds of sampling. This means that points get sampled with probability close to the actual De-sampling probability. As we have mentioned earlier, this is sufficient for the approximation guarantees of Bhattacharya et al. (2020b to hold. We summarise the observations of this section in the next lemma.
Lemma 16. Given dataset V E Nxxd and center set C Rexd in the QRAM model, there is quantum algorithu that runs in time O
TtmS log and with probability at least (1 22) Ntms
outpuss S independent samples with D2 distribution such that the distance dusttineeuunction DD is 8-close to D.
Proof. The proof follows from Lemma and the preceding discussion.
The above lemma says that for A Nem ).
we obtain the required samples with high probability. We can now give proof of Theorem assembling the quantum tools of this section. We restate the theorem below for case of reading.
Theorem (Restatement of Theorem Let < < 1/2 be the error parameter. There quantum algorithm that, when given QRAM data structure access to a dataset V E RN runs time Ô (20(t)ç((()) and outputs a center set C Rxxd such that with high probability (V, (1+ -PP..P.... Here, Ç is the aspect ratio, i.e., the ratio of the maximum to the minimum distance between two given points in V
Proof of Theorem The first requirement for executing the algorithm of Bhatttchary et al. (2020b) a constant pseudo approximation algorithm, using which we obtain the initial center set Cinit- By Lemma we know that 2k points sampled using D2 D2-sampling give such a center set. From
this can be done quantumly in time Ö( ((kc 22 The algorithm of Bhattacharya et al. (020bb has an outer repeat loop for probability amplification. Within the outer loop, poly(E) points are D De-sampled with respect to the center set Cinit (line 6). This can again be done quantumly using Lemma 16 in time (k/=s
Lemma 16
We can then classically process the point set M (see line 7 in Algorithm 4 and create the QRAM data structure for the list Ci.... Cr. of k-center sets that correspond to all possible disjoint subsets of M (see line in Algorithm 4. This takes time
Ö(Lkd), where L (b) Theorem 8 shows that at least one center set in the list gives (1 + =)- approximation. We use this fact conjunction with the result of Lemma to to get that the underlying quantum algorithm runs in time Ö(20()) (1)) and with high probability outputs center set C such that (VV C') < (1 e OPT
Whe Ô notation hides logarithmic factors N. The Ô in the exponent hides logarithmic factors in and 1/e.
We needed (1 + +), but got (1 + =)* instead. However, this be handled with e' e/5.
27

---

Published as a conference paper at ICLR 2025
E A ROBUST APPROXIMATION SCHEME FOR k-MEANS (PROOF OF THEOREM 8
This section gives the proof of Theorem We restate the theorem and the algorithm for readability. We state the algorithm of Bhattacharya et al. Bhattacharya et al. (2020b) replacing D2-sampling with Ld- sampling.
Algorithm 5 Algorithm of Bhattacharya al. (2020b) with replaced with 8-close 'D
1: Input: (V, k, E, Cinit), where V is the dataset, k >> 0 is the number of clusters, >> 0 is the error parameter, and Cimit a center set that gives constant (pssuddo)aprooximaton)
2: Output: A list L of l center sets such that for at least one C' E L. (VV, C*) S (1 +1+ OPT.
3: Constants: O [1- ): (
k
4: count +
5: repeat
6: Sample multi-set M of pk points from V using D2 saasliigngg wrt center set Cinst
7: .M + M U {rk copies of each element in Cinit)
8: for all disjoint subsets Si Si.... Sp of M such that Vi, |S:| = r do
9: C u (p(S1),.... ..... ((x)))
10: end for
11: count++
12: until count < 2
13:
return L
Theorem (Restatement of Theorem Let 0 < S. 2 be the error parameter, 0 < 8 < 1/2 be the closeness parumeter, V E R xd be the dataset, le be positive integer, and lei Cinit be constant solution for dataset V. Let C be the list returned by Algorithum 5 on input (V, K,K,E, Cina)) using the distance function D that is S-close the Euclidean distance function D. Then with probability at least 3/4, contains a center set C such that (V,C) s (1+ OPT. Moreover, [C| = 20(²) and the running time of the algorithm is ((N
Note that what this theorem essentially says is that if the error in the distance estimates is bounded within multiplicative factor of (1 + 8) with 8 < 1/2, then the guarantees of the algorithm of Bhattacharya al. [Bhattacharya et al. (2020b) do not change except for some constant factors (that get absorbed in the O of the exponent).
We need to define few quantities that will be used to prove the above theorem. Let {X1, Xx3 be the optimal clusters. is well-known that the center that optimizes the 1 1-means cost for any pointset
Σver v
is the centroid of the pointset. We denote the centroid of any pointset Y IRd with μ(Y) This follows from the following well-known fact:
[Vl
Fact 1. For any Y C Rdd and any E Rdd, we have EvEr yE Ilv - = lly x(Y) + |Y| ||c ())
We have used the norm notation instead of ((...) for the Euclidean distance function. This is to easily distinguish between the usage of D and D. We define the optimal 1-means cost for pointset X; as ((X,))1 2. We denote the optimal k-means cost using OPT = Σ A(X,). We will use the following sampling lemma from Inaba er al. Inaba et al. (1994), which says that the centroid of a small set of uniformly sampled points from the dataset Y is good center with respect
A(X.) Egex, x;
||
to the 1-means cost for dataset Y.
Lemma 17 (Inaba et al. (1994)). Let S be set of points obtained by independently sampling M points with replacement uniformly at random from a point set Y C TRd. Then for any 8 > O,
Pr ((u(S),
1
1
1
(()) 2 (1 (1-
8M
We will also use the following approximate triangle inequality that holds for squared distances.
Fact 2 (Approximate triangle inequality). For any x, y, Rd, we have ||æ 2|| < 2- (I1 v11
lly )
28

---

Published as a conference paper at ICLR 2025
The proof of Theorem follows from the following theorem, which will prove in the remaining section.
Theorem 10. Let 0 < E, 1/2. Let L denote the list returned by Algorithm 5 on input kV, Cina). Then with probability at least 3/4, L contains a center set such that
① (C,, (C, X (1+
EA(X)) OPT.
Moreover, [C] 20(²) and the running time of the algorithm is (ndd([))
Let Csnst be an (a, () approximate solution to the k-means problem on the dataset V. That is:
(V. Cinse) S a OPT and |Canat| S 3.
Let us now analyze the algorithm. Note that the outer repetition (lines 5-12) operation is to amplify the probability of the list containing good & center set. We will show that the probability of finding a good i center set in one iteration is at least (3/4)*, and the theorem will follow from standard probability analysis. So, we shall focus only
iteration of the outer loop. Consider the multi-set M obtained on line (7) of Algorithm 5 We will show that with probability at least (3/4)*, there are disjoint multi-subsets Ti, Ti...., Th each of size such that for every i I.
X(I(T)),X,,) S (1+ :) ((X.)
(5) line (8), we will get the desired result.
ОPP.
Since we try all possible subsets of More precisely, we will argue in the following manner: consider the multi-set C" (Tk copies of each element in ] We can interpret C" as a union multi-sets C₁, C32y Cl,..., C%+ where Cj = {t copies of each element in Cinat). Also, since M consists of pk independently sam- pled points, we can interpret M as a union of multi-sets M1. My..... Mí where Mi is the first p points sampled, Mt is the second P points and so on. For = I,,... k. let M; = CM n X,) 16 We will show that for every i {1..... k), with probability at least (3/4), M, contains subset T, of size t that satisfies Eqn. (5). Note that Tj's being disjoint follows from the definition M, will be sufficient to prove the following lemma.
Lemma 18. Consider the sets MI,... Ms as defined above. For any E {1....,k})
Pr .T, S. M; s.t. [T.] T and (D(u(T)), S (1+ A(X)) 2k
3 & OPT)]
We prove the above lemma in the remaining discussion. We do a case analysis that based on whether X(Cinss.X,) is large or small for particular i (1,..., k}.
(CCmu,
Case-l (#DCimit X,) S Boik @(Cinat: V)): Here, we will show that there is subset T. C C₁ C M, that satisfies Eqn. (5)
Case-ll (#(Cinit, Xz) > 5ak
$ (Cinit V)): Here will show that M, contains subset
Ti such that (T), X2) S (1+ 5) A(X)) and hence T; also satisfies Eqn. 5
We will discuss these two cases next.
Case-I: (D(Cinit: X²) S
= (CCnnis V)) First, observe that:
6ak
ε
D(Cinit; X²) <
OPP
(since Cinit is an a-approximate solution)
(6)
6hi
For any point V, let c(x) denote the center in the set C' that is closest z. That is, c(x) arg mineeCCmu ||c ic--a xxll Given this definition, note that:
Σ 11z-c(=)] D(Cinar, ZEX;
We define the multi-set X (c(x) : X²). Let and m' denote the centroids of the point sets
X, and X,, respectively. So, we have A(X)) ((m, X,) and A A(X() = 3(m', , X²). We will show that ((X,) s ((X)). First, bound the distance between m and m'.
Mf X; in this case, denotes those points in the multi-set Mf that belongs X;-
29

---

Published as a conference paper at ICLR 2025
Lemma 19. || m m'1l
P(CinitxX)) Xx+
Proof. We have:
||m m m'1 |EmEx, (x- -(x))))
1 ExEx, 11x - 11xx-1(aa
c(x)))1
((Cinits Xz)
|x,
[xyl
|xyl
where the second to last inequality follows from Sanuhy-Schwartz Lemma 20. A(X)) (CCinit, X;) A(Xi).
Proof. We have:
A(X)) =
E
|c(x) - m'11 1
Σ l[e(x)) - ml|
zEX;
x
(Fact
2 Σ (1((()) 2|1 || ml mll = 2- *(CCnnts X,) + A(X))
REX;
This completes the proof of the lemma.
We now show that good center for X will also be good center for X,, Lemma 21. Let m" be a point such that 4(m", - (1 + 5 A(X)). Then (mm",X) S (1+ 5) A(X;) + 2% OPT.
Proof. We have:
o(m", X,)
(Fact
Σ sEX,
| ml|² + |X,1- ||m- - m²1
(Fad
A(X.) 2|x [111= 1|mm - m m=11²))
(Lemma
A(X,) 2 ((Conits X.) + 2| 1| m²'1
(Fact)
A(X)) + @(Cmit X1) +24mmmm (00mm,,() ,X) (xx)))
A(X,) + (CC, + -(X())
(Lemma 20
A(X;) + (CCint X.) + (D(Cinits X.) + A(X.))
(Egg. 6
(1+)) 5) 2 A(X)) + E OPP.
2k
This completes the proof of the lemma.
We know from Lemma I7 that there exists (multi) subset of X of size 7 such that the mean of these points satisfies the condition of the lemma above. Since C² contains least copies of every element of Cinit, there guaranteed to be a subset T; C C² that satisfies Eqn. (5) So, for any index i {1...., k} such that ((C.mss.V)
((Cniit.)) - M, has good subset T, with probability 1.
Case-II: (C X,) Besk (CCinit, V)) If we can show that a D2-sampled set with respect center set Cinit has a subset S that may be considered a uniform sample from X,, then we can use Lemma 17 to argue that M, has a subset T; such that (T;) is good center for X,. Note that since = and D is 8-close to D. we can argue that if we D2-sapple poly( t elements, then we will get a good representation from X,, However, some the points from X; may be very close to one of the centers in Cinst and hence will have a very small chance of being D In such a case, no subset of a sampled set will behave like a uniform sample from X,. So, we need to argue
(CEnss,
"(Cinse, V)
carefully taking into consideration the fact that there may be points in X, for which the chance of being D2- -smmleee may be very small. Here the level argument that we will build:
30

---

Published as a conference paper at ICLR 2025
Consider the set X which is same X; except that points in X; that are very close Cinit have been "collapsed" to their closest center in Cinit-
Argue that a good center for the set X is good center for X;.
Show that a convex combination of copies of centers in Cinit (i.e., C3) and De-sampled points from X; gives good center for the set X
The closeness of point X; to points in Cinit is quantified using radius that defined by the equation:
defn. e² R
D(Cinit; X²)
(8)
41
[Xa]
Let Xmeur be the points X; that are within distance of R from a point in set Cinit and X: X; \ X That is, X = {i E X, minceComa ||x- cll S RJ and X for
X/ar X; \ X,ear
Using these, we define the multi-set X as:
x = X far U (c(x)) I E Xxear))
Note that XX| |X|] Let = (X,),, m = p(X)). Let X and ñ = [Xmear] We first show lower bound on A(X)) in terms of R.
Lemma 22. A ((;;)= 2 _ n..
Proof. Let c = arg ming I| dl. We case analysis:
1. Case 1: ||m - cll 2 5 R
Consider any point p E Xmeer, From triangle inequality, we have:
5
4 - R.
lp ml 2 ||e()) ml] - -c((pp) pll > R
R
2
This gives: A(X,) 2 E Epexpoer 11p- m||= 2 16n
-² R²a
2. Case 2: || cll < _ R
In this case, we have:
A(X,) = (c. X,) n. I|m cl12 #CCmitt. X2) - n |Im
cll2
41n
R²
25n
R2
>
16n
R²2
c²
2²
2
This completes the proof the lemma.
We now bound the distance between and m' in terms of R. Lemma 23. || m
112 < 2 R..
Proof. Since X2| = |X/| and the only difference between X; and X are the points corresponding
X near we have:
||m- m
Σ
(p-c(p)) c(p))
(p (p-
ñ
Σ
1p- (p-)cpp)12
<
R² (n)
<
n
R².
(n)
PEXpear
The second inequality above follows from the Cauchy- inequality.
We now show that A(X,) and ((X)) close.
Lemma 24. ((X)) 4 + 2 A(X)).
Proof. The lemma follows from the following sequence of inequalities:
A(X))
Σ
|c(p)
mll + Σ
1p 1p- m'|"
PE RCCr
PEX!" far
31

---

Published as a conference paper at ICLR 2025
Facey
Σ
2. (lcdl) - pll llp 1el1--mi 1-mmm11)++
Σ DEX!"
lp m'll
Near
2n + Dmmmm Xi)
(Fac
2n + 2 (M X,) + n 1|m m m²ll?)
(Lemmn
23
4 -
This completes the proof of the lemma.
We now argue that any center that is good for X/ is also good for X,.
Lemma 25. Let m" be such that ((m", X!) S (1 te) A(X)). Then D(m", (xi) S (1 (1+
A(X)).
Proof. The lemma follows from the following inequalities:
((m", X:)
Σ
|m"" pll
PEX.
(Foct
Σ
||m p112 + 11m m=
PEX.
(Fact
A(X,) + 2n (Im-m'l) mm11² 11mm 11m'mm"'1" mmml()
(Lemma
23
A(X,) + 2m +2n ||mm - m²11 -mmm
(Fact
A(X,) + 2m +2 --20(mm",, ,X!) -(x)))
( (Lemma bypothesis)
A(X,) + 2 + E A(X!)
(Lemmo
A(X,) + + + RRR E A(X.)
(Lemma 22
(1+ :) A(X.).
This completes the proof of the lemma.
Given the above lemma, all we need to argue is that our algorithm indeed considers center m such that ((m", x() S (1+6/16) A(X!). For this we would need about 2(² uniform samples from X/. However, our algorithm can only sample using D2 Da-samiingg w.r.. Cynst- For ease of notation, let c(Xpear) denote the multi-set {c(p) p X.ear). Recall that X consists of x/"r and c(Xmear). The first observation make is that the probability of sampling element from x is reasonably large (proportional to $). Using this fact, we show how to sample from X (almost uniformly). Finally, we show how convert this almost uniform sampling to uniform sampling (at the cost of increasing the size of sample).
Lemma 26. Let x be sample from D2 -aasmplin w.r.t. Cenit. Then, Pr(x E X("1] Book
Further,
for any point p x.err Pr(r 2
7 where y denotes 246ak
21-
[4,
Proof. Since points are Damsampled with D being 8-close to D, we note that Epex X Pr(z
p) < (1-6)= V(C.na.V |X implies that:
(1+5)²
R²
(1-5)² (1-8)2
d
(Cmii...)) Therefore, the fact that we are in case (Cinss)))
o (Contt (1+8) +-2 e² & (CCrnst, 2 8ack'
Pr[æ e X!"1 2 Pr|z E -r]-Pr E Xmear
> (C V) (1 - 8) 41 (CCinit, V)
32

---

Published as a conference paper at ICLR 2025
Also, if x E X/ then & ((Ciit:: {x}) R² 11
=² ((Cinst. [Xi
Therefore the probability that
point p X gets D2 De-sampled is,
(1- 8)2
((Cnnse: {x})
(1 - 8)2
8
R
Pr(x- = /| 2
(1+8y 8)2 Φ(Cinit, V)
(1 + 8)2
6or
((Cinit, X;)
(1 8)2
8
e²
1
(1 + 8)2
6ock 41
X2,
(1 8)2
1
(1
(1- -
(1 + 8)2
246ak
246ak
[X,
This completes the proof of the lemma.
Let OI,... Op be P points sampled independently using D'-ssmpling w.r.t. Cinit. We construct new set of random variables Yi...., ................................ Yp. Each variable Y, will depend on On only and will take values either in X or will be _.. These variables are defined as follows: if Ou & X!!rr, we set Y, to L. Otherwise, we assign Y, to one of the following random variables with equal probability: (i) O₂ or (ii) a random element of the multi-set c(Xpeer). The following observation follows from Lemma 26
Corollary 1. For fixed index u, and an element x E X Pr(Y, = 2 2 where 7/ 7/22.
Proof. If x X/for, then we know from Lemma 26 that O, is x with probability least [ (note that X; and X; have the same cardinality). Conditioned on this event, Ya will be equal to Ou with probability 1/2. Now suppose x E c c(Xpear). Lemma 26 implies that O₂ is an element of X! with probability at least s Conditioned on this event, Ya will be equal to x with probability at least z Te(Xpaar]] Therefore, the probability that O, is equal to æ is at least
Bock
Sock
2 R
16ak X XXI
Corollary shows that we can obtain samples from X; which are nearly uniform (up to a constant factor). To convert this to a set of uniform samples, we use the idea Jaiswal al. (014 For an TX² denotes the probability that the random variable Y, is equal
element x E Xt, let Ye be such that "Ys
to x (note that this is independent of u). Corollary I iimples that 72 2 7/- We define new set of independent random variables Zi,.... Zp. The random variable Z. will depend on Y, only. If Y, is I. Zu is also T. Yf, is equal to x E X then Zu takes the value x with probability 2 and T with the remaining probability. We can now prove the key lemma.
256, Lemma 27. Let p be e- and m² denote the mean of the non-null samples from Zi...., .a....,2, Zp Then, with probability at least (3/4), 4(m", X() s (1 (1++)) -
Proof. Note that random variable Z, is equal to a specific element of X with probability equal to [XT Therefore, it takes 1 value with probability 1 7/- Now consider different set of iid random variables Zg, S u S p as follows: each Z,, tosses a coin with probability of Heads being 7 If we get Tails, it gets value 1 otherwise, it is equal to a random element of X It is easy to check that the joint distribution of the random variables Z is identical to that of the random variables Z Thus, it suffices to prove the statement of the lemma for the random variables Z,,
Now we condition on the coin tosses of the random variables Z'_ Let ní' be the number of random variables which are not J. (n' is deterministic quantity because we have conditioned on the coin tosses). Let mn" be the mean of such non-l. variables among Z Zi,..., Z', If n' happens to larger
than 128 Lemma
17 implies that with probability at least (7/8), & (m" X() < (1 + A(X))
Finally, observe that the expected number of non- random variables is 7 2 256 Therefore, with probability at least I (using Chernoff-Hoefffding)) the number of non-1 elements will be at least
128
33

---

Published as a conference paper at ICLR 2025
Let C(e) denote the multi-set obtained by taking p copies of each of the centers in Cina- Now observe that all the non- elements among Yı, y are elements of (O1,.... Op} C(e), and so the same must hold for Zi...., Zp. Moreover, since we only need uniform subset of size 7 128 C suffices instead of C(p), This implies that in steps 8-9 of the algorithm,
would have tried adding the point m" as described Lemma 27 This means that M, contains a subset 7; such that ( X.) S (1 (1+3) -XX() with probability at least 3/ This concludes the proof of Theorem 10
F ADDITIONAL EXPERIMENTS
In this section, give additional experiments and some of the details of the experiments in Section 4
F.1 LARGER DATASETS AND AFKMC
We have added experiments on datasets significantly larger than the ones experimented on in Section further elaborate the dependence of Ç, and N on QI-k-means++ The conditions under which the experiments were performed are the same as before. We also compare with the AFKMC algorithm from Bachem al. (2016a). our implementation, we used the Markov chain length to be 200 suggested by Bachem et al. (2016a) for all datasets.
Dataset
N
Q OI-k-measst
AFKMC' Setup Time (s)
Setup Time (s)
KDD Caruana et al. (2004)
145, 751
74
1.1
0.2
SUSY Whiteson (2144)
5, 000, 000
18
11.2
2.5
Table 4: Details of the datasets experimented on and corresponding pre-processing times
We first compare the runtime for sampling (without taking into account the pre-pro re-processing step) for a range of values of k. The speedups are given in Table For better comparison, also provide plots for the cumulative runtime (done for 9 values of E {2,.., 10} ). which also includes the pre-processing cost.
Dataset
Algorithm
=0
4: =50
100
=200
KDD
QI-k-means++
10
7.6 x 10 4
1.9 x 10-2 -2
10-2
3.2 10
KDD
k k-means++
4.6 10
9.3 10
4.7
9.6
19.4
KDD
AFKMC
3.2 x 10
1.2 x 10-2
2.7 x 10-1
1.1
4.3
SUSY
QI 3I-kmeans+*
1,8 x 10
5.6 x 10
1.6 x 10
8.7 x 10-2
4.3 x 10
SUSY
k k-means++
5.0
9.7
48
95
195
SUSY
AFKMC2
2.4 x 10-3
6.5 x 10-3
8.8 10-2
3.2
10-1
1.2
Table 5: Runtime dependence (in seconds) for performing single clustering on k:
Kimaars
mm300111
Tuntime (Mwrord))
KUnDDOT of BorSdon
Number Incration
Figure Cumulative runtime plot for KDD
Figure 5: Cumulative runtime plot for SUSY
34

---

Published as a conference paper at ICLR 2025
Large Datasets For large datasets, the total runtime is dominated by the pre- pre-processing cost. After the pre-processing, sampling the cluster centers becomes extremely fast and several orders of magnitude faster than k-means++. This also be seen by the cumulative runtime plots in Figures[4 [ the plot for QT-k-means++ is almost constant. This shows that QT-k --e-k--mn-++++ scales well for large datasets since the gain from logarithmic dependence poor dependence on k, and d. As for the dependence on k, we can see from Table 5 that the quadratic dependence immediately visible, but the runtime is still significantly less than that of k-means++ even for intermediate values of k. Hence, such datasets lie in the advantageous regime of 0I-k-means++. This contrasts small datasets with larger aspect ratios, as elucidated in Section 4
N outweighs the
Comparison with AFKMC2 The AFKMC² algorithm also consists of a pre-processing step which takes O(Nd) time, and main sampling step, which takes d(mk²d) number of samples from the initial probability distribution, where m is the markov chain length. We note two major tradeoffs between AFKMC? and QI-k-means++ means++ ++ The first is that the sampling step itself is empirically faster for QI----maane + while the pre-processing step is more costly for QI means + since requires the setup of sample and query access data structures. But the SQ data structure allows the iadificatiion/ddditinn of data points in (loog Nd) time without repeating the pre- pre-processing step. In contrast, AFKMC2's pre-processing step calculates the initial probability distribution for the Markov chain, which requires calculating the distance of each point from an initial randomly chosen point. Hence, updating or adding a data point will require repeating the pre-processing step.
F.2 ADDITIONAL DETAILS
We report the variance of the clustering costs mentioned in Section (recall that the experiments were conducted over five runs). The seeds were chosen randomly for each run.
2
5
7
8
10
QI-k-man +
1.89
3.19
0.97
1.36
1.44
1.24
0.17
0.20
0.47
k-means++
1.93
3.29
1.90
1.44
1.57
1.09
0.73
0.32
0.52
Table 6: Variance of Clustering cost for binarized MNIST (values are scaled down by a factor of 1021)
2
4
5
8
9
10
Ql-k-means++
246523
48805
335
830
236
99
72
55
51
k k-means++
423718
27544
420
561
765
54
93
35
47
Table Variance Clustering cost for IRIS (values are rounded to 2 decimal places)
2
5
7
10
+l-k-means++
3.77
4.05
1.44
5.96
1.10
2.37
1.10
0.57
1.07
k-means++
1.91
2.00
2.24
3.92
2.28
0.38
1.34
1.51
1.06
Table 8: Variance of Clustering for DIGITS (values scaled down factor of 102")
35


Reviews:
[{"review_id": "85k3oaiUba", "reviewer": "Reviewer_9Gxa", "summary": "This paper provides a quantum algorithm as well as a dequantized (i.e quantum inspired classical) version of it for the problem of $D^2$ sampling. This type of sampling is important for the kmeans++ algorithm and is defined as sampling points in $\\mathbb{R}^d$ with probability proportional to the nearest center from a set $C$ of cluster centers in $\\mathbb{R}^d$. The classical implementation, which gives a $O(log k)$ approximation guarantee, involves a preprocessing step that builds a sample-query access data structure in time O(Nd). Depending on the implementation, the running time after this data structure is set up is $\\tilde{O}(\\zeta^2k^2d)$ or $\\tilde{O}(\\zeta^6k^2)$, where $\\zeta$ is the ratio between the largest and smallest pairwise distance in the pointset. The results are incomparable with prior work, since there is no algorithm that is the best in all parameter regimes. This work does asymptotically improve on all prior works for sufficiently small values of $\\zeta$ and $k$ though. The authors also give a quantum fixed parameter approximation scheme to get a $(1+\\varepsilon)$ approximation for the k-means problem for any $\\varepsilon>0$. The k-means problem has been shown to be NP-hard to approximate below a 1.07 constant factor due to prior work and therefore, this approximation scheme has exponential dependence on $1/\\varepsilon$, while it is efficient in terms of the other parameters. Finally, the authors provide experiments that verify the performance of the algorithms and make the comparison with the classical k-means++ algorithm.", "questions": "How can someone choose which algorithm to use between the ones in Theorem 2 and Theorem 3? For example, is there an efficient way to compute $\\zeta$ in advance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper gives novel algorithms for k-means, which is a fundamental problem for machine learning. The paper is also fairly well written.", "weaknesses": "The performance of the algorithm is only better in certain parameter regimes compared to prior work.\n\nMinor comments:\n-Line 94: I would call it “result” instead of “observation”\n-In many places throughout the paper, I believe the tilde notation is a bit abused. It should only be used to hide factors logarithmic in the function displayed, not arbitrary ones as in Theorem 1 for example.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j1t1FaGnio", "reviewer": "Reviewer_D44y", "summary": "The present paper gives new algorithms; both quantum and classical, for  the $k$-means problem. $k$-means problem is a significant clustering problem with broad spectrum of applications. Given a set $V$ of points in ${\\mathbf R}^{d}$, find a set $C$ of $k$ points, called centers, in $\\mathbf{R}^d$, so that  the sum of squared distance from points in $V$ to the closest point in $C$ is minimized. Because of its foundational algorithmic nature, this computational problem has been of attention from researchers from several perspectives. \n\nThe present paper investigates new quantum approaches to solving this problem. Given it is NP-hard, the goal is to develop approximation algorithms and an algorithm known as $k$-means++ (extending the well known $k$-means algorithm by Lloyd) by Arthur and Vassilvitskii has a $O(\\log k)$ approximation guarantee in expectation. A basic ingredient of $k$-means++ algorithm is called $D^2$-$\\mathit{sampling}$: a procedure that given a data set $V$ and a center set $C$, samples a point in $V$ with probability proportional to its squared distance from the nearest center in $C$. \n\nThe main contribution of this paper is a new quantum algorithm for $D^2$-sampling and a subsequent de-quantization of it. This algorithm then leads to new implementation of  (both quantum and classical) of $k$-means++. While there are other known quantum implementation of  $D^2$-sampling, the present algorithm appears to have different efficiency parameters and hence appears to perform better in certain regimes than known ones. The main parameter that the  running time of the algorithm depends on is the ${\\mathit aspect ratio}$ $\\zeta$: the ratio between the largest and smallest inter-point distance in the dataset. In particular, the quantum algorithm that the author/s develop runs in time $\\tilde{O}(\\zeta^2k^2)$ with $\\tilde{O}$ hiding the poly-log dependencies on relevant parameters. The author/s show how this can be de-quantized to get a classical algorithm with running time $O(Nd)+\\tilde{O}(\\zeta^2k^2d)$.   The paper also presents some initial experimental results.", "questions": "The paper is nicely written, overall. However, the discussion through the prior work is not very clearly written. May be a table of relevant known results will be useful to understand the context of the algorithm in terms of efficiency. Also a more detailed discussion on aspect ratio and its relevance (and if there are fundamental obstacles in improving the running time in terms of this parameter) will be very useful. A table of relevant known results might include:\n\n1. Key prior quantum and classical algorithms for k-means/k-means++\n2. Their runtime complexities\n3. Their approximation guarantees\n4. Key parameters they depend on (e.g. aspect ratio)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper designs new algorithms for a classical and significant computational problem: the  $k$-means problem. Any new algorithm for classical problems such as $k$-means is a contribution to the field of ML and data science.   Thus the paper has broad applicability (in particular will be of interest to ICLR audience).  This is the main strength of the paper.", "weaknesses": "The main weakness is  the algorithm's dependency on the aspect ratio. The algorithm has quadratic dependency on the aspect ratio. That makes one wonder whether it will be really  useful for broad applications. While the author/s briefly discuss this dependency in the paper, it is not at all clear why there needs to be a quadratic dependency. Is it possible to prove a lower bound (in a meaningful restricted model) showing that this dependency is needed? The authors cite a paper by Cohen-Addad et al that presents an algorithm that has closer to $\\log$ dependency on $\\zeta$ (at the expense of having a $N^{\\theta(1)}$ factor in the running time) which appears to be much more attractive. The paper will be substantially stronger if it can bring more clarity on this issue. Following are concrete points that the authors may address to make the paper stronger. \n\n1. Provide a more detailed justification for why the algorithm presented has quadratic dependence on the aspect ratio.\n2. Discuss whether the author/s  believe this dependence is fundamental or if there may be ways to improve it.\n3. Consider proving a lower bound, to show whether this dependence is necessary (if the authors believe it is). \n4. Compare their aspect ratio dependence more thoroughly to other algorithms like the Cohen-Addad et al. result, analyzing the tradeoffs in more depth.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r3RjQZ98YM", "reviewer": "Reviewer_66Ux", "summary": "The paper discusses a novel quantum-inspired algorithm for the k-means problem. Theoretical guarantees of the new algorithm are provided, showing it outperforms classical algorithms in certain areas. Experiments compare runtime of the quantum inspired k-means++ versus the classical k-means++.", "questions": "There are some (minor) questions about the results:\n\n1. In page 4, there is discussion about dependencies in the *assumption-free* case but seems like there are no results for the cases with assumptions. What comparisons and improvements can be made in scenarios with assumptions?\n\n2. Considering different algorithms appear to have quite different dependencies with regards to N, d, k, aspect ratio, matrix conditions, etc., what are some impossibility results available for the k-means problem and how does the algorithm's runtime dependencies compare with it? \n\n3. Can you elaborate on whether there are methods to improve the dependency on the aspect ratio $\\zeta$? It seems to be a bit counterintuitive. For example, if there are two clusters of points, and the two clusters are very well-separated, intuition might suggest that k-means with $k=2$ should be relatively straightforward and should be easier as the two clusters are separated out even more. But, in this case $\\zeta$ grows and the bound on the runtime worsens. Additionally, $\\zeta$ becomes very large if there is even a single pair of points that are close by. Do these observations suggest that the dependencies on $\\zeta$ can be tightened?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Starting from originality, the paper extends ideas in quantum machine learning (primarily the sample-access-query model of Tang) to the classical k-means problem, providing novel algorithms and results. Connections to existing literature are well-discussed, and discussions of the strengths and weaknesses of the new algorithm compared to classical algorithms are provided.\n\nIn terms of quality and clarity, it is quite clear that effort has been made to polish the text. The problem formulations, motivations, related work, and the design of the algorithm from a quantum-inspired perspective are all clearly stated. \n\nIt is interesting to see that the new algorithm has better dependency in N but worse dependency in the aspect ratio and k. While this does not show a uniform improvement in all aspects, it is still a good contribution.", "weaknesses": "One of the downsides of the algorithm's runtime dependencies is the dependence of the preprocessing cost O(Nd), which is ignored when comparing against existing results. If we add in O(Nd) to the equation, then both the new algorithm and classical algorithms has a linear dependence on $N$. Perhaps it would be meaningful to have experiments that showcase runtime *after preprocessing* so the plots in Figures 2-3 can be more reflective of the runtime dependencies after preprocessing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X4XSoFIi5b", "reviewer": "Reviewer_ZoT4", "summary": "The authors give novel quantum and classical implementations of $k$-means++.\nThe main ingredient of their approach is a novel $D^2$-sampling method.", "questions": "Page 1:\nI find the abstract to have too much low-level information :)\n\nPage 4:\nCan you please expand on related work?\nHow about the connections of your work to computational complexity?\n\nPage 5:\nPlease give some extra background knowledge in quantum computing and Dirac bra-ket notation :)\n\nPage 6:\nCan you please elaborate on the concept of dequantization and provide some examples?\n\nPage 7:\nI do not see why the states $(1),\\ \\dots,\\ (4)$ are the right ones involved in the quantum $D^2$-sampling algorithm :)\n\nPage 8:\nI do not understand the Lines 412 -- 417.\nWhat does pseudo approximate mean here?\n\nPage 9:\nI am not an expert with experiments :)\n\nPage 10:\nWhere is the Conclusion? :) Can you please add a Conclusion and Future Work section?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "$k$-means++ is an important tool in ML, therefore this paper is significant as it gives novel quantum or classical implementations of it.", "weaknesses": "See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)