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.
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 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 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), 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.
Clustering hyperspectral images is a complex task that requires careful consideration of the data's high dimensionality, noise, and redundancy. Spectral clustering has proven to be a powerful tool for analyzing hyperspectral images, due to its ability to capture non-linear relationships and intricate structures, providing robust clustering results even in highdimensional, complex datasets. By leveraging a combination of pre-processing techniques, and clustering algorithms, it is possible to effectively cluster hyperspectral data and extract meaningful information. In this work, we presented a hybrid approach of spectral clustering by utilizing quantum computing's ability to process complex, high-dimensional spaces and compute similarity measures more efficiently. This experiment demonstrates that when quantum kernel was used for clustering, the quality of the clusters improved significantly. Implementation of these quantum algorithms is currently limited by the number of qubits, gate fidelity, and coherence time of existing quantum computers. Despite these challenges, as quantum hardware and algorithms continue to evolve, this hybrid quantum-classical approach to spectral clustering holds promise for future applications.
With the development of quantum algorithms, high-cost computations are being scrutinized in the hope of a quantum advantage. While graphs offer a convenient framework for multiple real-world problems, their analytics still comes with high computation and space. By mapping the graph data into a low dimensional space, in which graph structural information is preserved, the eigenvectors of the Laplacian matrix constitute a powerful node embedding, called Laplacian Eigenmaps. Computing these embeddings is on its own an expensive task knowing that using specific sparse methods, the eigendecomposition of a Laplacian matrix has a cost of O(
rn2),
r being the ratio of nonzero elements. We propose a method to compute a Laplacian Eigenmap using a quantum variational circuit. The idea of our algorithm is to reach the eigenstates of the laplacian matrix, which can be considered as a hamiltonian operator, by adapting the variational quantum eigensolver algorithm. By estimating the
d first eigenvectors of the Laplacian at the same time, our algorithm directly generates a
d dimension quantum embedding of the graph. We demonstrate that it is possible to use the embedding for graph machine learning tasks by implementing a quantum classifier on the top of it. The overall circuit consists in a full quantum node classification algorithm. Tests on 32 nodes graph with a quantum simulator shows that we can achieve similar performances as the classical laplacian eigenmap algorithm. Although mathematical properties of this approximate approach are not fully understood, this algorithm opens perspectives for graph pre-processing using noisy quantum computers.
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.