Quantum linear system algorithm for dense matrices

"”A quantum linear system algorithm for dense matrice"

Published by Leonard Wossnig, Zhikuan Zhao, Anupam Prakash (ETH Zürich, Univ. of Oxford, Singapore Univ. of Tech. and Design, Nat. Univ. of Singapore), 20th April 2017

Machine learning
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.