= Solution
For a positive Hermitian matrix,
$$
\boxed{\kappa(A)=\frac{\lambda_{\max}}{\lambda_{\min}}}.
$$
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}\leq1$, this contributes a dependence at least linear in $\kappa$.
The controlled rotation must use a scale $C\leq\lambda_{\min}$. In the worst input direction its success probability is of order
$$
\frac{C^2}{\lambda_{\max}^2}=O(\kappa^{-2}),
$$
so obtaining constant success by <amplitude amplification> costs another $O(\kappa)$ factor. Thus a runtime polynomial in $\log N$ requires
$$
\boxed{\kappa=O(\operatorname{poly}(\log N))}.
$$
An exponentially ill-conditioned matrix would require exponentially fine phase resolution or exponentially many amplification steps.
Back to article page
