Quantum tensor singular value decomposition*

Xiaoqiang Wang, Lejia Gu, Heung Wing Lee, Guofeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time O(Npolylog(N)) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.

Original languageEnglish
Article number075001
Pages (from-to)1-15
Number of pages15
JournalJournal of Physics Communications
Volume5
Issue number7
DOIs
Publication statusPublished - 2 Jul 2021

Keywords

  • Quantum fourier transform
  • Quantum singular value estimation
  • T-product
  • T-svd
  • Tensor singular value decomposition

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Cite this