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=[v_1,\dots,v_n]\in\mathbb{R}^{d\times n}$ and outputs $k$ centroids $c_1,\dots,c_k\in\mathbb{R}^d$; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical $\varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity $\tilde{O}\big(\frac{\|V\|_F^2}{n}\frac{k^{2}d}{\varepsilon^2}(k + \log{n})\big)$, 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 $\tilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{3/2}d}{\varepsilon}(\sqrt{k}+\sqrt{d})(\sqrt{k} + \log{n})\big)$ that quadratically improves the runtime of our classical $\varepsilon$-$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.
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.
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.
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.
Quantum (Inspired) D2-sampling with Applications
D2-sampling is a fundamental component of sampling-based clustering algorithms such as k-means++. Given a dataset V⊂Rd with N points and a center set C⊂Rd, D2-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. Starting with empty C and iteratively D2-sampling and updating C in k rounds is precisely k-means++ seeding that runs in O(Nkd) time and gives O(logk)-approximation in expectation for the k-means problem. We give a quantum algorithm for (approximate) D2-sampling in the QRAM model that results in a quantum implementation of k-means++ that runs in time O~(ζ2k2). Here ζ is the aspect ratio (i.e., largest to smallest interpoint distance), and 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(logk) approximation guarantee. Further, we show that our quantum algorithm for D2-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)+O~(ζ2k2d), 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 D2-sampling with the known $ D^2$-sampling-based classical approximation scheme (i.e., (1+ε)-approximation for any given ε>0) to obtain the first quantum approximation scheme for the k-means problem with polylogarithmic running time dependence on N.
Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with nonconvex or nested structures [A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference (MIT Press, Cambridge, MA, 2002), pp. 849--856]. With roots in graph theory, it uses the spectral properties of the Laplacian matrix to project the data in a low-dimensional space where clustering is more efficient. Despite its success in clustering tasks, spectral clustering suffers in practice from a fast-growing running time of O(n3), where n is the number of points in the data set. In this work we propose an end-to-end quantum algorithm performing spectral clustering, extending a number of works in quantum machine learning. The quantum algorithm is composed of two parts: the first is the efficient creation of the quantum state corresponding to the projected Laplacian matrix, and the second consists of applying the existing quantum analog of the k-means algorithm [I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, q-means: A quantum algorithm for unsupervised machine learning, in Advances in Neural Information Processing Systems 32: Proceedings of the 2019 Conference (Curran Associates, Red Hook, NY, 2020), pp. 4136--4146]. Both steps depend polynomially on the number of clusters, as well as precision and data parameters arising from quantum procedures, and polylogarithmically on the dimension of the input vectors. Our numerical simulations show an asymptotic linear growth with n when all terms are taken into account, significantly better than the classical cubic growth. This work opens the path to other graph-based quantum machine learning algorithms, as it provides routines for efficient computation and quantum access to the incidence, adjacency, and projected Laplacian matrices of a graph.
We give a quantum approximation scheme (i.e., (1+ε)-approximation for every ε>0) for the classical k-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset V with N points in Rd stored in QRAM data structure, our quantum algorithm runs in time O~(2O~(εk)η2d) and with high probability outputs a set C of k centers such that cost(V,C)≤(1+ε)⋅cost(V,COPT). Here COPT denotes the optimal k-centers, cost(.) denotes the standard k-means cost function (i.e., the sum of the squared distance of points to the closest center), and η is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of (1+ε) for the k-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.