Quantum algorithms for tensor decompositions and machine learning

Abstract

Tensor decompositions have been proved to be useful in a number of applications, such as data completion, recommendation systems, multi-partite quantum systems, etc. Some of these applications exploit low structural complexity of the data, expressed either as low rank for the matrices, or low tensor-rank under some tensor decompositions, such as higher-order singular value decomposition (HOSVD), tensor singular value decomposition (t-svd), etc. In this thesis, we focus on exploring several novel applications of the tensor t-svd decomposition. The t-svd decomposition extends the familiar matrix svd strategy to tensors and perform matrix svd in the Fourier domain. However, the complexity of calculating full t-svd is extremely high especially for large scale datasets. Hence in our work, we present the first quantum t-svd algorithm for third-order tensors which achieves polynomial speedup compared with its classical counterpart, and then extend it to order p tensors. To our best knowledge, the efficiency of this algorithm beats any known classical t-svd algorithms in the literature. Quantum machine learning investigates how quantum techniques can be used to speed up some classical machine learning problems. Based on the proposed quantum t-svd algorithm, we next extend Kerenidis and Prakash's matrix recommendation system algorithm to third-order tensors, and propose a quantum machine learning algorithm, context-aware recommendation systems algorithm, based on truncated t-svd factorization. In fact, our algorithm offers recommendations by just sampling from an approximated preference matrix, which corresponds to measuring certain times a quantum state representing a user' approximated preference information, instead of reconstructing the entire tensor as its classical counterpart does. Therefore, the running time is polylogrithmic in the dimension of the preference tensor. Inspired by the Monte-Carlo randomized algorithm for finding the low-rank matrix approximations proposed by Frieze, Kannan and Vempala, we present a classical Monte-Carlo low tubal-rank tensor approximation algorithm based on truncated t-svd. The main idea is approximating the original tensor by performing truncated matrix svd on every frontal slice of the small sampled tensor under Fourier domain. In terms of time complexity, our algorithm achieves a polynomial speedup compared with the classical truncated t-svd algorithm. In the final part of our work, two schemes for the effective generation of large-size Schrodinger's cat states are proposed based on conditioned measurement, which provides a powerful resource for quantum information technology based on the superposition of coherent states. The schemes are based on the linear operation of Fock states and squeezed vacuum states. The simulation results shows that odd cat states with an amplitude of 2.001 with the fidelity of 0.99 could be obtained.