Randomized Row and Column Iterative Methods with a Quantum Computer
This work provides a quantum speedup for widely used iterative linear system solvers, benefiting large-scale data science applications.
The authors propose quantum implementations of the Kaczmarz and coordinate descent methods for solving linear systems, achieving exponential speedup in problem size and nearly linear complexity in the number of steps compared to classical versions.
We consider the quantum implementations of the two classical iterative solvers for a system of linear equations, including the Kaczmarz method which uses a row of coefficient matrix in each iteration step, and the coordinate descent method which utilizes a column instead. These two methods are widely applied in big data science due to their very simple iteration schemes. In this paper we use the block-encoding technique and propose fast quantum implementations for these two approaches, under the assumption that the quantum states of each row or each column can be efficiently prepared. The quantum algorithms achieve exponential speed up at the problem size over the classical versions, meanwhile their complexity is nearly linear at the number of steps.