Effect of matrix sparsity and quantum noise on quantum random walk linear solvers

Abstract

We study the effects of quantum noise in hybrid quantum-classical solver for sparse systems of linear equations using quantum random walks, applied to stoquastic Hamiltonian matrices. In an ideal noiseless quantum computer, sparse matrices achieve solution vectors with lower relative error than dense matrices. However, we find quantum noise reverses this effect, with overall error increasing as sparsity increases. We identify invalid quantum random walks as the cause of this increased error and propose a revised linear solver algorithm which improves accuracy by mitigating these invalid walks.