On Quantum Solvers for Linear Algebraic Systems

Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.