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

We study a hybrid quantum-classical solver for systems of linear equations using quantum random walk, applied to stoquastic Hamiltonian matrices [1]. In the absence of quantum noise, sparse matrices are expected to achieve solution vectors with lower error than dense matrices. We find that quantum noise reverses this effect, with error increasing as sparsity increases. This is a consequence of a corresponding increase in the number of invalid quantum random walks. We propose an improved algorithm that mitigates invalid quantum random walks.

[1] Chih-Chieh Chen et al, “Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines”, Sci. Reports 9, 16251 (2019)