Efficient quantum algorithms for solving quantum linear system problems

Abstract

We transform the problem of solving linear system of equations $A\mathbf{x}=\mathbf{b}$ to a problem of finding the right singular vector with singular value zero of an augmented matrix $C$, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left(s\kappa \log \left(1/\epsilon \right)\right)$ for a $s$-sparse matrix $C$, where $\kappa$ is the condition number of the matrix $A$, and $\epsilon$ is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[s\kappa +\log \left(1/\epsilon \right)/\log \log \left(1/\epsilon \right)\right]$. Both algorithms meet the optimal query complexity in $\kappa$, and are simpler than previous algorithms.

13 pages, reformulate the algorithms, more materials are added