左钱博士,北京大学前沿计算研究中心

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.