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

Fundamental Research

Variational quantum algorithm for node embedding

Zengrong Zhou, Hang Li, Gui‐Lu Long

Published Oct 14, 2023• 10 citations
Publisher

Abstract

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.

DOI
10.1016/j.fmre.2023.10.001

Related papers

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

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

Slimane Thabet, Jean-François Hullo

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.

arXiv:2011.05128•Nov 10, 2020•1 citation

Fast Variational Knowledge Graph Embedding

Pulak Ranjan Giri, Mori Kurokawa, Kazuhiro Saito

Embedding of a knowledge graph(KG) entities and relations in the form of vectors is an important aspect for the manipulation of the KG database for several downstream tasks, such as link prediction, knowledge graph completion, and recommendation. Because of the growing size of the knowledge graph databases, it has become a daunting task for the classical computer to train a model efficiently. Quantum computer can help speedup the embedding process of the KGs by encoding the entities into a variational quantum circuit of polynomial depth. Usually, the time complexity for such variational circuit-dependent quantum classical algorithms for each epoch is O(Npoly(logM)), where$N$is number of elements in the knowledge graph and$M$is the number of features of each entities of the knowledge graph. In this article we exploit additional quantum advantage by training multiple elements of KG in superpositions, thereby reducing the computing time further for the knowledge graph embedding model.

arXiv:2507.02472•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

Towards a Native Quantum Paradigm for Graph Representation Learning

Ge Yan, Yehui Tang, Junchi Yan

Graph representation learning has been extensively studied, and recent models can well incorporate both node features and graph structures. Despite these progress, the inherent scalability challenge for classical computers of processing graph data and solving the downstream tasks (many are NP-hard) is still a bottleneck for existing classical graph learning models. On the other hand, quantum computing is known a promising direction for its theoretically verified scalability as well as the increasing evidence for the access to physical quantum machine in near-term. Different from many existing classical-quantum hybrid machine learning models on graphs, in this paper we take a more aggressive initiative for developing a native quantum paradigm for (attributed) graph representation learning, which to our best knowledge, has not been fulfilled in literature yet. Specifically, our model adopts the well-established theory and technique in quantum computing e.g. quantum random walk, and adapt it to the attributed graph. Then the node attribute quantum state sequence is fed into a quantum recurrent network to obtain the final node embedding. Experimental results on three public datasets show the effectiveness of our quantum model which also outperforms a classical learning approach GraphRNA notably in terms of efficiency even on a classical computer. Though it is still restricted to the classical loss-based learning paradigm with gradient descent for model parameter training, while our computing scheme is compatible with quantum computing without involving classical computers. This is in fact largely in contrast to many hybrid quantum graph learning models which often involve many steps and modules having to be performed on classical computers.

ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)•Aug 12, 2022•5 citations

Finding Key Nodes in Complex Networks Through Quantum Deep Reinforcement Learning

Juechan Xiong, Xiao-Long Ren, Linyuan Lü

Identifying key nodes in networks is a fundamental problem in network science. This study proposes a quantum deep reinforcement learning (QDRL) framework that integrates reinforcement learning with a variational quantum graph neural network, effectively identifying distributed influential nodes while preserving the network's fundamental topological properties. By leveraging principles of quantum computing, our method is designed to reduce model parameters and computational complexity compared to traditional neural networks. Trained on small networks, it demonstrated strong generalization across diverse scenarios. We compared the proposed algorithm with some classical node ranking and network dismantling algorithms on various synthetical and empirical networks. The results suggest that the proposed algorithm outperforms existing baseline methods. Moreover, in synthetic networks based on Erdős-Rényi and Watts-Strogatz models, QDRL demonstrated its capability to alleviate the issue of localization in network information propagation and node influence ranking. Our research provides insights into addressing fundamental problems in complex networks using quantum machine learning, demonstrating the potential of quantum approaches for network analysis tasks.

Entropy•Apr 3, 2025•5 citations

Variational Quantum Circuit Model for Knowledge Graphs Embedding

Yunpu Ma, Volker Tresp, Liming Zhao +1 more

In this work, we propose the first quantum Ansätze for the statistical relational learning on knowledge graphs using parametric quantum circuits. We introduce two types of variational quantum circuits for knowledge graph embedding. Inspired by the classical representation learning, we first consider latent features for entities as coefficients of quantum states, while predicates are characterized by parametric gates acting on the quantum states. For the first model, the quantum advantages disappear when it comes to the optimization of this model. Therefore, we introduce a second quantum circuit model where embeddings of entities are generated from parameterized quantum gates acting on the pure quantum state. The benefit of the second method is that the quantum embeddings can be trained efficiently meanwhile preserving the quantum advantages. We show the proposed methods can achieve comparable results to the state-of-the-art classical models, e.g., RESCAL, DistMult. Furthermore, after optimizing the models, the complexity of inductive inference on the knowledge graphs might be reduced with respect to the number of entities.

arXiv:1903.00556•Feb 19, 2019•0 citations
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.
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.
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.
Embedding of a knowledge graph(KG) entities and relations in the form of vectors is an important aspect for the manipulation of the KG database for several downstream tasks, such as link prediction, knowledge graph completion, and recommendation. Because of the growing size of the knowledge graph databases, it has become a daunting task for the classical computer to train a model efficiently. Quantum computer can help speedup the embedding process of the KGs by encoding the entities into a variational quantum circuit of polynomial depth. Usually, the time complexity for such variational circuit-dependent quantum classical algorithms for each epoch is O(Npoly(logM)), whereNNNis number of elements in the knowledge graph andMMMis the number of features of each entities of the knowledge graph. In this article we exploit additional quantum advantage by training multiple elements of KG in superpositions, thereby reducing the computing time further for the knowledge graph embedding model.
Graph representation learning has been extensively studied, and recent models can well incorporate both node features and graph structures. Despite these progress, the inherent scalability challenge for classical computers of processing graph data and solving the downstream tasks (many are NP-hard) is still a bottleneck for existing classical graph learning models. On the other hand, quantum computing is known a promising direction for its theoretically verified scalability as well as the increasing evidence for the access to physical quantum machine in near-term. Different from many existing classical-quantum hybrid machine learning models on graphs, in this paper we take a more aggressive initiative for developing a native quantum paradigm for (attributed) graph representation learning, which to our best knowledge, has not been fulfilled in literature yet. Specifically, our model adopts the well-established theory and technique in quantum computing e.g. quantum random walk, and adapt it to the attributed graph. Then the node attribute quantum state sequence is fed into a quantum recurrent network to obtain the final node embedding. Experimental results on three public datasets show the effectiveness of our quantum model which also outperforms a classical learning approach GraphRNA notably in terms of efficiency even on a classical computer. Though it is still restricted to the classical loss-based learning paradigm with gradient descent for model parameter training, while our computing scheme is compatible with quantum computing without involving classical computers. This is in fact largely in contrast to many hybrid quantum graph learning models which often involve many steps and modules having to be performed on classical computers.
Identifying key nodes in networks is a fundamental problem in network science. This study proposes a quantum deep reinforcement learning (QDRL) framework that integrates reinforcement learning with a variational quantum graph neural network, effectively identifying distributed influential nodes while preserving the network's fundamental topological properties. By leveraging principles of quantum computing, our method is designed to reduce model parameters and computational complexity compared to traditional neural networks. Trained on small networks, it demonstrated strong generalization across diverse scenarios. We compared the proposed algorithm with some classical node ranking and network dismantling algorithms on various synthetical and empirical networks. The results suggest that the proposed algorithm outperforms existing baseline methods. Moreover, in synthetic networks based on Erdős-Rényi and Watts-Strogatz models, QDRL demonstrated its capability to alleviate the issue of localization in network information propagation and node influence ranking. Our research provides insights into addressing fundamental problems in complex networks using quantum machine learning, demonstrating the potential of quantum approaches for network analysis tasks.
In this work, we propose the first quantum Ansätze for the statistical relational learning on knowledge graphs using parametric quantum circuits. We introduce two types of variational quantum circuits for knowledge graph embedding. Inspired by the classical representation learning, we first consider latent features for entities as coefficients of quantum states, while predicates are characterized by parametric gates acting on the quantum states. For the first model, the quantum advantages disappear when it comes to the optimization of this model. Therefore, we introduce a second quantum circuit model where embeddings of entities are generated from parameterized quantum gates acting on the pure quantum state. The benefit of the second method is that the quantum embeddings can be trained efficiently meanwhile preserving the quantum advantages. We show the proposed methods can achieve comparable results to the state-of-the-art classical models, e.g., RESCAL, DistMult. Furthermore, after optimizing the models, the complexity of inductive inference on the knowledge graphs might be reduced with respect to the number of entities.