Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices

Abstract

In the field of quantum linear system algorithms, quantum computing has realized exponential computational advantages over classical computing. However, the focus has been on square coefficient matrices, with few quantum algorithms addressing non-square matrices. Towards this kind of problems defined by $Ax=b$ where $A$$\in {\mathbb{R}}^{m\times n}$, we propose a quantum algorithm inspired by the classical multi-row iteration method and provide an explicit quantum circuit based on the quantum comparator and Quantum Random Access Memory (QRAM). The time complexity of our quantum multi-row iteration algorithm is $O(K\log m)$, with $K$ representing the number of iteration steps, which demonstrates an exponential speedup compared to the classical version. Based on the convergence of the classical multi-row iteration algorithm, we prove that our quantum algorithm converges faster than the quantum one-row iteration algorithm presented in [Phys. Rev. A, 101, 022322 (2020)]. Moreover, our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems and quadratic optimization problems.

References in corpus (14)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• A quantum linear system algorithm for dense matrices
• Randomized Kaczmarz solver for noisy linear systems
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum gradient descent for linear systems and least squares
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Variational quantum simulations of stochastic differential equations
• Randomized Row and Column Iterative Methods with a Quantum Computer
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test