To begin with, unlabeled data is flooding the data space at an unprecedented rate. Labels are expensive; there is a need to deal with unlabeled data in an effective and efficient way. Quantum computing can offer a significant speedup over traditional classical unsupervised learning algorithms, which has large implications for dealing with this flow of unsupervised information.
The traditional classical k-means algorithm is commonly used for clustering. Using repeated alternation between two steps, the algorithm returns the locations of the “centroids” (center of each cluster):
- Label assignment. Each data point is assigned the label of the closest centroid. (Centroid locations are randomly set initially.)
- Centroid estimation. Update each centroid to be the average of the data points assigned to the corresponding cluster.
Consider, now, δ-k-means, which can be thought of as a noisy — but still classical — version of k-means. Assume δ is a preset parameter. The algorithm alternates between the same two steps, with some added noise:
- Label assignment. Each data point is assigned a random centroid whose distance is less than δ. That is, any centroid whose distance from the data point is less than a threshold has an equal chance of assignment.
- Centroid estimation. During the calculation of the location of each centroid, add δ/2 Gaussian noise.
Lastly, consider q-means, which is a truly quantum variant of k-means. As a quick prerequisite, recall that qubits contain probabilities; this makes them especially prone to measurement errors and noise from the environment, as opposed to bits.
- Label assignment. Estimate via quantum methods the distance between each data point and the centroid. Because of noise, this quantum distance estimation will have a certain level of noise. Then, assign each data point to a centroid.
- Centroid estimation. Using the same quantum tomography idea discussed in the sampling step of the QCNN method, states that can be measured correctly with a high probability are “converted” into classical form. There is, again, a certain level of noise inherent in this operation.
q-means seems very similar to k-means. The difference, though, is the noise; the introduction of δ-k-means acts as the “classical version” of q-means that captures that element of noise. The proposers behind q-means prove that analyzing δ-k-means can reveal information about how the q-means algorithm runs.
For instance, the δ-k-means algorithm often converges to a clustering that achieves a similar, if not better, accuracy than the k-means algorithm, when the (non-zero) value of δ is selected appropriately. Thus — while there is less freedom in choosing the amount of noise in the quantum variant — one can expect q-means to perform reasonably well to k-means.
Similarly, the δ-k-means algorithm is polylogarithmic in its running time. The q-means algorithm, then, is also polylogarithmic, a speedup over the k-means algorithm allowed for by introducing some error and relaxing stricter and more precise calculations.
Currently, q-means is too complex for quantum simulators nor quantum computers to test. However, via the δ-k-means algorithm, there is empirical evidence that q-means can perform generally at a similar level to k-means.
What is the purpose of quantum clustering, then? Further research may allow for clustering of quantum states or data, as well as spatial clustering of molecules and other very small phenomena — a very important task. In general, quantum methods seem to have some potential to surpass classical methods at traditional tasks as well.