Quantum k-Means Clustering

Overview

The k-means algorithm groups data points into k clusters by repeatedly assigning each point to its nearest cluster center and then moving each center to the average of its points. It is one of the most widely used unsupervised learning methods. Quantum k-means replaces the expensive distance calculations and updates with quantum subroutines such as the SWAP test and amplitude estimation.

There are several versions. Lloyd, Mohseni, and Rebentrost proposed a version with a runtime that depends only logarithmically on the size and dimension of the data, assuming quantum access to the data. Aïmeur, Brassard, and Gambs proposed a version using Grover search for a quadratic speedup. Kerenidis and coauthors proposed q-means in 2019, which has a polylogarithmic runtime per iteration under data-access assumptions.

The problem it solves

Partitioning a dataset into clusters of similar items — one of the most common unsupervised machine learning tasks.

History and background

Lloyd, Mohseni, and Rebentrost described quantum algorithms for supervised and unsupervised machine learning in 2013, including nearest-centroid classification and clustering. In the same year, Aïmeur, Brassard, and Gambs published Quantum Speed-up for Unsupervised Learning in the journal Machine Learning, using Grover search to speed up clustering primitives. In 2015 Wiebe, Kapoor, and Svore extended quantum methods to nearest-neighbor learning.

The q-means algorithm by Kerenidis, Landman, Luongo, and Prakash was presented at NeurIPS 2019, along with simulations suggesting accuracy comparable to classical k-means on image data, with noise built in. In 2018, Ewin Tang gave classical sampling-based algorithms for supervised clustering, which cast doubt on exponential speedups under comparable data access. Small experimental demonstrations with a few qubits have been reported on photonic and superconducting devices.

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.

Classical k-means spends most of its time computing distances between N data points and k centroids in d dimensions. That is about N times k times d operations per iteration. If the data points and centroids are stored as quantum states, the distance between two of them can be estimated with the SWAP test using a number of operations that depends on the logarithm of d, not d itself.

For the update step, the new centroid of a cluster is the average of its points. A quantum computer can prepare a superposition over all points in the cluster and use amplitude estimation to estimate their mean coordinates, with a quadratic improvement in precision over sampling.

Grover-style versions work differently. They treat finding the point farthest from or nearest to a center as a search problem and use quantum minimum finding to speed it up, giving a square-root gain in the number of points.

Step by step

1. Load the N data points into a quantum memory so that each can be prepared as a quantum state on demand, and choose k initial centroids.
2. For each data point, estimate its distance to every centroid using the SWAP test or an inner-product estimation routine.
3. Assign each point to its nearest centroid, using quantum minimum finding over the k estimated distances.
4. Estimate the new centroid for each cluster by amplitude estimation, or by preparing a superposition of the cluster's points and measuring.
5. Replace the centroids with the new estimates, with a tolerance that accounts for estimation error.
6. Repeat until the centroids stop changing, and read out the final cluster centers or the cluster assignments.

A worked example

Suppose there are 1,000,000 data points in 128 dimensions and k = 10 clusters. Classical k-means needs about 1.3 billion distance component operations per iteration. A quantum version with data in a QRAM could estimate each point-to-centroid distance in a number of steps that grows only with the logarithm of 128, but it must repeat the SWAP test thousands of times for each estimate to reach useful precision.

The overall advantage depends on whether the cost of building the QRAM and the precision requirements are small compared with the classical work. For a one-time clustering of a fixed data set, the loading cost can erase the gain, which is why proposals emphasize repeated clustering tasks over the same loaded data.

Complexity and resources

What hardware it needs

• A fault-tolerant quantum computer with a large QRAM for the exponential-speedup versions.
• Fast, repeated SWAP tests and amplitude estimation with high-fidelity gates.
• A classical controller for the iteration loop and stopping criterion.

Applications

• Clustering large data sets in marketing, genomics, and image analysis, if data access is cheap.
• Compression and quantization of images or features.
• Preprocessing for other machine learning models.
• Clustering of quantum data, where states are already available.

Limitations and caveats

• Loading classical data into quantum states removes much of the theoretical speedup.
• Classical algorithms such as sampling-based methods and mini-batch k-means are already fast.
• Distance estimation requires many repetitions for good precision, adding overhead.
• No demonstration has outperformed classical clustering on real data.

Common misconceptions

• Quantum k-means does not always give the same clusters as classical k-means. Estimation noise changes the results slightly.
• It does not remove the need to choose k or to deal with poor initialization.
• An exponential speedup claim depends entirely on the data access model.

How it compares

• Classical k-means is simple, fast, and parallelizable.
• Quantum PCA and quantum support vector machines share the same input assumptions.
• Quantum anomaly detection uses similar distance and projection ideas.

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.

Why it matters

Clustering is among the most common machine learning tasks, so a quantum speedup would have broad effects. The q-means work also set a standard for stating assumptions and running noise-aware simulations in quantum machine learning papers.

The field's experience, with a claimed exponential gain followed by classical dequantization, is a good case study for how to judge claims in the area.

Frequently asked questions

Keep learning

• Related algorithm: SWAP Test
• Related algorithm: Quantum Principal Component Analysis
• Related algorithm: Quantum Support Vector Machine
• Related algorithm: Quantum Random Access Memory (QRAM)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database