= Solution
The usual sufficient input promises for the <HHL algorithm> are efficient <quantum state preparation> of the nonzero vector $b$, efficient access to a <sparse matrix> $A$ with at most $\operatorname{poly}(n)$ nonzero entries per row, and a <condition number> $\kappa=\lambda_{\max}/\lambda_{\min}=\operatorname{poly}(n)$ after an efficiently known normalization. Both the positions and values of the nonzero <matrix elements> must be computable coherently in <polynomial time>. More generally, efficient <Hamiltonian simulation> can replace the sparsity promise. We assume $A$ is invertible; if zero <eigenvalues> occur, one must instead restrict $b$ to their <orthogonal complement> and specify the desired inverse on that support.
With $a=\lambda_{\max}$ and a known bound $\kappa$, choose $c=a/\kappa\leq\lambda_{\min}$. The <HHL controlled reciprocal rotation> then succeeds with probability
$$
p_{\rm succ}=c^2\|A^{-1}|b\rangle\|^2\geq\frac{c^2}{a^2}=\boxed{\kappa^{-2}}.
$$
This is the required inverse-polynomial lower bound. In the usual approximate algorithm, inverse-polynomial requested error also gives polynomial runtime under these input promises. The original https://arxiv.org/abs/0811.3171[HHL paper] states the dependence on sparsity, conditioning, and accuracy.
There is a qualification for a literally exact version. Representability of the <eigenvalues> in $n$ bits does not itself make exact <quantum phase estimation> efficient: using $e^{2\pi iA}$ requires controlled powers corresponding to evolution times as large as $2\pi2^{n-1}$. Under the paper's idealization we may describe their exact action, but polynomial runtime for that exact circuit additionally requires efficient implementations of those controlled powers, or equivalent efficient exact spectral access. Assuming an operation executes exactly does not bound its cost. This distinction is recorded in <cost of exact phase estimation on a dyadic spectrum>.
Back to article page
