Quantum linear system algorithm for dense matrices

20 April 2017

Additional Info

  • Paper Title:

    ”A quantum linear system algorithm for dense matrice"

  • Paper Authors:

    Leonard Wossnig, Zhikuan Zhao, Anupam Prakash (ETH Zürich, Univ. of Oxford, Singapore Univ. of Tech. and Design, Nat. Univ. of Singapore)

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.

What's Interesting?

How can we help you?

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Copyright © Qu & Co BV
close