Quantum linear system algorithm for dense matrices
Solving linear systems of equations is a frequently encountered problem in machine
learning and optimization. Given a matrix A and a vector b the task is to find the vector x such
that A x= b. We describe a quantum algorithm that achieves a sparsity-independent runtime
scaling of O (κ 2 n polylog (n)/ε) for an n× n dimensional A with bounded spectral norm,
where κ denotes the condition number of A, and ε is the desired precision parameter. This
amounts to a polynomial improvement over known quantum linear system algorithms when …
learning and optimization. Given a matrix A and a vector b the task is to find the vector x such
that A x= b. We describe a quantum algorithm that achieves a sparsity-independent runtime
scaling of O (κ 2 n polylog (n)/ε) for an n× n dimensional A with bounded spectral norm,
where κ denotes the condition number of A, and ε is the desired precision parameter. This
amounts to a polynomial improvement over known quantum linear system algorithms when …
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix and a vector the task is to find the vector such that . We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of for an dimensional with bounded spectral norm, where denotes the condition number of , and is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of and the vector of Euclidean norms of the rows of .
American Physical Society