Solving quantum linear system problem with near-optimal complexity

10/31/2019

∙

by   Lin Lin, et al.

∙

0

∙

share

We present a simple algorithm to solve the quantum linear system problem (QLSP), i.e. preparing a quantum state | x〉 that is proportional to A^-1| b〉. The algorithm decomposes a general QLSP into an initial state preparation problem solved by the time-optimal adiabatic quantum computation, and an eigenstate filtering problem solved by quantum signal processing. The algorithm does not rely on phase estimation, variable-time amplitude amplification, or in fact any amplitude amplification procedure. The probability of success is Ω(1). The query complexity of the algorithm is O(κ(log(κ)/loglog(κ)+log(1/ϵ))), which is near-optimal with respect to the condition number κ up to a logarithmic factor, and is optimal with respect to the target accuracy ϵ.