Variational Quantum Approximated Spectral Clustering

Clustering is a fundamental task for analyzing unlabeled data based solely on its underlying distribution. Spectral clustering is a clustering method that represents a dataset as a graph and uses the relationships between data points. However, classical spectral clustering methods incur high computational costs that can scale cubically with the dataset size-as is typical for approaches that involve solving eigenvalue problems. In this work, we propose Variational Quantum Approximated Spectral Clustering (VQASC), which extends quantum distance-based classifier models to the clustering framework. Our approach uses efficient quantum circuit designs whose depth scales sub-quadratically with dataset size, enabling the computation of weighted sums over various matrix representations of an undirected graph. Furthermore, we adopt an empirical risk formulation to reduce the impact of local minima arising from parameterized quantum circuits, and we validate our approach through simulations on real-world datasets.