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.
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.*
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.
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.
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.
Abstract. Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with [Formula: see text] nodes and [Formula: see text] edges, outputs a classical description of an [Formula: see text]-spectral sparsifier in sublinear time [Formula: see text]. This contrasts with the optimal classical complexity [Formula: see text]. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for [Formula: see text]-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.
Graph clustering, the process of grouping nodes in a graph based on their relationships, is a cornerstone of numerous data analysis applications, including social network analysis, bioinformatics, and anomaly detection. Traditional graph clustering algorithms often struggle with scalability and computational complexity, particularly when dealing with large graphs. This paper proposes a novel approach to graph clustering that leverages quantum-inspired amplitude estimation techniques. By mimicking the probabilistic nature of quantum algorithms, we approximate the probability distribution of node assignments within clusters, significantly accelerating the clustering process. Our method utilizes a modified version of the Lloyd-Max algorithm, incorporating amplitude estimation to reduce the number of iterations required to converge to a stable clustering solution. We demonstrate, through theoretical analysis and algorithmic design, that this approach can achieve comparable or superior clustering performance compared to conventional methods, while exhibiting a markedly reduced computational footprint. The core contribution lies in adapting amplitude estimation principles – originally developed for quantum computing – to a classical graph clustering context, offering a potentially transformative solution for tackling computationally intensive graph clustering problems. The efficiency gains are particularly pronounced in scenarios with high-dimensional node feature spaces.