Quantum Machine Learning Algorithm for Knowledge Graphs
arXiv:2001.01077
Abstract
Semantic knowledge graphs are large-scale triple-oriented databases for knowledge representation and reasoning. Implicit knowledge can be inferred by modeling and reconstructing the tensor representations generated from knowledge graphs. However, as the sizes of knowledge graphs continue to grow, classical modeling becomes increasingly computational resource intensive. This paper investigates how quantum resources can be capitalized to accelerate the modeling of knowledge graphs. In particular, we propose the first quantum machine learning algorithm for making inference on tensorized data, e.g., on knowledge graphs. Since most tensor problems are NP-hard, it is challenging to devise quantum algorithms to support that task. We simplify the problem by making a 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 exponential speedup with a runtime that is polylogarithmic in the dimension of knowledge graph tensor.
References in corpus (11)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- A Review of Relational Machine Learning for Knowledge Graphs
- Quantum principal component analysis
- Quantum random access memory
- Quantum singular value decomposition of non-sparse low-rank matrices
- Quantum Recommendation Systems
- Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of non-sparse low rank matrices
- Tensor sparsification via a bound on the spectral norm of random tensors
- Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization