Preconditioned Block Encodings for Quantum Linear Systems

Abstract

Quantum linear system solvers like the Quantum Singular Value Transformation (QSVT) require a block encoding of the system matrix $A$ within a unitary operator $U_A$. Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix's effective condition number $\kappa$, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce $\kappa$ by multiplying $A$ by a preconditioner $P$. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding $A$ and its preconditioner $P$, followed by quantum multiplication, and (b) classically multiplying $A$ and $P$ before encoding the product in $U_{PA}$. Their impact on subnormalisation factors and condition number $\kappa$ are analysed using practical matrices from Computational Fluid Dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in $\kappa$. We introduce preamplified quantum multiplication to reduce subnormalisation, which is of independent interest. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the Sparse Approximate Inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024x1024.

24 pages, 17 figures. Accepted manuscript, see front page for copyright and licence

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Preconditioned quantum linear system algorithm
• Efficient phase-factor evaluation in quantum signal processing
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Block-encoding structured matrices for data input in quantum computing
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Quantum Circulant Preconditioner for Linear System of Equations
• Quantum Computing and Preconditioners for Hydrological Linear Systems