中科院数学与系统科学研究院
数学研究所
学术报告
计算机科学研讨班
报告人：左钱 博士（北京大学前沿计算研究中心）
题 目：A novel and faster quantum-inspired algorithm for solving linear systems
时 间：2023.04.14（星期五）14:30-15:30
地 点：数学院南楼N802
摘 要：In this talk, we introduce a modified classical algorithm to solve linear systems in a model that resembles the QRAM used by quantum linear solvers. Specifically, we demonstrate that for the linear system Ax = b, there exists a classical algorithm that produces a data structure for x with the ability to sample and query its entries. The resulting x satisfies ||x - A^{-1}b|| <= eps*||A^{-1}b||. This output can be considered as a classical analogue to the output obtained by quantum linear solvers. Our algorithm's complexity is roughly ~O(kappa_{F}^2 kappa^3 / eps^2 + kappa_{F}^4 kappa), where kappa_{F} = ||A||_{F} ||A^{-1}||_2, kappa = ||A||_2 ||A^{-1}||_2. This novel algorithm improves over the previous best-known one in terms of time complexity, namely ~O(kappa_{F}^6 kappa^2 / eps^2) in [Shao, Montanaro, ACM Transactions on Quantum Computing]. The algorithm we have investigated can be regarded as an accelerated average randomized Kaczmarz algorithm with the heavy ball momentum method. The theoretical analysis depends on the careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices.
附件：