Computing a Sparse Approximate Inverse on Quantum Annealing Machines

Abstract

Abstract. 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 article, we demonstrate that a particular preconditioner, namely, sparse approximate inverse (SPAI), can be computed efficiently using quantum annealing machines. Specifically, we provide an extension of the box algorithm for computing the SPAI of 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 several poorly conditioned linear systems arising from a 2D finite-difference formulation of the Poisson problem.