Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 324 / 3 / b / Solution

For a positive Hermitian matrix,The HHL algorithm phase-estimates $A$, performs a controlled rotation with amplitude proportional to $1/{\lambda }_i$, uncomputes the estimate, and postselects the rotation ancilla. Resolving the smallest eigenvalue requires phase-estimation precision $O({\lambda }_{\min })$ and evolution time $\Omega (1/{\lambda }_{\min })$. Since ${\lambda }_{\max }\le 1$, this contributes a dependence at least linear in $\kappa$.

The controlled rotation must use a scale $C\le {\lambda }_{\min }$. In the worst input direction its success probability is of orderso obtaining constant success by amplitude amplification costs another $O(\kappa )$ factor. Thus a runtime polynomial in $\log N$ requiresAn exponentially ill-conditioned matrix would require exponentially fine phase resolution or exponentially many amplification steps.