Randomized Row and Column Iterative Methods with a Quantum Computer

Abstract

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.

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• A quantum linear system algorithm for dense matrices
• Randomized Iterative Methods for Linear Systems
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Randomized Iterative Methods with Alternating Projections

Cited by in corpus (7)

• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• Practical Quantum Computing: solving the wave equation using a quantum approach
• An Application of Quantum Annealing Computing to Seismic Inversion
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• A deterministic Kaczmarz algorithm for solving linear systems
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
• Quantum relaxed row and column iteration methods based on block-encoding