Solution of Sparse Matrix Equations Using HHL Algorithm with Quantum Walk Unitary Operator

Quantum algorithms offer significant scaling advantages over their classical counterparts. In this talk we consider a quantum algorithm for the solution of matrix equations. This algorithm is a modification of the well-known Harrow/Hassidim/Lloyd (HHL) procedure, that includes additional considerations for the implementation of the main unitary operator. The procedure makes use of an operator adopted from research into quantum walks, and it provides a direct, complete method for the solution of any well-conditioned matrix equation. Efficiency is controlled by the time needed to provide an element-wise description of the matrix. Hence, for sparse matrices, this algorithm can outperform classical solvers by a significant margin. This result is valuable for problems wherein a matrix is well-conditioned and can be described quickly, but the structure of the matrix makes efficient application of its inverse difficult.