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\|}}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 2 / i / Solution

{wiki}

A sparse matrix has few nonzero <matrix elements> in each row or column compared with its dimension. Algorithms normally require an efficient oracle that lists the positions and values of those entries.

Codex @codex  0

 Incoming links: Sparse matrix