EUVIMEDEUVIMED entdecken
Crossref

Accelerating spectral clustering on quantum and analog platforms

Xingzi Xu, Tuhin Sahai

Academia Quantum · 2025

DOI: 10.20935/acadquant7587 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Academia Quantum, 2025. Verfasst von Xingzi Xu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 61 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce a novel hybrid quantum–analog algorithm to perform a graph clustering that exploits connections between the evolution of dynamical systems on graphs and the underlying graph spectra. This approach constitutes a new class of algorithms that combine emerging quantum and analog platforms to accelerate computations. Our hybrid algorithm is equivalent to spectral clustering and significantly reduces the computational complexity from 𝒪(N3) to 𝒪(N), where N is the number of nodes in the graph. We achieve this speedup by circumventing the need for explicit eigendecomposition of the normalized graph Laplacian matrix, which dominates the classical complexity, and instead leveraging quantum evolution of the Schrödinger equation followed by efficient analog computation for the dynamic mode decomposition (DMD) step. Specifically, while classical spectral clustering requires 𝒪(N3) operations to perform eigendecomposition, our method exploits the natural quantum evolution of states according to the graph Laplacian Hamiltonian in linear time, combined with the linear scaling for DMD that leverages efficient matrix–vector multiplications on analog hardware. We prove and demonstrate that this hybrid approach can extract the eigenvalues and scaled eigenvectors of the normalized graph Laplacian by evolving Schrödinger dynamics on quantum computers followed by DMD computations on analog devices, providing a significant computational advantage for large-scale graph clustering problems. Our demonstrations can be reproduced using our code that has been released at on github.

Zitieren

APA

Xu, X., & Sahai, T. (2025). Accelerating spectral clustering on quantum and analog platforms. Academia Quantum. https://doi.org/10.20935/acadquant7587

Vancouver

Xu X, Sahai T. Accelerating spectral clustering on quantum and analog platforms. Academia Quantum. 2025. doi:10.20935/acadquant7587

BibTeX
@article{Xu2025,
  author = {Xu, Xingzi and Sahai, Tuhin},
  title = {Accelerating spectral clustering on quantum and analog platforms},
  journal = {Academia Quantum},
  year = {2025},
  doi = {10.20935/acadquant7587}
}
Kostenlos starten →