We know that there are four caveats for the exponential speedup proven for the HHL algorithm. Could anyone answer how that exponential speedup evolves as we relax the caveats?
For example, the condition number of the matrix, $\kappa$, needs to scale linearly. Is there a way to back calculate the scaling of $\kappa$ if the advantage of HHL goes down to quartic or quadratic? Or does it just drops off a cliff from exponential to nothing?
Your link 404's, but certainly HHL, like most quantum (and classical!) algorithms include a number of caveats for their applicability. The runtime of HHL depends on a number of factors in addition to or based on $n=\log_2 N$, which is best defined to be the number of qubits in the answer register $|x\rangle$, but, many of these factors are independent of each other, and if we increase one we might be able to get by with decreasing another.
You mentioned the condition number $\kappa$ of the $N\times N$ matrix $A$; there's also the sparsity $s$ of $A$ and an error $\epsilon$ associated with the Hamiltonian simulation of $e^{-iAt}$. Wikipedia mentions a number of Hamiltonian simulation algorithms, many of which were optimized after HHL's introduction.
It's rare (impossible?) to have one these factors change from one polynomial (linear) to another polynomial (quadratric) and then have the overall runtime fall off the cliff to be exponential. For example have from Ambainis that the runtime of his algorithm is:
$$\mathcal{O}(\log(N)s^2 \kappa/\varepsilon)$$
(he doesn't mention the sparsity factor $s$ directly but it's implied). It can be seen that, for Ambainis's algorithm, letting $\kappa$ vary quadratically would lead to a quadratic increase in the runtime.
