HHL linear-systems reference

HHL estimates an observable of the solution $|x\rangle\propto A^{-1}|b\rangle$ to a linear system $Ax=b$ for Hermitian, $s$-sparse $A$ (or made Hermitian via a standard block embedding). The circuit encodes $A$'s eigenvalues into a phase register via quantum phase estimation on $e^{iAt}$, applies a controlled rotation proportional to $\lambda^{-1}$ on an ancilla, and uncomputes the phase register, leaving $|x\rangle$ entangled with an ancilla flag. Under the coherent access model, circuit cost scales roughly as $O(s\,\kappa^2\log(1/\epsilon))$ where $\kappa=|\lambda_{\max}|/|\lambda_{\min}|$ is $A$'s condition number and $\epsilon$ the target precision — versus roughly $O(s\kappa)$ for classical conjugate gradient, so the advantage narrows as $\kappa$ grows. Crucially, $|x\rangle$ is a quantum state: reading out every component costs $O(N)$ measurements and erases any speedup, so — matching this record's caveat — HHL is only useful when a single scalar observable of $x$, not the full vector, is the actual goal.