Row and column iteration methods to solve linear systems on a quantum computer

We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size $n$ over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\kappa }_s^2(logn)\left(log\frac{1}{\epsilon }\right))$, where ${\kappa }_s$ is the scaled condition number, and $\epsilon$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.

Figure 1

Illustrative example of Kaczmarz iteration in dimension 2.