Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.02826

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang

Published Jun 5, 2023• 1 citation
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2306.02826

Related papers

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David Paul Woodruff, Lichen Zhang

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume $n,d\geq\mathrm{poly}(k/ε)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $ε$-coreset of input points of size $\tilde O(k^{4/3}ε^{-2})$ (resp. $\tilde O(k^{3/2}ε^{-2})$) in time $\tilde O(ε^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(ε^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/ε$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geqΩ(k^{7/3})$ (resp. $Ω(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $ε$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}ε^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})$ time with factored output (plus $\tilde O(nk^2ε^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $ε$-coreset of size $o(\sqrt{nS})$ needs $Ω(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(ε^{-1},\log n)$ and VC-dimension factors.

arXiv:2509.16801•Sep 20, 2025•1 citation

Coreset Clustering on Small Quantum Computers

Teague Tomesh, Pranav Gokhale, Eric R. Anschuetz +1 more

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.

arXiv:2004.14970•Electronics•Jul 15, 2021•28 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.

arXiv:1812.03584•Dec 10, 2018•170 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{\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, 2019•22 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.

arXiv:2308.09701•Aug 18, 2023•7 citations

Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm

Fanzhe Qu, Sarah Erfani, Muhammad Usman

Quantum computing is anticipated to offer immense computational capabilities which could provide efficient solutions to many data science problems. However, the current generation of quantum devices are small and noisy, which makes it difficult to process large data sets relevant for practical problems. Coreset selection aims to circumvent this problem by reducing the size of input data without compromising the accuracy. Recent work has shown that coreset selection can help to implement quantum K-Means clustering problem. However, the impact of coreset selection on the performance of quantum K-Means clustering has not been explored. In this work, we compare the relative performance of two coreset techniques (BFL16 and ONESHOT), and the size of coreset construction in each case, with respect to a variety of data sets and layout the advantages and limitations of coreset selection in implementing quantum algorithms. We also investigated the effect of depolarisation quantum noise and bit-flip error, and implemented the Quantum AutoEncoder technique for surpassing the noise effect. Our work provides useful insights for future implementation of data science algorithms on near-term quantum devices where problem size has been reduced by coreset selection.

arXiv:2206.07852•Jun 16, 2022•6 citations
kkk-Clustering in Rd\mathbb{R}^dRd (e.g., kkk-median and kkk-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality nnn, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for kkk-clustering in Rd\mathbb{R}^dRd with O~(nkd3/2)\tilde{O}(\sqrt{nk}d^{3/2})O~(nk​d3/2) query complexity. Our coreset reduces the input size from nnn to poly(kε−1d)\mathrm{poly}(kε^{-1}d)poly(kε−1d), so that existing ααα-approximation algorithms for clustering can run on top of it and yield (1+ε)α(1 + ε)α(1+ε)α-approximation. This eventually yields a quadratic speedup for various kkk-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Ω(nk)Ω(\sqrt{nk})Ω(nk​) queries in order to achieve even O(1)O(1)O(1)-approximation for kkk-clustering.
We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume n,d≥poly(k/ε)n,d\geq\mathrm{poly}(k/ε)n,d≥poly(k/ε) and, for regression, n≥poly(d)n\geq\mathrm{poly}(d)n≥poly(d): - kkk-median/kkk-means: For nnn points in Rd\mathbb{R}^dRd, we build an εεε-coreset of input points of size O~(k4/3ε−2)\tilde O(k^{4/3}ε^{-2})O~(k4/3ε−2) (resp. O~(k3/2ε−2)\tilde O(k^{3/2}ε^{-2})O~(k3/2ε−2)) in time O~(ε−1n0.5dk1.67)\tilde O(ε^{-1}n^{0.5}dk^{1.67})O~(ε−1n0.5dk1.67) (resp. O~(ε−1n0.5dk1.75)\tilde O(ε^{-1}n^{0.5}dk^{1.75})O~(ε−1n0.5dk1.75)). Our better ddd- and linear 1/ε1/ε1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3)d\geqΩ(k^{7/3})d≥Ω(k7/3) (resp. Ω(k2.5)Ω(k^{2.5})Ω(k2.5)). - ℓp\ell_pℓp​ regression: For min⁡x∥Ax−b∥p\min_x\|Ax-b\|_pminx​∥Ax−b∥p​, A∈Rn×dA\in\mathbb{R}^{n\times d}A∈Rn×d, we build an εεε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})O~p​(dmax{1,p/2}ε−2) in time O~p(n0.5d1.5ε−1)\tilde O_p(n^{0.5}d^{1.5}ε^{-1})O~p​(n0.5d1.5ε−1) for p≤2p\leq 2p≤2 and O~p(n0.5dp/4+1(ε−1+d0.5))\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))O~p​(n0.5dp/4+1(ε−1+d0.5)) for p>2p>2p>2, matching [Liu and Ji, ICML'26] for p≤2p\leq 2p≤2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2p>2p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-kkk approximation of A∈Rd×nA\in\mathbb{R}^{d\times n}A∈Rd×n free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5)\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})O~(n0.5dk0.5ε−0.5) time with factored output (plus O~(nk2ε−2)\tilde O(nk^2ε^{-2})O~(nk2ε−2) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity SSS, any quantum algorithm outputting an εεε-coreset of size o(nS)o(\sqrt{nS})o(nS​) needs Ω(nS)Ω(\sqrt{nS})Ω(nS​) queries, so our query complexity is optimal up to poly(ε−1,log⁡n)\mathrm{poly}(ε^{-1},\log n)poly(ε−1,logn) and VC-dimension factors.
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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)κ(V)κ(V) is the condition number, μ(V)μ(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2η= \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm ηηη and the error parameter δδδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\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)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)\kappa(V)κ(V) is the condition number, μ(V)\mu(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2\eta = \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm η\etaη and the error parameter δ\deltaδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)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 kkk-means. This algorithm takes nnn vectors V=[v1,…,vn]∈Rd×nV=[v_1,\dots,v_n]\in\mathbb{R}^{d\times n}V=[v1​,…,vn​]∈Rd×n and outputs kkk centroids c1,…,ck∈Rdc_1,\dots,c_k\in\mathbb{R}^dc1​,…,ck​∈Rd; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical ε\varepsilonε-kkk-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity O~(∥V∥F2nk2dε2(k+log⁡n))\tilde{O}\big(\frac{\|V\|_F^2}{n}\frac{k^{2}d}{\varepsilon^2}(k + \log{n})\big)O~(n∥V∥F2​​ε2k2d​(k+logn)), exponentially improving the dependence on the data size nnn and matching that of the "qqq-means" quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19). Moreover, we propose an improved qqq-means quantum algorithm with time complexity O~(∥V∥Fnk3/2dε(k+d)(k+log⁡n))\tilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{3/2}d}{\varepsilon}(\sqrt{k}+\sqrt{d})(\sqrt{k} + \log{n})\big)O~(n​∥V∥F​​εk3/2d​(k​+d​)(k​+logn)) that quadratically improves the runtime of our classical ε\varepsilonε-kkk-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 computing is anticipated to offer immense computational capabilities which could provide efficient solutions to many data science problems. However, the current generation of quantum devices are small and noisy, which makes it difficult to process large data sets relevant for practical problems. Coreset selection aims to circumvent this problem by reducing the size of input data without compromising the accuracy. Recent work has shown that coreset selection can help to implement quantum K-Means clustering problem. However, the impact of coreset selection on the performance of quantum K-Means clustering has not been explored. In this work, we compare the relative performance of two coreset techniques (BFL16 and ONESHOT), and the size of coreset construction in each case, with respect to a variety of data sets and layout the advantages and limitations of coreset selection in implementing quantum algorithms. We also investigated the effect of depolarisation quantum noise and bit-flip error, and implemented the Quantum AutoEncoder technique for surpassing the noise effect. Our work provides useful insights for future implementation of data science algorithms on near-term quantum devices where problem size has been reduced by coreset selection.