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:2012.11139

Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator

Amanuel Tamirat Getachew

Published Dec 21, 2020• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2012.11139

Related papers

Advanced Quantum Algorithms for Big Data Clustering and High-Dimensional Classification

José Gabriel Carrasco Ramírez

The exponential growth of data and the increasing complexity of high-dimensional classification problems have pushed classical computing methods to their limits. Quantum computing emerges as a promising paradigm to address these challenges. This research article explores advanced quantum algorithms for big data clustering and high-dimensional classification. We investigate quantum versions of K-means, spectral clustering, and support vector machines, comparing their performance with classical counterparts. Our results demonstrate significant speedups in processing time and improvements in clustering quality for high-dimensional datasets. Additionally, we propose a novel quantum-inspired classical algorithm that bridges the gap between quantum and classical approaches. This comprehensive study provides insights into the potential of quantum computing in revolutionizing data analysis and machine learning, paving the way for future advancements in the field.

Journal of Advanced Computing Systems•Jun 8, 2024•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

Comparison of Two Quantum Nearest Neighbor Classifiers on IBM’s Quantum Simulator

Wei Hu

Today computers are used to store data in memory and then process them. In our big data era, we are facing the challenge of storing and processing the data simply due to their fast ever growing size. Quantum computation offers solutions to these two prominent issues quantum mechanically and beautifully. Through careful design to employ superposition, entanglement, and interference of quantum states, a quantum algorithm can allow a quantum computer to store datasets of exponentially large size as linear size and then process them in parallel. Quantum computing has found its way in the world of machine learning where new ideas and approaches are in great need as the classical computers have reached their capacity and the demand for processing big data grows much faster than the computing power the classical computers can provide today. Nearest neighbor algorithms are simple, robust, and versatile supervised machine learning algorithms, which store all training data points as their learned “model” and make the prediction of a new test data point by computing the distances between the query point and all the training data points. Quantum counterparts of these classical algorithms provide efficient and elegant ways to deal with the two major issues of storing data in memory and computing the distances. The purpose of our study is to select two similar quantum nearest neighbor algorithms and use a simple dataset to give insight into how they work, highlight their quantum nature, and compare their performances on IBM’s quantum simulator.

Natural Science•Jan 1, 2018•10 citations

Exploring Quantum Machine Learning Algorithms for Enhanced Data Classification and Clustering in Complex Systems - Integration with Gradient Boosting and K-means for Improved Performance

M. Babu, M. R. Arun, S. Janes Pushparani +2 more

This research focuses on the implementation of quantum machine learning with the classical models such as Gradient Boosting and K-means clustering for efficient classification and clustering of most complex datasets in advanced systems. Taking advantage of the large datasets that are handled by the qc, this work examines Quantum Support Vector Machines (QSVM), Quantum Boosting, and Quantum K-means. To compare the efficiency of these hybrid models three datasets - the healthcare, the financial, and the cyber-security datasets - are used. Our findings indicate that quantum optimization algorithms achieve better accuracy in clustering in comparison to the classical counterparts and are computationally faster. This work shows how quantum machine learning can lead to the enhancement of difficult data processing tasks, a major issue in the quantum computing domain, with specific reference to resources and high-dimensional data. The opportunity to integrate quantum and classical models successfully is the best basis for further developments in machine learning.

International Conference on Cybernation and Computation (CYBERCOM)•Nov 15, 2024•9 citations

Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

We present quantum algorithms for performing nearest-neighbor learning and $k$--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

Quantum Information and Computation•Mar 1, 2015•243 citations

Quantum Machine Learning

Santanu Pattanayak

In this chapter and the next one, we will explore the exciting areas of quantum machine learning and quantum deep learning. Machine learning and deep learning have seen great success in recent years because of the increase in the computational power at our disposal and because of the high-end research in these fields. Quantum machine learning presents an exciting opportunity to increase the computational efficiency of the existing machine learning algorithms as well as presents a way to tackle some of the more computationally intractable problems. In this chapter, we start with the Harrow-Hassidim-Lloyd algorithm, popularly known as HHL, which acts as the matrix inversion routine in the quantum computing domain. Hence, HHL will be the default choice for algorithms such as linear regression and least square support vector machines. Subsequently, we touch upon quantum linear regression and support vector machines in detail in this chapter. We will then move on to implementing quantum routines such as quantum dot product and quantum Euclidean distances since they are integral to several machine learning algorithms such as the k-means clustering and nearest neighbor methods. In this regard, we will implement the k-means clustering method in detail. Also, we will discuss how Grover’s algorithm can be used to optimize quantum objectives by illustrating its usage in the cluster assignment in the k-means algorithm. Principal component analysis is an important machine learning technique, and we will walk through its quantum implementation in great detail as well.

Apress eBooks•Jan 1, 2021•9 citations
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.
The exponential growth of data and the increasing complexity of high-dimensional classification problems have pushed classical computing methods to their limits. Quantum computing emerges as a promising paradigm to address these challenges. This research article explores advanced quantum algorithms for big data clustering and high-dimensional classification. We investigate quantum versions of K-means, spectral clustering, and support vector machines, comparing their performance with classical counterparts. Our results demonstrate significant speedups in processing time and improvements in clustering quality for high-dimensional datasets. Additionally, we propose a novel quantum-inspired classical algorithm that bridges the gap between quantum and classical approaches. This comprehensive study provides insights into the potential of quantum computing in revolutionizing data analysis and machine learning, paving the way for future advancements in the field.
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.
Today computers are used to store data in memory and then process them. In our big data era, we are facing the challenge of storing and processing the data simply due to their fast ever growing size. Quantum computation offers solutions to these two prominent issues quantum mechanically and beautifully. Through careful design to employ superposition, entanglement, and interference of quantum states, a quantum algorithm can allow a quantum computer to store datasets of exponentially large size as linear size and then process them in parallel. Quantum computing has found its way in the world of machine learning where new ideas and approaches are in great need as the classical computers have reached their capacity and the demand for processing big data grows much faster than the computing power the classical computers can provide today. Nearest neighbor algorithms are simple, robust, and versatile supervised machine learning algorithms, which store all training data points as their learned “model” and make the prediction of a new test data point by computing the distances between the query point and all the training data points. Quantum counterparts of these classical algorithms provide efficient and elegant ways to deal with the two major issues of storing data in memory and computing the distances. The purpose of our study is to select two similar quantum nearest neighbor algorithms and use a simple dataset to give insight into how they work, highlight their quantum nature, and compare their performances on IBM’s quantum simulator.
This research focuses on the implementation of quantum machine learning with the classical models such as Gradient Boosting and K-means clustering for efficient classification and clustering of most complex datasets in advanced systems. Taking advantage of the large datasets that are handled by the qc, this work examines Quantum Support Vector Machines (QSVM), Quantum Boosting, and Quantum K-means. To compare the efficiency of these hybrid models three datasets - the healthcare, the financial, and the cyber-security datasets - are used. Our findings indicate that quantum optimization algorithms achieve better accuracy in clustering in comparison to the classical counterparts and are computationally faster. This work shows how quantum machine learning can lead to the enhancement of difficult data processing tasks, a major issue in the quantum computing domain, with specific reference to resources and high-dimensional data. The opportunity to integrate quantum and classical models successfully is the best basis for further developments in machine learning.
We present quantum algorithms for performing nearest-neighbor learning and kkk--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
In this chapter and the next one, we will explore the exciting areas of quantum machine learning and quantum deep learning. Machine learning and deep learning have seen great success in recent years because of the increase in the computational power at our disposal and because of the high-end research in these fields. Quantum machine learning presents an exciting opportunity to increase the computational efficiency of the existing machine learning algorithms as well as presents a way to tackle some of the more computationally intractable problems. In this chapter, we start with the Harrow-Hassidim-Lloyd algorithm, popularly known as HHL, which acts as the matrix inversion routine in the quantum computing domain. Hence, HHL will be the default choice for algorithms such as linear regression and least square support vector machines. Subsequently, we touch upon quantum linear regression and support vector machines in detail in this chapter. We will then move on to implementing quantum routines such as quantum dot product and quantum Euclidean distances since they are integral to several machine learning algorithms such as the k-means clustering and nearest neighbor methods. In this regard, we will implement the k-means clustering method in detail. Also, we will discuss how Grover’s algorithm can be used to optimize quantum objectives by illustrating its usage in the cluster assignment in the k-means algorithm. Principal component analysis is an important machine learning technique, and we will walk through its quantum implementation in great detail as well.