Quantum Spectral Clustering

Abstract

Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with non convex or nested structures. With roots in graph theory, it uses the spectral properties of the Laplacian matrix to project the data in a low-dimensional space where clustering is more efficient. Despite its success in clustering tasks, spectral clustering suffers in practice from a fast-growing running time of $O(n^3)$, where $n$ is the number of points in the dataset. In this work we propose an end-to-end quantum algorithm performing spectral clustering, extending a number of works in quantum machine learning. The quantum algorithm is composed of two parts: the first is the efficient creation of the quantum state corresponding to the projected Laplacian matrix, and the second consists of applying the existing quantum analogue of the $k$-means algorithm. Both steps depend polynomially on the number of clusters, as well as precision and data parameters arising from quantum procedures, and polylogarithmically on the dimension of the input vectors. Our numerical simulations show an asymptotic linear growth with $n$ when all terms are taken into account, significantly better than the classical cubic growth. This work opens the path to other graph-based quantum machine learning algorithms, as it provides routines for efficient computation and quantum access to the Incidence, Adjacency, and projected Laplacian matrices of a graph.

References in corpus (2)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Unsupervised Machine Learning on a Hybrid Quantum Computer

Cited by in corpus (16)

• Quantum computing for finance
• Prospects and challenges of quantum finance
• Quantum Clustering with k-Means: a Hybrid Approach
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• How quantum computing can enhance biomarker discovery
• Quantum algorithm for Neighborhood Preserving Embedding
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Quantum spectral clustering algorithm for unsupervised learning
• Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning
• Quantum diffusion map for nonlinear dimensionality reduction
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Quantum density peak clustering
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks