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/ϵ\right)\right)$ for a $s$-sparse matrix $C$, where $\kappa$ is the condition number of the matrix $A$, and $ϵ$ 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] $.Bothalgorithmsmeettheoptimalquerycomplexityin$\kappa $, and are simpler than previous algorithms.