154.com皇冠学术报告

Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems

左钱

（北京大学前沿计算研究中心）

报告时间：2023年8月8日 星期二 下午16:00-17:00

报告地点：沙河校区E404  

报告摘要：Quantum-inspired classical algorithms have become a popular research topic in theoretical computer science, showing that for many quantum algorithms with complexity poly-logarithmic in problem size, there exist classical algorithms using sampling-based data structures with complexity at most a polynomial of the quantum counterpart. However, the degree of this polynomial is typically large, which is at least 6 in current state-of-the-art results~[Chia et al., JACM 69 (5), 1-72, 2022] and prohibits practical applications of quantum-inspired classical algorithms.

In this paper, we propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A \in \Rc^{m\times n}$ and a vector $b\in \Rc^{m}$, we propose classical algorithms that produce a data structure for the solution $x\in \Rc^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\|x - A^{+}b\| \leq \epsilon \|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm and $A^{+}$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(\kappa_{F}^{4}/\kappa \epsilon^{2})$ in the general case, where $\kappa_{F} = \|A\|_{F} \|A^{+}\|$ and $\kappa =\|A\| \|A^{+}\|$ are condition numbers. Compared to the prior state-of-the-art result with complexity $\widetilde{O} ( \kappa_{F}^{4} \kappa^{2}/\epsilon^{2})$~[Shao andMontanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s \kappa^2_{F}/\kappa {\log}(1/\epsilon))$, matching the quantum lower bound for solving linear systems in $\kappa$ and $1/\epsilon$ up to poly-logarithmic factors~[Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s \sqrt{\kappa}{\log}(1/\epsilon))$.

Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices, which achieves tighter convergence and may be of independent interest.

Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.

报告人简介：左钱，北京大学计算机学院前沿计算中心博士后，合作导师：李彤阳，北京大学助理教授。2022年获得武汉大学理学博士学位。研究兴趣包括量子计算、受量子启发的经典算法、量子机器学习和随机算法。

邀请人： 谢家新