Quantum Algorithm for Regularized Spectral Clustering
Changzhou Long, Yasunori Futamura, Xiucai Ye, Tetsuya Sakurai · 2023
Spectral clustering is one of the most robust methods of an unsupervised machine learning field. Compared with the well-known k-means, spectral clustering uses the spectral properties of the Laplacian matrix to project data to a low-dimensional clustering with higher efficiency. However, for a sparse network with a substantial degree of heterogeneity, standard spectral clustering often overfits noise in the periphery of a sparse and stochastic graph. In our work, we combined the quantum version of the k-means algorithm with regularized spectral clustering and proposed a new quantum machine learning algorithm. It is more like a combination of classical and quantum algorithms. Compared with the established quantum k-means algorithm, our method has obvious computational advantages in non-convex or nested structures. At this stage, the research of quantum algorithms mainly stays in the simulation of classical computers. Our method does not need to expend a lot of effort to preprocess the data at the initial quantum state stage. Under the assumption of quantum data encoding, we theoretically demonstrate the feasibility of the quantum regularized spectral clustering algorithm. Then combine Q-means algorithm complexity advantages to complete the clustering task. This work aims to pave the path and help realize quantum spectral clustering algorithms on real quantum computers in the future and help create other versions of quantum machine learning algorithms. We provide simulations and data examples to illustrate these results.