= Solution
For the <HHL algorithm> to have runtime polynomial in $\log N$, the Hermitian matrix $A$ must be invertible, have a <condition number> $\kappa$ bounded by $\operatorname{poly}(\log N)$, and be a <sparse matrix> with its nonzero entries efficiently accessible by an oracle. The normalized state $|b\rangle$ must also be preparable in $\operatorname{poly}(\log N)$ time. With precision costs suppressed, these assumptions let HHL prepare, with high probability,
$$
\boxed{|\xi\rangle=\frac{A^{-1}|b\rangle}
{\|A^{-1}|b\rangle\|}}.
$$
Back to article page
