HHL algorithm

The Harrow–Hassidim–Lloyd (HHL) algorithm is a <a href="/facts/Quantum_algorithm/ceJaJ6Eq">quantum algorithm</a> for numerically solving a <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a>, designed by <a href="/facts/Aram_Harrow/rwTrKcwV">Aram Harrow</a>, Avinatan Hassidim, and <a href="/facts/Seth_Lloyd/NpKGzGaS">Seth Lloyd</a>. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with <a href="/facts/Shor%2527s_Algorithm/9JwEtznC">Shor's factoring algorithm</a> and <a href="/facts/Grover%2527s_algorithm/SJuxBPpA">Grover's search algorithm</a>. Provided the linear system is <a href="/facts/Sparse_matrix/FFtN0XjR">sparse</a> and has a low <a href="/facts/Condition_number/9Tjtk6wh">condition number</a> 
 
 
 
 κ
 
 
 {\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 
 
 
 
 O
 (
 log
 ⁡
 (
 N
 )
 
 κ
 
 2
 
 
 )
 
 
 {\displaystyle O(\log(N)\kappa ^{2})}
 
, where 
 
 
 
 N
 
 
 {\displaystyle N}
 
 is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in 
 
 
 
 O
 (
 N
 κ
 )
 
 
 {\displaystyle O(N\kappa )}
 
 (or 
 
 
 
 O
 (
 N
 
 
 κ
 
 
 )
 
 
 {\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. The demonstrations consisted of simple linear equations on specially designed quantum devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018.
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.

HHL algorithm open-in-new

HHL algorithm