Paper (2009) – Quantum algorithm for solving linear systems of equations

Home Quantum Computing 04 Algorithms Paper (2009) – Quantum algorithm for solving linear systems of equations

Viewing 1 post (of 1 total)
  • Author
    Posts
  • #6790
    davelowe
    Registered
    • University or Employer: Loughborough
    • Country: UK
    • Occupation: Mature student
    @davelowe
    Up
    1
    Down

    Abstract: Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn’t need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x’Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x’Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.

Viewing 1 post (of 1 total)
  • You must be logged in to reply to this topic.