HHL algorithm

The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for obtaining certain 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 of linear equations.^[1]

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 linear system is sparse^[2] and has a low condition number ${\displaystyle \kappa }$, and that the user is interested in the result of a scalar measurement on the solution vector and not the entire vector itself, the algorithm has a runtime of ${\displaystyle O(\log(N)\kappa ^{2})}$, where ${\displaystyle N}$ is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in ${\displaystyle O(N\kappa )}$ (or ${\displaystyle O(N{\sqrt {\kappa }})}$ for positive semidefinite matrices).

An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by three independent publications.^[3][4][5] The demonstrations consisted of simple linear equations on specially designed quantum devices.^[3][4][5] The first demonstration of a general-purpose version of the algorithm appeared in 2018.^[6]