PaperlayerView exact revision on arXiv

Source-linked AI summary

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, Anupam Prakash

arXiv:1812.03584v2quant-phcs.LG

TL;DR

As unlabelled datasets grow, more powerful processing methods are needed, motivating quantum approaches to unsupervised clustering. The paper introduces q-means as a quantum counterpart to robust δ-k-means, with outputs consistent with δ-k-means and running time polylogarithmic in dataset size. Simulations report performance similar to k-means, while the method provides explicit centroids for later use.

  • Problem

    Growing volumes of largely unlabelled data require more powerful processing methods, while quantum machine learning algorithms may offer speedups over classical approaches.

  • Method

    The paper introduces q-means, a quantum clustering algorithm equivalent to the robust δ-k-means algorithm, for well-clusterable datasets stored in QRAM.

  • Results

    q-means outputs with high probability centroids consistent with δ-k-means, with running time polylogarithmic in dataset size and linear in feature dimension.

  • Takeaways & Limitations

    Simulations show q-means has performance similar to k-means, while its explicit classical centroids can support subsequent classical or quantum classification.

  • Takeaways & Limitations

    The running-time parameter η is a maximum-square-norm worst-case guarantee, whereas practical scaling may follow the average square norm; after PCA on MNIST, these values were 8.3 and 2.65.

Abstract

from arXiv · show

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The $q$-means algorithm has convergence and precision guarantees similar to $k$-means, and it outputs with high probability a good approximation of the $k$ cluster centroids like the classical algorithm. Given a dataset of $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $η$ and the error parameter $δ$. Both running times are only polylogarithmic in the number of datapoints $N$. Our algorithm provides substantial savings compared to the classical $k$-means algorithm that runs in time $O(kdN)$ per iteration, particularly for the case of large datasets.

1 Introduction

The paper introduces q-means as a quantum alternative to k-means for unsupervised clustering, with outputs consistent with robust δ-k-means and running time polylogarithmic in dataset size. Its guarantees and tighter well-clusterable-data analysis target substantial savings over classical clustering, especially for large datasets.

  • Context: The algorithm assumes quantum access to data, as do several quantum machine-learning procedures discussed in prior work.Related quantum clustering approaches include quantum distance estimation, minimum finding, and adiabatic assignment methods.
  • Contribution: q-means is a quantum clustering algorithm designed as an alternative to classical k-means and equivalent to robust δ-k-means.Its output is analyzed for consistency with δ-k-means.
  • Classical baseline: Classical k-means decreases RSS toward a local minimum, but each iteration costs O(kNd) because every vector is compared with every centroid.Finding the global RSS minimum is NP-hard.
  • Quantum algorithm: q-means outputs classical descriptions of cluster centroids with running time polylogarithmic in N and linear in feature dimension d.The centroids can be used in subsequent classical or quantum classification algorithms.
  • Well-clusterable data: For well-clusterable datasets, q-means has a tighter running-time analysis and is intended to cluster most data points correctly under a suitable constant δ.The model uses well-separated centroids with points sampled from small-variance Gaussian distributions.

2 Quantum preliminaries

The paper introduces quantum-computing primitives for encoding data, manipulating matrices, estimating amplitudes, and recovering classical vectors from quantum states. These tools support the quantum processing used by q-means.

  • Representations: Data points and centroids are represented as rows of matrices V and C_t, with suitable QRAM structures assumed for the algorithmic analysis.A vector state |v⟩ is the normalized encoding of a vector v.
  • Data access: QRAM stores dataset rows and supports quantum state-preparation unitaries for indexed vectors in logarithmic time.The data structure supports inserting, updating, and deleting entries in O(log^2(N)) time and state preparation in T = O(log^2 N).
  • Quantum linear algebra: Quantum linear algebra procedures apply matrix multiplication, inversion, and norm estimation with costs depending on condition number, matrix parameter µ, and precision.These procedures assume QRAM storage and provide states approximating Mx or M^-1x, together with norm estimates.
  • Classical recovery: Vector-state tomography reconstructs a classical approximation of a quantum state using O(d log d/ϵ^2) calls to its state-preparation unitary.The reconstruction has Euclidean error at most ϵ with probability at least 1 − 1/poly(d).

3 Modelling well-clusterable datasets

The paper defines well-clusterable datasets through centroid separation, proximity of most points to their nearest centroid, and a distance-separation condition. This model supports correctness guarantees and tighter bounds on quantum linear-algebra parameters and running time.

  • Assumptions: The model normalizes data so 1 ≤ ||v_i|| and defines η = max_i ||v_i||^2, while assuming each of k clusters contains at least Ω(N/k) points.These assumptions are used to derive tighter running-time bounds rather than to define the general q-means algorithm.
  • Definition: Well-clusterable datasets have centroids separated by at least ξ, at least λN points within β of their nearest centroid, and a further η-dependent separation condition.The definition uses constants ξ, β > 0, λ ∈ [0, 1], and η ≤ 1.
  • Low-rank structure: A well-clusterable dataset has a useful rank-k approximation, which is later used to bound the quantum algorithm’s running time.Such datasets can be constructed from separated cluster centers with points sampled from low-variance Gaussian distributions around them.
  • Running-time analysis: Well-clusterability is used to establish bounds on µ(V) and κ(V), the matrix parameters governing quantum linear-algebra running times.The supplied passages identify these parameters as the focus of the tighter analysis.
  • Condition thresholding: Truncating singular values below τ preserves the matrix within Frobenius error at most (ϵ′ + ϵτ)||V||F under the stated rank-k approximation assumption.The threshold is τ = ϵτ√k ||V||F.
  • Clustering guarantee: For at least λN points, any δ-k-means parameter satisfying δ < ξ^2 − 2√ηβ yields correct cluster assignments.The guarantee follows because competing centroids remain more than δ farther away than the nearest centroid.

4 The q-means algorithm

q-means follows the classical k-means structure while replacing its main operations with quantum distance estimation, minimum finding, matrix multiplication, and tomography. The procedure assigns points, creates centroid states, recovers classical centroids, and repeats until convergence.

  • Algorithm structure: q-means begins with k initial centroids stored in QRAM and iteratively performs distance estimation, assignment, centroid-state creation, and centroid update.The algorithm continues until its convergence condition is satisfied.
  • Cluster assignment: The assignment step selects the centroid with minimum estimated distance, using a quantum minimum-finding circuit that costs O(k log p).Because squaring is monotone, q-means need not compute square roots before selecting the closest centroid.
  • Centroid-state creation: Centroid states are created by measuring label registers and multiplying V^T by the resulting cluster state using quantum linear algebra.The matrix-multiplication step uses relative error ϵ3.
  • Centroid update: Tomography converts the updated centroid states into classical vectors, whose QRAM representations replace the previous centroids.The recovered centroid error is bounded by √η(ϵ3 + ϵ4).
  • Centroid distance estimation: Quantum distance estimation maps indexed data points and centroids to estimates of squared distances or inner products with controlled additive error and high probability.The procedure assumes QRAM access to vector states and known vector norms.
  • Distance-estimation mechanism: Distance estimation combines normalized-state overlap estimation with the product of vector norms to recover distances or inner products for unnormalized vectors.Amplitude estimation and median evaluation provide the distance estimates while reversing the circuit removes garbage states.

5 Analysis

The analysis establishes that q-means can match classical δ-k-means assignments and centroids with high probability while giving per-iteration runtimes polylogarithmic in N. For well-clusterable data, thresholding the condition number yields a specialized runtime bound and preserves this consistency.

  • General guarantees: High probability q-means outputs centroids consistent with classical δ-k-means for QRAM-stored V.The general theorem provides the algorithm’s runtime and accuracy guarantee.
  • Assignment accuracy: ϵ1 < δ/2 ensures q-means does not select a centroid whose distance exceeds the minimum by more than δ.Assignments estimate all point-centroid squared distances, then choose the minimum without additional error.
  • Centroid accuracy: ϵ3 < δ/(4√η) and ϵ4 < δ/(4√η) make centroid updates consistent with classical δ-k-means; ϵ2 affects only a logarithmic factor.Updates use quantum matrix multiplication, norm estimation, and tomography to obtain classical centroid descriptions.
  • Runtime analysis: The general per-iteration runtime combines centroid-state preparation, norm estimation, tomography, and error-dependent quantum subroutines.Centroid-state preparation depends on κ(V)(µ(V) + Tχ), while tomography costs scale with k and d.
  • Well-clusterable datasets: For well-clusterable data, q-means returns consistent centroids with high probability and has a runtime polynomial in k, d, η, and 1/δ.The analysis replaces the condition number with a thresholded condition number by discarding sufficiently small singular values.
  • Runtime implications: The runtime is only polylogarithmic in N, giving an improvement over classical k-means when the dataset size dominates the other parameters.The algorithm retains the classical δ-k-means output and iteration count while reducing dependence on the number of data points.

6 Simulations on real data

The simulations evaluate δ-k-means as a classical proxy for q-means on Gaussian clusters and MNIST, using accuracy and multiple clustering metrics. Results show convergence comparable to k-means, with performance depending on δ and preprocessing.

  • 6.1 Gaussian clusters dataset: 20,000 points in 10 dimensions formed 4 Gaussian clusters, with dataset condition number 5.06.The synthetic data were generated from Gaussian distributions and normalized so η = 4.
  • 6.1 Gaussian clusters dataset: 100% accuracy was reached in a few steps on the Gaussian dataset for the tested convergent δ values.Convergence persisted until η/δ = 3, corresponding to δ = 1.2; larger δ caused later accuracy growth from boundary-point assignments.
  • 6.2 MNIST: PCA preprocessing reduced MNIST from 784 dimensions to 40, yielding η = 8.25 and condition number 4.53.The MNIST dataset contains 60,000 handwritten-digit images originally represented by 28×28 pixels.
  • 6.2 MNIST: For PCA-preprocessed MNIST, k-means and δ-k-means reached similar low accuracy in the same number of steps when η/δ was about 20.The dataset is not well-clusterable under k-means without preprocessing beyond dimensionality reduction, and accuracy dropped as δ increased.
  • 6.2 MNIST: Across ACC, HOM, COMP, V-M, AMI, ARI, and RMSEC, δ-k-means with δ between 0.2 and 0.5 performed similarly to k-means, usually differing at the third decimal point.RMSEC directly compares centroids predicted by k-means and δ-k-means and applies only to the training set.
  • 6.2 MNIST: LDA preprocessing enabled k-means to reach 87% accuracy, but this supervised preprocessing is unsuitable for practical unsupervised learning.With LDA-reduced MNIST, δ-k-means converged to the same accuracy as k-means in the same number of steps.
  • 6 Simulations on real data: The experiments support convergence nearly matching regular k-means for sufficiently large δ, alongside lower q-means running time on large datasets.The simulations used classical δ-k-means because sufficiently large quantum simulators or quantum computers were unavailable.
Loading 1812.03584v2…