HHL algorithm (Harrow–Hassidim–Lloyd algorithm)

The HHL algorithm prepares a quantum state proportional to $A^{-1}b$ for a sparse, efficiently accessible, well-conditioned linear system $Ax=b$, provided that $|b⟩$ can be prepared efficiently. Its runtime depends polynomially on the sparsity, condition number, inverse precision, and $\log N$.

On a positive eigenvalue label $\lambda$ and a clean quantum ancilla, the HHL algorithm applies a quantum variable rotation with angle ${\theta }_{\lambda }=\arcsin (c/\lambda )$, where $0<c\le {\lambda }_{\min }$:Uncomputation of the eigenvalue register followed by conditioning on flag one multiplies each input eigenvector amplitude by $c/\lambda$. If $|b⟩$ is normalized, the success probability is $c^2\Vert A^{-1}|b⟩{\Vert }^2$. Choosing $c={\lambda }_{\max }/\kappa$ from a valid condition number bound gives success probability at least $1/{\kappa }^2$.

If the eigenvalues of $A$ are $\ell /2^n$ with $0\le \ell <2^n$, exact quantum phase estimation on $U=e^{2\pi iA}$ uses $n$ controlled powers $U^{2^j}$. Their Hamiltonian simulation times reach $2\pi 2^{n-1}$. Counting each supplied controlled power as one oracle query is valid in that oracle model, but does not prove a polynomial time implementation from generic sparse-matrix access. In the ordinary HHL algorithm, one instead chooses finite precision appropriate to the output error and the condition number, or exploits additional structure giving efficient access to the needed powers.