Quantum k-Means Clustering
Accelerating the assignment step of k-means using quantum distance estimation and amplitude amplification.
Classical k-means
k-means partitions N data points into k clusters by alternating two steps: assign each point to its nearest centroid, then recompute each centroid as the mean of its assigned points. The assignment step dominates cost, requiring N times k distance evaluations, each in dimension d, giving O(N k d) per iteration.
Quantum distance estimation
The core quantum subroutine estimates the distance or inner product between two vectors encoded as quantum states. The swap test measures the overlap |
Speedups in the loop
- Distance to a centroid computed via swap test on amplitude-encoded vectors.
- Nearest-centroid search accelerated with Grover-style minimum finding.
- Amplitude encoding makes per-distance cost scale with log d rather than d.
The q-means variant
A well-known formulation, sometimes called q-means, achieves per-iteration cost polylogarithmic in N and d under the assumption of efficient quantum access to the data (quantum RAM). It returns centroids close to those of a robust classical k-means, with running time depending on cluster separation and desired accuracy rather than on N directly.
Assumptions and caveats
The speedup requires amplitude encoding of data and fast quantum memory, both nontrivial to build; the cost of loading data can erase the advantage if it must be done from scratch each run. Outputs are cluster assignments and centroids, which must be read out classically. As with much quantum machine learning, the benefit is real only when data access is favorable and the pipeline keeps results in quantum form as long as possible. See quantum SVM for a related classifier.