Quantum Algorithms Database
Quantum k-Means Clustering
A quantum version of the classical k-means clustering algorithm, grouping similar data points together using quantum distance estimation techniques.
Year
2013
Inventor(s)
Lloyd, Mohseni & Rebentrost
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
The Problem
Partitioning a dataset into clusters of similar items — one of the most common unsupervised machine learning tasks.
How It Works
Uses quantum subroutines like the SWAP test to estimate distances between data points and cluster centers, potentially reducing the work needed compared to classical distance calculations.
Real-World Impact
Like other early quantum ML proposals, theoretically promising but constrained by the practical challenge of efficiently loading real-world data into quantum states.