基于QR迭代的量子奇异值分解
Quantum Singular Value Decomposition Based on QR Iteration
-
摘要: 针对大型矩阵奇异值分解(singular value decomposition, SVD)时使用经典算法时间复杂度较高, 以及已有的量子SVD算法要求待分解的矩阵必须具有非稀疏低秩的性质, 并且在计算过程中构造任意大小酉矩阵对目前的量子计算机来说实现起来并不容易等问题, 提出基于QR迭代的量子SVD。QR迭代使用的是Householder变换, 通过量子矩阵乘法运算完成经典矩阵乘法运算过程。实验结果表明, 该方法能够得到所求矩阵的奇异值及奇异矩阵, 使大型矩阵的SVD具有可行性。Abstract: Aiming at the high computational complexity of classical algorithms for the singular value decomposition (SVD) of large matrices, as well as the limitations of existing quantum SVD algorithms that require the matrix to be decomposed to possess non-sparse, low-rank characteristics, and the difficulty of constructing unitary matrices of arbitrary size for current quantum computers, a quantum SVD algorithm based on QR iteration was introduced. QR iteration is a numerical algorithm for calculating the eigenvalues and eigenvectors of matrices. The QR iteration leverages Householder transformations to execute the classical matrix multiplication operations via quantum matrix multiplication computations. Results show that the proposed approach can obtain the singular values and singular matrices of the target matrix, and it is feasible to perform SVD on large-scale matrices.