Quantum tensor singular value decomposition with applications to recommendation systems
This work addresses the computational bottleneck in tensor-based machine learning for quantum computing, offering potential speedups in applications like recommendation systems, but it is incremental as it builds on classical tensor SVD methods.
The paper tackles the problem of decomposing high-order tensors and applying it to recommendation systems, achieving an exponential speedup with complexity O(N polylog(N)) for quantum tensor SVD compared to classical methods, and proposes a quantum recommendation algorithm running in O(N polylog(N) poly(k)) time for personalized, context-aware recommendations.
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{\rm 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{\rm polylog}(N){\rm 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.