Computing a Sparse Approximate Inverse on Quantum Annealing Machines

Many engineering problems involve solving large linear systems of equations. Conjugate gradient (CG) is one of the most popular iterative methods for solving such systems. CG typically requires a good preconditioner to speed up convergence, and computing these preconditioners can be challenging. In this paper, we explore whether any of the popular preconditioners can be computed today using quantum computers. We demonstrate that sparse approximate inverse (SPAI) preconditioners can be computed efficiently using quantum annealing machines. Specifically, we provide an extension of the box algorithm for computing the SPAI of very large matrices on D-Wave Advantage machines. The computation of an SPAI reduces to solving a series of quadratic unconstrained binary optimization (QUBO) problems. This is demonstrated using both well-conditioned and poorly-conditioned linear systems arising from a 2D finite difference formulation of the Poisson problem.