Quantum tensor singular value decomposition with applications to recommendation systems

Abstract

In this paper, we present a quantum singular value decomposition algorithm for third-order tensors inspired by the classical algorithm of tensor singular value decomposition (t-svd) and then extend it to order-$p$ tensors. It can be proved that the quantum version of the t-svd for a third-order tensor $\mathcal{A}\in {\mathbb{R}}^{N\times N\times N}$ achieves the complexity of $\mathcal{O}(N\mathrm{polylog}(N))$, an exponential speedup compared with its classical counterpart. As an application, we propose a quantum algorithm for recommendation systems which incorporates the contextual situation of users to the personalized recommendation. We provide recommendations varying with contexts by measuring the output quantum state corresponding to an approximation of this user's preferences. This algorithm runs in expected time $\mathcal{O}(N\mathrm{polylog}(N)\mathrm{poly}(k)),$ if every frontal slice of the preference tensor has a good rank-$k$ approximation. At last, we provide a quantum algorithm for tensor completion based on a different truncation method which is tested to have a good performance in dynamic video completion.

arXiv comment29 pages, 5 figure. Comments are welcome!

References in corpus (9)

• Quantum principal component analysis
• Quantum random access memory
• Quantum gradient descent for linear systems and least squares
• Quantum singular value decomposition of non-sparse low-rank matrices
• Quantum Circulant Preconditioner for Linear System of Equations
• How entangled can a multi-party system possibly be?
• Generalized Tensor Function via the Tensor Singular Value Decomposition based on the T-Product
• Quantum Machine Learning Algorithm for Knowledge Graphs
• Quantum Higher Order Singular Value Decomposition

Cited by in corpus (1)

• Quantum Higher Order Singular Value Decomposition