Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM/IEEE Design Automation Conference (DAC)

Quantum Spectral Clustering of Mixed Graphs

Daniel Volya, Prabhat Mishra

Published Nov 8, 2021• 15 citations
Publisher

Abstract

Spectral graph partitioning is a well known technique to estimate clusters in undirected graphs. Recent approaches explored efficient spectral algorithms for directed and mixed graphs utilizing various matrix representations. Despite its success in clustering tasks, classical spectral algorithms suffer from a cubic growth in runtime. In this paper, we propose a quantum spectral clustering algorithm for discovering clusters and properties of mixed graphs. Our experimental results based on numerical simulations demonstrate that our quantum spectral clustering outperforms classical spectral clustering techniques. Specifically, our approach leads to a linear growth in complexity, while state-of-the-art classical counterpart leads to cubic growth. In a case study, we apply our proposed algorithm to preform unsupervised machine learning using both real and simulated quantum computers. This work opens an avenue for efficient implementation of machine learning algorithms on directed as well as mixed graphs by making use of the inherent potential quantum speedup.

DOI
10.1109/dac18074.2021.9586308

Related papers

Quantum spectral clustering

Iordanis Kerenidis, Jonas Landman

Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with nonconvex or nested structures [A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference (MIT Press, Cambridge, MA, 2002), pp. 849--856]. 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 data set. 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 analog of the $k$-means algorithm [I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, $q$-means: A quantum algorithm for unsupervised machine learning, in Advances in Neural Information Processing Systems 32: Proceedings of the 2019 Conference (Curran Associates, Red Hook, NY, 2020), pp. 4136--4146]. 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.

arXiv:2007.00280•Physical Review A•Apr 15, 2021•74 citations

Quantum Algorithm for Regularized Spectral Clustering

Changzhou Long, Yasunori Futamura, Xiucai Ye +1 more

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.

International Conference on Machine Learning and Computing (ICMLC)•Feb 17, 2023•2 citations

Quantum hybrid algorithm and subroutines for image segmentation based on spectral clustering and graph cuts

José Ignacio Espinoza Camacho

The increasing size of data sets is a motivation to develop new optimal and low complexity algorithms. Quantum computing is a promising alternative, as it provides computational speed-up for some problems. Spectral clustering algorithms are unsupervised machine learning algorithms that make use of the space of eigenvalues and eigenvectors (spectrum) of matrices derived from the data to make an efficient partition. However, this spectral transformation becomes computationally expensive when dealing with thousands or even hundreds of data points, as is the case for the segmentation of large images. Recently, a new quantum algorithm for spectral clustering [1] proved a speed-up over the classical algorithm. In this work, we propose a quantum hybrid algorithm for image segmentation based on spectral clustering with normalized cuts [1, 2] and graph cuts. Our work compares our image segmentation results with those produced by normalized cuts.

•Nov 22, 2022•0 citations

Approximate graph spectral decomposition with the Variational Quantum Eigensolver

Josh Payne, Mario Srouji

Spectral graph theory is a branch of mathematics that studies the relationships between the eigenvectors and eigenvalues of Laplacian and adjacency matrices and their associated graphs. The Variational Quantum Eigen- solver (VQE) algorithm was proposed as a hybrid quantum/classical algorithm that is used to quickly determine the ground state of a Hamiltonian, and more generally, the lowest eigenvalue of a matrix M ∈ Rnxn. There are many interesting problems associated with the spectral decompositions of associated matrices, such as partitioning, embedding, and the determination of other properties. In this paper, we will expand upon the VQE algorithm to analyze the spectra of directed and undirected graphs. We evaluate runtime and accuracy comparisons (empirically and theoretically) between different choices of ansatz parameters, graph sizes, graph densities, and matrix types, and demonstrate the effectiveness of our approach on Rigetti's QCS platform on graphs of up to 64 vertices, finding eigenvalues of adjacency and Laplacian matrices. We finally make direct comparisons to classical performance with the Quantum Virtual Machine (QVM) in the appendix, observing a superpolynomial runtime improvement of our algorithm when run using a quantum computer.*

arXiv:1912.12366•Apr 27, 2020•3 citations

Advanced Quantum Algorithms for Big Data Clustering and High-Dimensional Classification

José Gabriel Carrasco Ramírez

The exponential growth of data and the increasing complexity of high-dimensional classification problems have pushed classical computing methods to their limits. Quantum computing emerges as a promising paradigm to address these challenges. This research article explores advanced quantum algorithms for big data clustering and high-dimensional classification. We investigate quantum versions of K-means, spectral clustering, and support vector machines, comparing their performance with classical counterparts. Our results demonstrate significant speedups in processing time and improvements in clustering quality for high-dimensional datasets. Additionally, we propose a novel quantum-inspired classical algorithm that bridges the gap between quantum and classical approaches. This comprehensive study provides insights into the potential of quantum computing in revolutionizing data analysis and machine learning, paving the way for future advancements in the field.

Journal of Advanced Computing Systems•Jun 8, 2024•0 citations

Accelerating spectral clustering on quantum and analog platforms

Xingzi Xu, Tuhin Sahai

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.

arXiv:2408.08486•Academia quantum.•Mar 24, 2025•2 citations
Spectral graph partitioning is a well known technique to estimate clusters in undirected graphs. Recent approaches explored efficient spectral algorithms for directed and mixed graphs utilizing various matrix representations. Despite its success in clustering tasks, classical spectral algorithms suffer from a cubic growth in runtime. In this paper, we propose a quantum spectral clustering algorithm for discovering clusters and properties of mixed graphs. Our experimental results based on numerical simulations demonstrate that our quantum spectral clustering outperforms classical spectral clustering techniques. Specifically, our approach leads to a linear growth in complexity, while state-of-the-art classical counterpart leads to cubic growth. In a case study, we apply our proposed algorithm to preform unsupervised machine learning using both real and simulated quantum computers. This work opens an avenue for efficient implementation of machine learning algorithms on directed as well as mixed graphs by making use of the inherent potential quantum speedup.
Spectral clustering is a powerful unsupervised machine learning algorithm for clustering data with nonconvex or nested structures [A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference (MIT Press, Cambridge, MA, 2002), pp. 849--856]. 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(n3)O({n}^{3})O(n3), where nnn is the number of points in the data set. 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 analog of the kkk-means algorithm [I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, qqq-means: A quantum algorithm for unsupervised machine learning, in Advances in Neural Information Processing Systems 32: Proceedings of the 2019 Conference (Curran Associates, Red Hook, NY, 2020), pp. 4136--4146]. 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 nnn 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.
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.
The increasing size of data sets is a motivation to develop new optimal and low complexity algorithms. Quantum computing is a promising alternative, as it provides computational speed-up for some problems. Spectral clustering algorithms are unsupervised machine learning algorithms that make use of the space of eigenvalues and eigenvectors (spectrum) of matrices derived from the data to make an efficient partition. However, this spectral transformation becomes computationally expensive when dealing with thousands or even hundreds of data points, as is the case for the segmentation of large images. Recently, a new quantum algorithm for spectral clustering [1] proved a speed-up over the classical algorithm. In this work, we propose a quantum hybrid algorithm for image segmentation based on spectral clustering with normalized cuts [1, 2] and graph cuts. Our work compares our image segmentation results with those produced by normalized cuts.
Spectral graph theory is a branch of mathematics that studies the relationships between the eigenvectors and eigenvalues of Laplacian and adjacency matrices and their associated graphs. The Variational Quantum Eigen- solver (VQE) algorithm was proposed as a hybrid quantum/classical algorithm that is used to quickly determine the ground state of a Hamiltonian, and more generally, the lowest eigenvalue of a matrix M ∈ Rnxn. There are many interesting problems associated with the spectral decompositions of associated matrices, such as partitioning, embedding, and the determination of other properties. In this paper, we will expand upon the VQE algorithm to analyze the spectra of directed and undirected graphs. We evaluate runtime and accuracy comparisons (empirically and theoretically) between different choices of ansatz parameters, graph sizes, graph densities, and matrix types, and demonstrate the effectiveness of our approach on Rigetti's QCS platform on graphs of up to 64 vertices, finding eigenvalues of adjacency and Laplacian matrices. We finally make direct comparisons to classical performance with the Quantum Virtual Machine (QVM) in the appendix, observing a superpolynomial runtime improvement of our algorithm when run using a quantum computer.*
The exponential growth of data and the increasing complexity of high-dimensional classification problems have pushed classical computing methods to their limits. Quantum computing emerges as a promising paradigm to address these challenges. This research article explores advanced quantum algorithms for big data clustering and high-dimensional classification. We investigate quantum versions of K-means, spectral clustering, and support vector machines, comparing their performance with classical counterparts. Our results demonstrate significant speedups in processing time and improvements in clustering quality for high-dimensional datasets. Additionally, we propose a novel quantum-inspired classical algorithm that bridges the gap between quantum and classical approaches. This comprehensive study provides insights into the potential of quantum computing in revolutionizing data analysis and machine learning, paving the way for future advancements in the field.
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.