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:2001.01077 · ACM Transactions on Quantum Computing

Quantum Machine Learning Algorithm for Knowledge Graphs

Yunpu Ma, Volker Tresp C

Published Sep 30, 2021• 21 citations
arXivHTMLPDF

Abstract

Semantic knowledge graphs are large-scale triple-oriented databases for knowledge representation and reasoning. Implicit knowledge can be inferred by modeling the tensor representations generated from knowledge graphs. However, as the sizes of knowledge graphs continue to grow, classical modeling becomes increasingly computationally resource intensive. This article investigates how to capitalize on quantum resources to accelerate the modeling of knowledge graphs. In particular, we propose the first quantum machine learning algorithm for inference on tensorized data, i.e., on knowledge graphs. Since most tensor problems are NP-hard [18], it is challenging to devise quantum algorithms to support the inference task. We simplify the modeling task by making the plausible assumption that the tensor representation of a knowledge graph can be approximated by its low-rank tensor singular value decomposition, which is verified by our experiments. The proposed sampling-based quantum algorithm achieves speedup with a polylogarithmic runtime in the dimension of knowledge graph tensor.

DOI
10.1145/3467982

Related papers

Quantum Negative Sampling Strategy for Knowledge Graph Embedding with Variational Circuit

Pulak Ranjan Giri, Mori Kurokawa, Kazuhiro Saito

Knowledge graph is a collection of facts, known as triples(head, relation, tail), which are represented in form of a network, where nodes are entities and edges are relations among the respective head and tail entities. Embedding of knowledge graph for facilitating downstream tasks such as knowledge graph completion, link prediction, recommendation, has been a major area of research recently in classical machine learning. Because the size of knowledge graphs are becoming larger, one of the natural choices is to exploit quantum computing for knowledge graph embedding. Recently, a hybrid quantum classical model for knowledge graph embedding has been studied in which a variational quantum circuit is trained. One of the important aspects in knowledge graph embedding is the sampling of negative triples, which plays a crucial role in efficient training of the model. In classical machine learning various negative sampling strategies have been studied. In quantum knowledge graph embedding model, although we can use these strategies in principle, it is natural to ask if we can exploit quantum advantage in negative sampling. In this article we study such a negative sampling strategy, which exploits quantum superposition, and evaluate the model's performance with a knowledge graph database.

arXiv:2502.17973•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•4 citations

Towards a Native Quantum Paradigm for Graph Representation Learning: A Sampling-based Recurrent Embedding Approach

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

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 Quantum Graph Neural Networks: An Ego-Graph Learning Approach

Ai, Xing, Zhihong Zhang, Luzhe Sun +2 more

Quantum machine learning is a fast-emerging field that aims to tackle machine learning using quantum algorithms and quantum computing. Due to the lack of physical qubits and an effective means to map real-world data from Euclidean space to Hilbert space, most of these methods focus on quantum analogies or process simulations rather than devising concrete architectures based on qubits. In this paper, we propose a novel hybrid quantum-classical algorithm for graph-structured data, which we refer to as the Ego-graph based Quantum Graph Neural Network (egoQGNN). egoQGNN implements the GNN theoretical framework using the tensor product and unity matrix representation, which greatly reduces the number of model parameters required. When controlled by a classical computer, egoQGNN can accommodate arbitrarily sized graphs by processing ego-graphs from the input graph using a modestly-sized quantum device. The architecture is based on a novel mapping from real-world data to Hilbert space. This mapping maintains the distance relations present in the data and reduces information loss. Experimental results show that the proposed method outperforms competitive state-of-the-art models with only 1.68\% parameters compared to those models.

arXiv:2201.05158•Jan 13, 2022•32 citations

Machine Learning Algorithms in Quantum Computing: A Survey

Somayeh Bakhtiari Ramezani, Alexander Sommers, Harish Kumar Manchukonda +2 more

Machine Learning (ML) aims at designing models that learn from previous experience, without being explicitly formulated. Applications of machine learning are inexhaustible, including recognizing patterns, predicting future trends and making decisions, and they are capable of handling sizable quantities of multi-dimensional data in the form of large vectors and tensors. To perform these operations on classical computers, however, requires vast time and computational resources. Unlike the classical computers that rely on computations using binary bits, Quantum Computers (QC) benefit from qubits which can hold combinations of 0 and 1 at the same time via superposition and entanglement. This makes QCs powerful at handling and post processing large tensors, making them a prime target for implementing ML algorithms. While several models used for ML on QCs are based on concepts from their classical computing counterparts, utilization of the QC's potential has made them the superior of the two. This paper presents an overview of the current state of knowledge in application of ML on QC, and evaluates the speed up, and complexity advantages of using quantum machines.

International Joint Conference on Neural Networks (IJCNN)•Jul 1, 2020•138 citations

Quantum Algorithms for Linear Algebra and Machine Learning.

Anupam Prakash

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

•Jan 1, 2014•51 citations
Semantic knowledge graphs are large-scale triple-oriented databases for knowledge representation and reasoning. Implicit knowledge can be inferred by modeling the tensor representations generated from knowledge graphs. However, as the sizes of knowledge graphs continue to grow, classical modeling becomes increasingly computationally resource intensive. This article investigates how to capitalize on quantum resources to accelerate the modeling of knowledge graphs. In particular, we propose the first quantum machine learning algorithm for inference on tensorized data, i.e., on knowledge graphs. Since most tensor problems are NP-hard [18], it is challenging to devise quantum algorithms to support the inference task. We simplify the modeling task by making the plausible assumption that the tensor representation of a knowledge graph can be approximated by its low-rank tensor singular value decomposition, which is verified by our experiments. The proposed sampling-based quantum algorithm achieves speedup with a polylogarithmic runtime in the dimension of knowledge graph tensor.
Knowledge graph is a collection of facts, known as triples(head, relation, tail), which are represented in form of a network, where nodes are entities and edges are relations among the respective head and tail entities. Embedding of knowledge graph for facilitating downstream tasks such as knowledge graph completion, link prediction, recommendation, has been a major area of research recently in classical machine learning. Because the size of knowledge graphs are becoming larger, one of the natural choices is to exploit quantum computing for knowledge graph embedding. Recently, a hybrid quantum classical model for knowledge graph embedding has been studied in which a variational quantum circuit is trained. One of the important aspects in knowledge graph embedding is the sampling of negative triples, which plays a crucial role in efficient training of the model. In classical machine learning various negative sampling strategies have been studied. In quantum knowledge graph embedding model, although we can use these strategies in principle, it is natural to ask if we can exploit quantum advantage in negative sampling. In this article we study such a negative sampling strategy, which exploits quantum superposition, and evaluate the model's performance with a knowledge graph database.
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.
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.
Quantum machine learning is a fast-emerging field that aims to tackle machine learning using quantum algorithms and quantum computing. Due to the lack of physical qubits and an effective means to map real-world data from Euclidean space to Hilbert space, most of these methods focus on quantum analogies or process simulations rather than devising concrete architectures based on qubits. In this paper, we propose a novel hybrid quantum-classical algorithm for graph-structured data, which we refer to as the Ego-graph based Quantum Graph Neural Network (egoQGNN). egoQGNN implements the GNN theoretical framework using the tensor product and unity matrix representation, which greatly reduces the number of model parameters required. When controlled by a classical computer, egoQGNN can accommodate arbitrarily sized graphs by processing ego-graphs from the input graph using a modestly-sized quantum device. The architecture is based on a novel mapping from real-world data to Hilbert space. This mapping maintains the distance relations present in the data and reduces information loss. Experimental results show that the proposed method outperforms competitive state-of-the-art models with only 1.68\% parameters compared to those models.
Machine Learning (ML) aims at designing models that learn from previous experience, without being explicitly formulated. Applications of machine learning are inexhaustible, including recognizing patterns, predicting future trends and making decisions, and they are capable of handling sizable quantities of multi-dimensional data in the form of large vectors and tensors. To perform these operations on classical computers, however, requires vast time and computational resources. Unlike the classical computers that rely on computations using binary bits, Quantum Computers (QC) benefit from qubits which can hold combinations of 0 and 1 at the same time via superposition and entanglement. This makes QCs powerful at handling and post processing large tensors, making them a prime target for implementing ML algorithms. While several models used for ML on QCs are based on concepts from their classical computing counterparts, utilization of the QC's potential has made them the superior of the two. This paper presents an overview of the current state of knowledge in application of ML on QC, and evaluates the speed up, and complexity advantages of using quantum machines.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.