arXiv:2405.13351

Quantum (Inspired) $D^2$-sampling with Applications

Poojan Shah, Ragesh Jaiswal

Published May 22, 2024• 0 citations

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$. Starting with empty $C$ and iteratively $D^2$-sampling and updating $C$ in $k$ rounds is precisely $k$-means++ seeding that runs in $O(Nkd)$ time and gives $O(\log{k})$-approximation in expectation for the $k$-means problem. We give a quantum algorithm for (approximate) $D^2$-sampling in the QRAM model that results in a quantum implementation of $k$-means++ that runs in time $\tilde{O}(ζ^2 k^2)$. Here $ζ$ 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}(ζ^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 (i.e., $(1+\varepsilon)$-approximation for any given $\varepsilon>0$) to obtain the first quantum approximation scheme for the $k$-means problem with polylogarithmic running time dependence on $N$.

DOI: 10.48550/arxiv.2405.13351

Related papers

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

Jan 1, 201915 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

arXiv:1812.03584Dec 10, 2018119 citations

A Quantum Approximation Scheme for k-Means

Ragesh Jaiswal

arXiv:2308.08167Aug 16, 20233 citations

Do you know what q-means?

Arjan Cornelissen, João Fernando Doriguello, Alessandro Luongo +1 more

arXiv:2308.09701Aug 18, 20232 citations

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li +1 more

arXiv:2306.02826Jun 5, 20230 citations

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim +1 more

quant-pharXiv:2610.42069Nov 2, 2026

arXiv:2405.13351

Quantum (Inspired) $D^2$ -sampling with ApplicationsQuantum (Inspired) $D^2$-sampling with Applications

Poojan Shah, Ragesh Jaiswal

Published May 22, 2024• 0 citations

arXiv HTML PDF

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

. Starting with empty

C

and iteratively

D^2

-sampling and updating

C

k

rounds is precisely

k

-means++ seeding that runs in

O(Nkd)

time and gives

O(\log{k})

-approximation in expectation for the

k

-means problem. We give a quantum algorithm for (approximate)

D^2

-sampling in the QRAM model that results in a quantum implementation of

k

-means++ that runs in time

\tilde{O}(ζ^2 k^2)

. Here

ζ

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}(ζ^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 (i.e.,

(1+\varepsilon)

-approximation for any given

\varepsilon>0

) to obtain the first quantum approximation scheme for the

k

-means problem with polylogarithmic running time dependence on

N

DOI: 10.48550/arxiv.2405.13351

Related papers

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

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 $N$ $d$ -dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)$ per iteration, where $\kappa(V)$ is the condition number, $\mu(V)$ is a parameter that appears in quantum linear algebra procedures and $\eta = \max_{i} ||v_{i}||^{2}$ . For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)$ per iteration, which is linear in the number of features $d$ , and polynomial in the rank $k$ , the maximum square norm $\eta$ and the error parameter $\delta$ . 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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)$ per iteration, where $\kappa(V)$ is the condition number, $\mu(V)$ is a parameter that appears in quantum linear algebra procedures and $\eta = \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $\eta$ and the error parameter $\delta$. 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.

Jan 1, 201915 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

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 $N$ $d$ -dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$ . For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ 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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ 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.

arXiv:1812.03584Dec 10, 2018119 citations

A Quantum Approximation Scheme for k-Means

Ragesh Jaiswal

We give a quantum approximation scheme (i.e., $(1 + \varepsilon)$ -approximation for every $\varepsilon > 0$ ) for the classical $k$ -means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset $V$ with $N$ points in $\mathbb{R}^d$ stored in QRAM data structure, our quantum algorithm runs in time $\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)$ and with high probability outputs a set $C$ of $k$ centers such that $cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})$ . Here $C_{OPT}$ denotes the optimal $k$ -centers, $cost(.)$ denotes the standard $k$ -means cost function (i.e., the sum of the squared distance of points to the closest center), and $η$ is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of $(1+\varepsilon)$ for the $k$ -means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.We give a quantum approximation scheme (i.e., $(1 + \varepsilon)$-approximation for every $\varepsilon > 0$) for the classical $k$-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset $V$ with $N$ points in $\mathbb{R}^d$ stored in QRAM data structure, our quantum algorithm runs in time $\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)$ and with high probability outputs a set $C$ of $k$ centers such that $cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})$. Here $C_{OPT}$ denotes the optimal $k$-centers, $cost(.)$ denotes the standard $k$-means cost function (i.e., the sum of the squared distance of points to the closest center), and $η$ is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of $(1+\varepsilon)$ for the $k$-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.

arXiv:2308.08167Aug 16, 20233 citations

Do you know what q-means?

Arjan Cornelissen, João Fernando Doriguello, Alessandro Luongo +1 more

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=[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.

arXiv:2308.09701Aug 18, 20232 citations

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li +1 more

$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 $\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.

arXiv:2306.02826Jun 5, 20230 citations

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim +1 more

Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$ , return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$ . We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$ , we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.

quant-pharXiv:2610.42069Nov 2, 2026

Quantum (Inspired)

D^2

-sampling with Applications

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

. Starting with empty

C

and iteratively

D^2

-sampling and updating

C

k

rounds is precisely

k

-means++ seeding that runs in

O(Nkd)

time and gives

O(\log{k})

-approximation in expectation for the

k

-means problem. We give a quantum algorithm for (approximate)

D^2

-sampling in the QRAM model that results in a quantum implementation of

k

-means++ that runs in time

\tilde{O}(ζ^2 k^2)

. Here

ζ

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}(ζ^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 (i.e.,

(1+\varepsilon)

-approximation for any given

\varepsilon>0

) to obtain the first quantum approximation scheme for the

k

-means problem with polylogarithmic running time dependence on

N

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

N

d

-dimensional vectors

v_i

(seen as a matrix

V \in \mathbb{R}^{N \times d})

stored in QRAM, the running time of q-means is

\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)

per iteration, where

\kappa(V)

is the condition number,

\mu(V)

is a parameter that appears in quantum linear algebra procedures and

\eta = \max_{i} ||v_{i}||^{2}

. For a natural notion of well-clusterable datasets, the running time becomes

\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)

per iteration, which is linear in the number of features

d

, and polynomial in the rank

k

, the maximum square norm

\eta

and the error parameter

\delta

. 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.

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

N

d

-dimensional vectors

v_i

(seen as a matrix

V \in \mathbb{R}^{N \times d})

stored in QRAM, the running time of q-means is

\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)

per iteration, where

κ(V)

is the condition number,

μ(V)

is a parameter that appears in quantum linear algebra procedures and

η= \max_{i} ||v_{i}||^{2}

. For a natural notion of well-clusterable datasets, the running time becomes

\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)

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.

We give a quantum approximation scheme (i.e.,

(1 + \varepsilon)

-approximation for every

\varepsilon > 0

) for the classical

k

-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset

V

with

N

points in

\mathbb{R}^d

stored in QRAM data structure, our quantum algorithm runs in time

\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)

and with high probability outputs a set

C

k

centers such that

cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})

. Here

C_{OPT}

denotes the optimal

k

-centers,

cost(.)

denotes the standard

k

-means cost function (i.e., the sum of the squared distance of points to the closest center), and

η

is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of

(1+\varepsilon)

for the

k

-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.

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.

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

\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.

Quantum algorithms for linear algebra that access a matrix

A

through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to

A

, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm

ρ=\|A\|_F/\|A\|

and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use

\widetilde O(ρ)

queries, whereas the best dequantized algorithms use

\widetilde O(ρ^4)

. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant

κ_0>1

, we construct dense linear systems with condition number at most

κ_0

for which sampling from the solution within a sufficiently small constant total variation distance requires

Ω(ρ^4/\logρ)

classical queries but only

Θ(ρ)

quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.