Quantum Spectral Clustering Framework via Compact Circuit Structures

Spectral machine learning methods based on spectral graph theory are powerful but scale poorly due to costly eigen‐analysis. Although various eigenvector approximation methods have been proposed, the construction of a partial kernel matrix still remains within their frameworks. This work presents compact quantum circuit designs for spectral clustering in which the eigenproblem is approximated via a Rayleigh–Ritz formulation that bypasses kernel matrix construction and whose overall depth is dominated by the data‐embedding routine. A rigorous shot complexity analysis is provided, showing that the sampling‐based estimation remains tractable for the spectral clustering objective including a penalty term. Simulations on canonical datasets demonstrate reliable optimization behavior with an under‐parameterized hardware‐efficient ansatz. Finite‐shot simulations further confirm the predicted sampling behavior of the penalty estimator, validating the main claims as a proof of concept.