Efficient quantum algorithms for solving quantum linear system problems
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We transform the problem of solving linear system of equations A x = b to a problem of finding the right singular vector with singular value zero of an augmented matrix C , and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of O ( sκ log (1 /ǫ )) for a s -sparse matrix C , where κ is the condition number of the matrix A , and ǫ is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as O [ sκ + log (1 /ǫ ) / log log (1 /ǫ )]. Both algorithms meet the optimal query complexity in κ , and are simpler than previous algorithms.