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)), where
Nis number of elements in the knowledge graph and
Mis 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
QRAM, the standard model studied in quantum query complexity, requires time
O(sqrtn) to encode vectors
vinRn into quantum states. We propose simple hardware augmentations to the oracle
QRAM, that enable vectors
vinRn to be encoded in time
O(logn), 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
ketv for
AinRmtimesn, the singular value
sigmai is estimated within additive error
epsilonnormAF. The first algorithm requires time
wt1/epsilon3 and uses the approach for simulating
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/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(mnlogn+poly(1/epsilon)), the quantum algorithms have running time
O(sqrtmpoly(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
ell2 regularized regression problems, the quantum ridge regression algorithm requires time
wt1/mu2delta to output a quantum state that is
delta close to the solution, where
mu is the regularization parameter.