Quantum algorithms with tensor approach

Abstract

Recently quantum computing becomes more and more popular and realizable, and tensor is an effective method in quantum computing. This thesis is devoted to studying structured tensors and providing several quantum algorithms. Three topics are included: 1. introducing a new subclass of Hankel tensors and verifying their properties; 2. designing two quantum algorithms for higher order singular value decomposition; 3. presenting two quantum algorithms for polynomial optimization. For the first topic, a subclass of Hankel tensors called basic positive semi-definite (PSD) Hankel tensors is introduced, and the purpose is to find some low-rank basic PSD non-strong Hankel tensors. It is shown that rank-1 even order strong Hankel tensors are equivalent to rank-1 basic PSD Hankel tensors, and all even order strong Hankel tensors with rank larger than 1 can be expressed as the sum of rank-1 basic PSD Hankel tensors. Thus, the study of non-strong PSD Hankel tensors is reduced to the study of basic PSD Hankel tensors with rank larger than 1. It is proved that (i) there are no rank-2 basic PSD Hankel tensors, (ii) rank-3 basic PSD Hankel tensors with dimension no less than 3 do not exist. Furthermore, an example of basic PSD Hankel tensor whose rank equals 3 or 4 is provided. For the second topic, higher order singular value decomposition (HOSVD) is studied, as it is a vital method for analyzing big data in multilinear algebra and machine learning. We present two quantum algorithms for HOSVD. The methods allow one to decompose a tensor into a core tensor containing tensor singular values and some unitary matrices by quantum computers. Compared to the classical HOSVD algorithm, our quantum algorithms provide an exponential speedup. Furthermore, a hybrid quantum-classical algorithm of HOSVD model applied in recommendation systems is introduced. For the last topic, the quantum version of Barzilai-Borwein (BB) gradient method is proposed and applied to polynomial optimization with a unit norm constraint. It is known that gradient methods are widely used in optimization and machine learning problems. However, standard gradient descent method usually converges very slowly while BB gradient method overcomes this obstacle with nearly no more cost. Our quantum algorithms scale polylogarithmically in the dimension of solution vector. Compared with the classical counterpart, our quantum methods provide an exponential speedup, and succeed to find the optimal value in fewer iterations than the existing quantum gradient methods.