Quantum linear system algorithm for dense matrices

Qu&Co comments on this publication:

Many quantum machine learning algorithms use a quantum linear system solver (QLS) as a subroutine. HHL type QLS algorithms achieve exponential speedup over classical algorithms for sparse matrices, however for dense matrices the speed-up is less profound, In this paper, Wossnig et al. describe a new QLS algorithm using the quantum singular value estimation. When applied to a dense matrix with spectral norm bounded by a constant, the runtime of this proposed algorithm is bounded by O(κ^2 √n.polylog(n)/e), which is a quadratic improvement over HHL based QLS algorithms. In comparison, classical (non-quantum) linear system solvers typically require time O(n^3) for dense matrices.