HHL algorithm

The Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of 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, Grover's search algorithm, and the quantum Fourier transform. Provided 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, instead of the values of the solution vector itself, then 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]

Due to the prevalence of linear systems in virtually all areas of science and engineering, the quantum algorithm for linear systems of equations has the potential for widespread applicability.^[7]