Lesson plan
HHL algorithm
The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for obtaining certain limited information about the solution to a system of linear equations, introduced by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. Specifically, the algorithm estimates quadratic functions of the solution vector to a given system. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm and Grover's search algorithm. Assuming the system is sparse, has a low condition number \kappa , and that the user is only interested in certain information about solution vector and not the entire vector itself, the algorithm has a runtime of O(\log(N)\kappa^2) , where N is the number of variables. This offers an exponential speedup over the fastest classical algorithm, which runs in O(N\kappa) (or O(N\sqrt{\kappa}) for positive semidefinite matrices). An implementation of the HHL algorithm was first demonstrated in 2013 by three independent publications, consisting of simple systems on specially designed devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018.
Article summary
The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for obtaining certain limited information about the solution to a system of linear equations, introduced by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. Specifically, the algorithm estimates quadratic functions of the solution vector to a given system. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm and Grover's search algorithm. Assuming the system is sparse, has a low condition number \kappa , and that the user is only interested in certain information about solution vector and not the entire vector itself, the algorithm has a runtime of O(\log(N)\kappa^2) , where N is the number of variables. This offers an exponential speedup over the fastest classical algorithm, which runs in O(N\kappa) (or O(N\sqrt{\kappa}) for positive semidefinite matrices). An implementation of the HHL algorithm was first demonstrated in 2013 by three independent publications, consisting of simple systems on specially designed devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.