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

arXiv:2011.05128

Laplacian Eigenmaps with variational circuits: a quantum embedding of graph data

Slimane Thabet, Jean-François Hullo

Published Nov 10, 2020• 1 citation
arXivHTMLPDF

Abstract

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($rn^2$), $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.

DOI
10.48550/arxiv.2011.05128

Related papers

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•2 citations

VQNE: Variational Quantum Network Embedding with Application to Network Alignment

Xinyu Ye, Ge Yan, Junchi Yan

Learning of network embedding with vector-based node representation has attracted wide attention over the decade. It differs from the general setting of graph node embedding whereby the node attributes are also considered and yet may incur privacy issues. In this paper, we depart from the classic CPU/GPU architecture to consider the well-established network alignment problem based on network embedding, and develop a quantum machine learning approach with a low qubit cost for its near-future applicability on Noisy Intermediate-Scale Quantum (NISQ) devices. Specifically, our model adopts the discrete-time quantum walk (QW) and conducts the QW on the tailored merged network to extract structure information from the two aligning networks without the need for quantum state preparation which otherwise requires high quantum gate cost. Then the quantum states from QW are fed to a quantum embedding ansatz (i.e., parameterized circuit) to learn the latent representation of each node. The key part of our approach is to connect these two quantum modules to achieve a pure quantum paradigm without involving classical modules. To our best knowledge, there has not been any classic-quantum hybrid approach to network embedding, let alone a pure quantum paradigm being free from the bottleneck of communication between classic devices and quantum devices, which is still an open problem. Experimental results on two real-world datasets show the effectiveness of our quantum embedding approach in comparison with classical embedding approaches. Our model is readily and efficiently implemented in Python with a full-amplitude simulation of the QW and the quantum circuit. Therefore, our model can be readily deployed on an existing NISQ device with all the circuits provided, and only 13 qubits are needed in the experiments, which is rarely attained in existing quantum graph learning works.

ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)•Aug 4, 2023•9 citations

Variational quantum algorithm for node embedding

Zengrong Zhou, Hang Li, Gui‐Lu Long

Quantum machine learning has made remarkable progress in many important tasks. However, the gate complexity of the initial state preparation is seldom considered in lots of quantum machine learning algorithms, making them non-end-to-end. Herein, we propose a quantum algorithm for the node embedding problem that maps a node graph’s topological structure to embedding vectors. The resulting quantum embedding state can be used as an input for other quantum machine learning algorithms. With O(log(N)) qubits to store the information of N nodes, our algorithm will not lose quantum advantage for the subsequent quantum information processing. Moreover, owing to the use of a parameterized quantum circuit with O(poly(log(N))) depth, the resulting state can serve as an efficient quantum database. In addition, we explored the measurement complexity of the quantum node embedding algorithm, which is the main issue in training parameters, and extended the algorithm to capture high-order neighborhood information between nodes. Finally, we experimentally demonstrated our algorithm on an nuclear magnetic resonance quantum processor to solve a graph model.

Fundamental Research•Oct 14, 2023•10 citations

Enhancing the performance of variational quantum classifiers with hybrid autoencoders

Georgios Maragkopoulos, Aikaterini Mandilara, Antonia Tsili +1 more

Abstract Variational quantum circuits (VQC) lie at the forefront of quantum machine learning research. Still, the use of quantum networks for real data processing remains challenging as the number of available qubits cannot accommodate a large dimensionality of data—if the usual angle encoding scenario is used. To achieve dimensionality reduction, Principal Component Analysis is routinely applied as a pre-processing method before the embedding of the classical features on qubits. In this work, we propose an alternative method which reduces the dimensionality of a given dataset by taking into account the specific quantum embedding that comes after. This method aspires to make quantum machine learning with VQCs more versatile and effective on datasets of high dimension. At a second step, we propose a quantum-inspired classical autoencoder model which can be used to encode information in low latent spaces. The power of our proposed models is exhibited via numerical tests. We show that our targeted dimensionality reduction method considerably boosts VQC’s performance, and we also identify cases for which the second model outperforms classical autoencoders in terms of reconstruction loss.

arXiv:2409.03350•Quantum Information Processing•Jul 30, 2025•11 citations

A Quantum Algorithm for Solving Eigenproblem of the Laplacian Matrix of a Fully Connected Weighted Graph

Hailing Liu, Lin‐Chun Wan, Chao‐Hua Yu +4 more

Abstract Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block‐encoding framework is adopted to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of this entire algorithm is to construct a block‐encoding of the Laplacian matrix. To achieve this, how to construct block‐encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block‐encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non‐symmetric) normalized Laplacian matrix.

arXiv:2203.14451•Advanced Quantum Technologies•Apr 28, 2023•10 citations

Quantum Machine Learning for High Dimensional Data Classification: A Variational Algorithm Approach

Jami Venkata Suman, Omprakash Gurrapu, Silpa Kesav Velagaleti +3 more

Quantum machine learning offers the ability to change the significant task of classifying high-dimensions data by taking advantage of infinite-dimensional, enriched state spaces granting a net benefit of quantum computation. We offer a variational quantum algorithm that accommodates many use cases in quantum computing to classify large-scale and high-dimensions data in real time and in cloud-all computing environments. We created our unique quantum circuits; we optimized the parameterized gates using either gradient methods or gradients-free methods and we investigated quantum kernels that provide the capability to identify embeddings in Hilbert space. Our experimental results using both customized synthetic data and benchmarks have shown that the variational quantum classifier was able to achieve comparability in accuracy to classical deep learning accuracy, while improving scale and robustness to noise. In addition, after we deployed the application in a cloud environment, we assessed latency, throughput and metrics from each cloud vendor, and we discovered that if the latency of the quantum accelerators can be controlled by a pipeline of optimized data and workloads, then they are eligible to satisfy the real-time requirement. Based on a theoretical and practical rapidly emerging basis, these results have indicated that variation quantum classifiers are a pathway for future dataintensive applications deployed in the quantum-cloud ecosystem.

International Conference on Intelligent Computing, Information and Control Systems (ICOIICS)•Nov 19, 2025•1 citation
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(rn2rn^2rn2), rrr 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 ddd first eigenvectors of the Laplacian at the same time, our algorithm directly generates a ddd 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 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.*
Learning of network embedding with vector-based node representation has attracted wide attention over the decade. It differs from the general setting of graph node embedding whereby the node attributes are also considered and yet may incur privacy issues. In this paper, we depart from the classic CPU/GPU architecture to consider the well-established network alignment problem based on network embedding, and develop a quantum machine learning approach with a low qubit cost for its near-future applicability on Noisy Intermediate-Scale Quantum (NISQ) devices. Specifically, our model adopts the discrete-time quantum walk (QW) and conducts the QW on the tailored merged network to extract structure information from the two aligning networks without the need for quantum state preparation which otherwise requires high quantum gate cost. Then the quantum states from QW are fed to a quantum embedding ansatz (i.e., parameterized circuit) to learn the latent representation of each node. The key part of our approach is to connect these two quantum modules to achieve a pure quantum paradigm without involving classical modules. To our best knowledge, there has not been any classic-quantum hybrid approach to network embedding, let alone a pure quantum paradigm being free from the bottleneck of communication between classic devices and quantum devices, which is still an open problem. Experimental results on two real-world datasets show the effectiveness of our quantum embedding approach in comparison with classical embedding approaches. Our model is readily and efficiently implemented in Python with a full-amplitude simulation of the QW and the quantum circuit. Therefore, our model can be readily deployed on an existing NISQ device with all the circuits provided, and only 13 qubits are needed in the experiments, which is rarely attained in existing quantum graph learning works.
Quantum machine learning has made remarkable progress in many important tasks. However, the gate complexity of the initial state preparation is seldom considered in lots of quantum machine learning algorithms, making them non-end-to-end. Herein, we propose a quantum algorithm for the node embedding problem that maps a node graph’s topological structure to embedding vectors. The resulting quantum embedding state can be used as an input for other quantum machine learning algorithms. With O(log(N)) qubits to store the information of N nodes, our algorithm will not lose quantum advantage for the subsequent quantum information processing. Moreover, owing to the use of a parameterized quantum circuit with O(poly(log(N))) depth, the resulting state can serve as an efficient quantum database. In addition, we explored the measurement complexity of the quantum node embedding algorithm, which is the main issue in training parameters, and extended the algorithm to capture high-order neighborhood information between nodes. Finally, we experimentally demonstrated our algorithm on an nuclear magnetic resonance quantum processor to solve a graph model.
Abstract Variational quantum circuits (VQC) lie at the forefront of quantum machine learning research. Still, the use of quantum networks for real data processing remains challenging as the number of available qubits cannot accommodate a large dimensionality of data—if the usual angle encoding scenario is used. To achieve dimensionality reduction, Principal Component Analysis is routinely applied as a pre-processing method before the embedding of the classical features on qubits. In this work, we propose an alternative method which reduces the dimensionality of a given dataset by taking into account the specific quantum embedding that comes after. This method aspires to make quantum machine learning with VQCs more versatile and effective on datasets of high dimension. At a second step, we propose a quantum-inspired classical autoencoder model which can be used to encode information in low latent spaces. The power of our proposed models is exhibited via numerical tests. We show that our targeted dimensionality reduction method considerably boosts VQC’s performance, and we also identify cases for which the second model outperforms classical autoencoders in terms of reconstruction loss.
Abstract Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block‐encoding framework is adopted to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of this entire algorithm is to construct a block‐encoding of the Laplacian matrix. To achieve this, how to construct block‐encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block‐encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non‐symmetric) normalized Laplacian matrix.
Quantum machine learning offers the ability to change the significant task of classifying high-dimensions data by taking advantage of infinite-dimensional, enriched state spaces granting a net benefit of quantum computation. We offer a variational quantum algorithm that accommodates many use cases in quantum computing to classify large-scale and high-dimensions data in real time and in cloud-all computing environments. We created our unique quantum circuits; we optimized the parameterized gates using either gradient methods or gradients-free methods and we investigated quantum kernels that provide the capability to identify embeddings in Hilbert space. Our experimental results using both customized synthetic data and benchmarks have shown that the variational quantum classifier was able to achieve comparability in accuracy to classical deep learning accuracy, while improving scale and robustness to noise. In addition, after we deployed the application in a cloud environment, we assessed latency, throughput and metrics from each cloud vendor, and we discovered that if the latency of the quantum accelerators can be controlled by a pipeline of optimized data and workloads, then they are eligible to satisfy the real-time requirement. Based on a theoretical and practical rapidly emerging basis, these results have indicated that variation quantum classifiers are a pathway for future dataintensive applications deployed in the quantum-cloud ecosystem.