2017/04/30 by Leonard Wossnig, Zhikuan Zhao, Anupam Prakash · 3 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physrevlett.120.050502
published as Phys. Rev. Lett. 120, 050502 (2018)
arxiv created 2017/05/03 · arxiv updated 2018/02/07
Solving linear systems of equations is a frequently encountered problem in machine learning and optimisation. Given a matrix A and a vector \mathbf b the task is to find the vector \mathbf x such that A \mathbf x = \mathbf b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of O(κ2 ‖A‖F polylog(n)/ε), where n× n is the dimensionality of A with Frobenius norm ‖A‖F, κ denotes the condition number of A, and ε is the desired precision parameter. When applied to a dense matrix with spectral norm bounded by a constant, the runtime of the proposed algorithm is bounded by O(κ2√(n) polylog(n)/ε), which is a quadratic improvement over known quantum linear system algorithms. 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 and row Frobenius norms of A.