$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for $k$-clustering in $\mathbb{R}^d$ with $\tilde{O}(\sqrt{nk}d^{3/2})$ query complexity. Our coreset reduces the input size from $n$ to $\mathrm{poly}(kε^{-1}d)$, so that existing $α$-approximation algorithms for clustering can run on top of it and yield $(1 + ε)α$-approximation. This eventually yields a quadratic speedup for various $k$-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make $Ω(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation for $k$-clustering.
k-Clustering in Rd (e.g., k-median and k-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality n, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for k-clustering in Rd with O~(nkd3/2) query complexity. Our coreset reduces the input size from n to poly(kε−1d), so that existing α-approximation algorithms for clustering can run on top of it and yield (1+ε)α-approximation. This eventually yields a quadratic speedup for various k-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Ω(nk) queries in order to achieve even O(1)-approximation for k-clustering.
We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation. Our contributions include: * k-median and k-means clustering: For n points in d-dimensional Euclidean space, we give an algorithm that constructs an ε-coreset in time O(n0.5dk2.5poly(ε−1)) for k-median and k-means clustering. Our approach achieves a better dependence on d and constructs smaller coresets that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * ℓp regression: For ℓp regression problems, we construct an ε-coreset of size Op(dmax{1,p/2}ε−2) in time Op(n0.5dmax{0.5,p/4}+1(ε−3+d0.5)), improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all p∈(0,2)∪(2,22], including the widely studied least absolute deviation regression (ℓ1 regression). * Low-rank approximation with Frobenius norm error: We introduce the first quantum sublinear-time algorithm for low-rank approximation that does not rely on data-dependent parameters, and runs in O(nd0.5k0.5ε−1) time. Additionally, we present quantum sublinear algorithms for kernel low-rank approximation and tensor low-rank approximation, broadening the range of achievable sublinear time algorithms in randomized numerical linear algebra.
Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigated using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We used numerical simulations to compare the performance of this approach to classical k-means clustering. We were able to find data sets with which coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well—which is necessary for a quantum advantage over k-means on the entire data set—appears to be challenging.
Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigated using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We used numerical simulations to compare the performance of this approach to classical k-means clustering. We were able to find data sets with which coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well—which is necessary for a quantum advantage over k-means on the entire data set—appears to be challenging.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for k-means. This algorithm takes n vectors V=[v1,…,vn]∈Rd×n and outputs k centroids c1,…,ck∈Rd; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical ε-k-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity O~(n∥V∥F2ε2k2d(k+logn)), exponentially improving the dependence on the data size n and matching that of the "q-means" quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19). Moreover, we propose an improved q-means quantum algorithm with time complexity O~(n∥V∥Fεk3/2d(k+d)(k+logn)) that quadratically improves the runtime of our classical ε-k-means algorithm in several parameters. Our quantum algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states based on the current iteration's clusters and multivariate quantum amplitude estimation. Finally, we provide classical and quantum query lower bounds, showing that our algorithms are optimal in most parameters.