<p>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 <span class="math-container">$n=\log_2 N$</span>, which is best defined to be the number of qubits in the answer register <span class="math-container">$|x\rangle$</span>, 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.</p>
<p>You mentioned the condition number <span class="math-container">$\kappa$</span> of the <span class="math-container">$N\times N$</span> matrix <span class="math-container">$A$</span>; there's also the sparsity <span class="math-container">$s$</span> of <span class="math-container">$A$</span> and an error <span class="math-container">$\epsilon$</span> associated with the Hamiltonian simulation of <span class="math-container">$e^{-iAt}$</span>.  <a href="https://en.wikipedia.org/wiki/Hamiltonian_simulation" rel="nofollow noreferrer">Wikipedia</a> mentions a number of Hamiltonian simulation algorithms, many of which were optimized <em>after</em> HHL's introduction.</p>
<p>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 <a href="https://arxiv.org/abs/1010.4458" rel="nofollow noreferrer">Ambainis</a> that the runtime of his algorithm is:</p>
<p><span class="math-container">$$\mathcal{O}(\log(N)s^2 \kappa/\varepsilon)$$</span></p>
<p>(he doesn't mention the sparsity factor <span class="math-container">$s$</span> directly but it's implied).  It can be seen that, for Ambainis's algorithm, letting <span class="math-container">$\kappa$</span> vary quadratically would lead to a quadratic increase in the runtime.</p>

CC BY-SA 4.0
2023-06-24T14:22:06.700Z
2023-06-24T14:22:06.700Z
Mark S
<p>We know that there are four caveats for the exponential speedup proven for the <a href="https://qiskit.org/textbook/ch-applications/hhl_tutorial.html" rel="nofollow noreferrer">HHL algorithm</a>. Could anyone answer how that exponential speedup evolves as we relax the caveats?</p>
<p>For example, the condition number of the matrix, <span class="math-container">$\kappa$</span>, needs to scale linearly. Is there a way to back calculate the scaling of <span class="math-container">$\kappa$</span> if the advantage of HHL goes down to quartic or quadratic? Or does it just drops off a cliff from exponential to nothing?</p>

<quantum-computing><linear-algebra><quantum-information>
Impact HHL caveat relaxation on quantum advantage
Omar Shehab
# Impact HHL caveat relaxation on quantum advantage

(Asked by: username_0 on 2023-03-06)

We know that there are four caveats for the exponential speedup proven for the [HHL algorithm](https://qiskit.org/textbook/ch-applications/hhl_tutorial.html). 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?

**Tags:** quantum-computing, linear-algebra, quantum-information

---

## 1 answers

### Answer by username_1 on 2023-06-24. Score: 1 | Accepted answer

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](https://en.wikipedia.org/wiki/Hamiltonian_simulation) 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](https://arxiv.org/abs/1010.4458) 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.


---

