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

Physical Review A

Quantum k -medoids algorithm using parallel amplitude estimation

Yong-Mei Li, Hailing Liu, Shi‐Jie Pan, Su‐Juan Qin, Fei Gao, Dong-Xu Sun, Qiaoyan Wen

Published Feb 14, 2023• 9 citations
Publisher

Abstract

Quantum computing is a promising paradigm that can provide viable solutions to high-complexity problems. The $k$-medoids algorithm is a powerful clustering method ubiquitously used in data mining, image processing, pattern recognition, etc. The core of $k$-medoids algorithm is to perform cluster assignment and center update, which are time-consuming for large data sets. A\"{\i}meur et al. proposed a quantum $k$-medoids algorithm [A\"{\i}meur, Brassard, and Gambs, Mach. Learn. 90, 261 (2013)] by quantizing the center update. Nevertheless, it has a query complexity $O({N}^{3/2})$ for one iteration, which is computationally expensive for a large $N$ where $N$ is the number of points. In this paper, we propose a complete quantum algorithm for $k$-medoids algorithm. Specifically, in cluster assignment, we devise a quantum subroutine to calculate the Manhattan distance between any two points and then assign all points to the closest center in parallel, which is faster than what is achievable classically. In center update, for a cluster, we use parallel amplitude estimation to calculate the average distance of each point to all the others. It makes our algorithm polynomially faster than the algorithm of A\"{\i}meur et al., whose sum of distances of each point to all the others is computed by adding the distances one by one. Our quantum $k$-medoids algorithm, with time complexity $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}({N}^{1/2})$, achieves a polynomial speedup in $N$ compared to the existing one.

DOI
10.1103/physreva.107.022421

Related papers

Quantum Computing Approach in K-Medoids Method for AIDS Disease Prediction Using Manhattan Distance

Mochamad Wahyudi, Imeldi Sintagel br Sianipar, Lise Pujiastuti +2 more

Acquired Immunodeficiency Syndrome (AIDS) caused by the Human Immunodeficiency Virus (HIV) is one of the deadliest infectious diseases in the world. Understanding its spread and epidemiological characteristics is crucial for developing and preventing more effective treatments. This study uses the K-Medoids method with a quantum computing approach to predict AIDS based on clinical and demographic data. K-Medoids is chosen to group large amounts of data using a clustering technique that determines the center point (medoid) of each cluster, minimizing the overall distance between data in a cluster. The Manhattan distance is used because it is easier to process data. The quantum computing approach is used to overcome the limitations of classical computing when processing large-scale medical data. This study shows that the application of quantum algorithms to the K-Medoids method allows for faster and more accurate predictions in the diagnosis of AIDS. The tests carried out showed that the prediction accuracy of classical and quantum methods was comparable, namely 85%. The results support the great potential of quantum computing to improve the efficiency of medical predictions. The research involves converting data into quantum format, processing it with the K-Medoids algorithm, and evaluating its performance based on metrics such as intercluster distance and computation time. The research will also identify patterns and risk factor for the spread of AIDS that can be used to develop more effective health interventions. The conclusion of the research is that integrating the K-Medoids techniques can only increase the speed of data processing but also provide competitive accuracy compared to traditional techniques. This research opens up new possibilities in medical data analysis, especially when managing large and complex data sets. The bottom line is that these findings can help make better medical decisions and strategically support AIDS prevention and treatment efforts.

ILKOM Jurnal Ilmiah•Apr 20, 2025•0 citations

Quantum clustering with k-Means: A hybrid approach

Alessandro Poggiali, Alessandro Berti, Anna Bernasconi +2 more

Quantum computing, based on quantum theory, holds great promise as an advanced computational paradigm for achieving fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degrees of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms are theoretically faster than the classical algorithm, while experiments suggest that it is possible to obtain comparable clustering results.

arXiv:2212.06691•Theoretical Computer Science•Feb 21, 2024•50 citations

Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator

Amanuel Tamirat Getachew

Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.

arXiv:2012.11139•Dec 21, 2020•2 citations

Quantum-data-adaptive clustering algorithm

Meng-Ting Yang, Yu Huang, Lu Yan +1 more

Abstract Quantum state clustering provides a powerful tool for quantum information processing. This paper focuses on the classification of single-qubit pure and mixed states via clustering algorithms, and discovers that the classical K -means algorithm has two limitations in clustering quantum states: the Euclidean distance cannot accurately reflect the similarity between quantum states, and the centroid update based on the arithmetic mean frequently fails to yield valid quantum states. To address these issues, we propose two distance metrics for quantum states: the dynamic distance and the Bloch distance, and adopt the K -medoids method to update the centroid, ensuring that the cluster center always remains a valid quantum state, thereby designing a quantum-data-adaptive clustering algorithm. Experimental results show that the dynamic distance achieves a clustering accuracy as high as 91.4 % , but at the cost of higher computational complexity. In contrast, the Bloch distance significantly reduces computational complexity while maintaining clustering performance comparable to that of the dynamic distance, achieving a clustering accuracy of 87.4 % . This paper provides a practical method for achieving efficient and reliable clustering of single-qubit quantum states.

Laser Physics Letters•Jul 1, 2026•0 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.

arXiv:2308.08167•Aug 16, 2023•3 citations

Quantum amplitude estimation from classical signal processing

Farrokh Labib, B. D. Clader, Nikitas Stamatopoulos +1 more

We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of $\sim 4.3/\varepsilon$ and a parallel query complexity of $\sim 0.26/\varepsilon$ at 95% confidence. This performance is statistically equivalent and a $16\times$ improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.

arXiv:2405.14697•May 23, 2024•0 citations
Quantum computing is a promising paradigm that can provide viable solutions to high-complexity problems. The kkk-medoids algorithm is a powerful clustering method ubiquitously used in data mining, image processing, pattern recognition, etc. The core of kkk-medoids algorithm is to perform cluster assignment and center update, which are time-consuming for large data sets. A"{\i}meur et al. proposed a quantum kkk-medoids algorithm [A"{\i}meur, Brassard, and Gambs, Mach. Learn. 90, 261 (2013)] by quantizing the center update. Nevertheless, it has a query complexity O(N3/2)O({N}^{3/2})O(N3/2) for one iteration, which is computationally expensive for a large NNN where NNN is the number of points. In this paper, we propose a complete quantum algorithm for kkk-medoids algorithm. Specifically, in cluster assignment, we devise a quantum subroutine to calculate the Manhattan distance between any two points and then assign all points to the closest center in parallel, which is faster than what is achievable classically. In center update, for a cluster, we use parallel amplitude estimation to calculate the average distance of each point to all the others. It makes our algorithm polynomially faster than the algorithm of A"{\i}meur et al., whose sum of distances of each point to all the others is computed by adding the distances one by one. Our quantum kkk-medoids algorithm, with time complexity O\ifmmode~\else˜\fi(N1/2)\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}({N}^{1/2})O\ifmmode~\else˜\fi​(N1/2), achieves a polynomial speedup in NNN compared to the existing one.
Acquired Immunodeficiency Syndrome (AIDS) caused by the Human Immunodeficiency Virus (HIV) is one of the deadliest infectious diseases in the world. Understanding its spread and epidemiological characteristics is crucial for developing and preventing more effective treatments. This study uses the K-Medoids method with a quantum computing approach to predict AIDS based on clinical and demographic data. K-Medoids is chosen to group large amounts of data using a clustering technique that determines the center point (medoid) of each cluster, minimizing the overall distance between data in a cluster. The Manhattan distance is used because it is easier to process data. The quantum computing approach is used to overcome the limitations of classical computing when processing large-scale medical data. This study shows that the application of quantum algorithms to the K-Medoids method allows for faster and more accurate predictions in the diagnosis of AIDS. The tests carried out showed that the prediction accuracy of classical and quantum methods was comparable, namely 85%. The results support the great potential of quantum computing to improve the efficiency of medical predictions. The research involves converting data into quantum format, processing it with the K-Medoids algorithm, and evaluating its performance based on metrics such as intercluster distance and computation time. The research will also identify patterns and risk factor for the spread of AIDS that can be used to develop more effective health interventions. The conclusion of the research is that integrating the K-Medoids techniques can only increase the speed of data processing but also provide competitive accuracy compared to traditional techniques. This research opens up new possibilities in medical data analysis, especially when managing large and complex data sets. The bottom line is that these findings can help make better medical decisions and strategically support AIDS prevention and treatment efforts.
Quantum computing, based on quantum theory, holds great promise as an advanced computational paradigm for achieving fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degrees of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms are theoretically faster than the classical algorithm, while experiments suggest that it is possible to obtain comparable clustering results.
Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.
Abstract Quantum state clustering provides a powerful tool for quantum information processing. This paper focuses on the classification of single-qubit pure and mixed states via clustering algorithms, and discovers that the classical K -means algorithm has two limitations in clustering quantum states: the Euclidean distance cannot accurately reflect the similarity between quantum states, and the centroid update based on the arithmetic mean frequently fails to yield valid quantum states. To address these issues, we propose two distance metrics for quantum states: the dynamic distance and the Bloch distance, and adopt the K -medoids method to update the centroid, ensuring that the cluster center always remains a valid quantum state, thereby designing a quantum-data-adaptive clustering algorithm. Experimental results show that the dynamic distance achieves a clustering accuracy as high as 91.4 % , but at the cost of higher computational complexity. In contrast, the Bloch distance significantly reduces computational complexity while maintaining clustering performance comparable to that of the dynamic distance, achieving a clustering accuracy of 87.4 % . This paper provides a practical method for achieving efficient and reliable clustering of single-qubit quantum states.
We give a quantum approximation scheme (i.e., (1+ε)(1 + \varepsilon)(1+ε)-approximation for every ε>0\varepsilon > 0ε>0) for the classical kkk-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 VVV with NNN points in Rd\mathbb{R}^dRd stored in QRAM data structure, our quantum algorithm runs in time O~(2O~(kε)η2d)\tilde{O} \left( 2^{\tilde{O}(\frac{k}{\varepsilon})} η^2 d\right)O~(2O~(εk​)η2d) and with high probability outputs a set CCC of kkk centers such that cost(V,C)≤(1+ε)⋅cost(V,COPT)cost(V, C) \leq (1+\varepsilon) \cdot cost(V, C_{OPT})cost(V,C)≤(1+ε)⋅cost(V,COPT​). Here COPTC_{OPT}COPT​ denotes the optimal kkk-centers, cost(.)cost(.)cost(.) denotes the standard kkk-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+ε)(1+\varepsilon)(1+ε) for the kkk-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 demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of ∼4.3/ε\sim 4.3/\varepsilon∼4.3/ε and a parallel query complexity of ∼0.26/ε\sim 0.26/\varepsilon∼0.26/ε at 95% confidence. This performance is statistically equivalent and a 16×16\times16× improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.