Clustering using matrix product states

The matrix product state has been demonstrated to be able to explore the most relevant portion of the exponentially large quantum Hilbert space and find accurate solutions for one-dimensional interacting quantum many-body systems. Inspired by this success, here we propose a clustering algorithm based on the matrix product state, which first maps the classical data into quantum states represented as matrix product states, and then minimizes the loss function using a variational matrix product states algorithm in the enlarged space. We demonstrate this algorithm by applying it to several commonly used machine learning data sets, showing that this algorithm could reach higher learning precision and that it is less likely to be trapped in local minima compared to the standard K-means algorithm. We also show that this algorithm can achieve state-of-the-art learning precision on popular computer vision data sets when used in combination with better initialization schemes.

Figure 1

(a) Learning accuracy (blue dashed line with triangle) and NMI (red dashed line with circle) as a function of the bond dimension $D$ for our MPS clustering algorithm. The blue solid and red solid lines are the corresponding values of the K-means algorithm. (b) Distribution of learning accuracy for 100 trials for the K-means algorithm (black solid line) and our MPS clustering algorithms with different bond dimensions (dashed lines).

Figure 2

Structures for (a) our AE-MPS clustering algorithm and (b) ADSSC-MPS clustering algorithm. The fully connected autoencoder is used here, and the number of neurons in each layer is written below each layer.

Figure 3

(a), (b) Histograms of learning accuracies and NMIs for MNIST. (c), (d) Histograms of learning accuracies and NMIs for USPS. (e), (f) Histograms of learning accuracies and NMIs for FashionMNIST. The cyan, red, and yellow bars stand for $D=1,4,16$, respectively.

Figure 4

(a) The loss value as a function of the number of K-means iterations for the K-means algorithm. (b) The loss value as a function of the number of sweeps for MPS clustering with $D=8$ (blue line) and $D=16$ (yellow line), respectively. For MPS clustering we have used three sweeps in each K-means like the iteration. Here the Yeast data set is used. The loss values in both cases are divided by their initial values.

Figure 5

Inner product between the learned centroids for the K-means algorithm (left panel) and for MPS clustering with $D=8$ (right panel). Here the Yeast data set is used.