HHL and the fine print of quantum linear-systems speedups

Short answer: The HHL algorithm, from Harrow, Hassidim and Lloyd, is reported to offer an exponential speedup for the quantum linear-system problem, but only under conditions. Its authors say the greatest advantage occurs when the condition number and the inverse error are both polylogarithmic in the matrix size, and a 2025 paper says preparing the initial quantum state is a difficulty known as the encoding bottleneck. These are theoretical results and no deployment is claimed.

The promise

An essay by Scott Aaronson says the "killer apps" for a quantum computer, the problems promising huge speed advantages, have struck some people as inconveniently narrow. He lists accelerating the simulation of quantum physics and chemistry, breaking much of today's public-key cryptography with Shor's algorithm, and maybe a modest speedup for NP-hard optimization problems. He then says a new family of quantum algorithms has come along to challenge this narrow view, promising exponential speedups over classical algorithms.

The condition number

The HHL paper on arXiv says an important factor in the performance of its matrix inversion algorithm is the condition number of the matrix, the ratio between its largest and smallest eigenvalues. As the condition number grows, the matrix becomes closer to one that cannot be inverted, and the solutions become less stable. Such a matrix is called ill-conditioned.

The authors say their algorithms generally assume that the singular values of the matrix lie between 1 over kappa and 1, where kappa is the condition number. In that case the runtime scales as kappa squared times the logarithm of N divided by epsilon, where N is the matrix dimension and epsilon is the additive error in the output state. They conclude that the greatest advantage over classical algorithms occurs when both kappa and 1 over epsilon are polylogarithmic in N, in which case the algorithm achieves an exponential speedup. They add that they also discuss techniques for handling ill-conditioned matrices.

Inputs and the encoding bottleneck

The HHL paper says that as inputs it requires a procedure to produce the input state and a method of producing the non-zero elements of any row of the matrix. A 2025 arXiv paper says some caveats for the speedup could be hard to meet. One difficulty is the encoding bottleneck, the efficient preparation of the initial quantum state. It says that to prepare an arbitrary N-dimensional state exactly, existing state-preparation approaches generally require a runtime of order N, which will ruin the speedup of the HHL algorithm.

A proposed workaround

The 2025 paper reports that states can be prepared approximately with a runtime polylogarithmic in N by employing a slightly modified version of the HHL algorithm itself. It says applying this approach to prepare the initial state of the original HHL algorithm can preserve the exponential speedup advantage, and that it can also serve as a standalone solution for other applications demanding rapid state preparation. This is the authors' claim in a preprint. We have not verified the proof.

What this does not tell you

This article summarises one essay and the abstracts and introductions of two papers. It makes no claim that the speedup has been realised on hardware, and a speedup under stated assumptions is not a speedup for every linear-algebra task.

FAQ

What does HHL claim?

An exponential speedup for the quantum linear-system problem, under conditions stated by its authors.

When is the advantage greatest?

According to the HHL paper, when both the condition number and the inverse error are polylogarithmic in the matrix size.

What is the condition number?

The ratio between the matrix's largest and smallest eigenvalues, per the HHL paper. As it grows, the matrix becomes ill-conditioned and solutions become less stable.

What is the encoding bottleneck?

A 2025 paper says it is the efficient preparation of the initial quantum state, which with existing approaches takes time of order N for an arbitrary N-dimensional state and ruins the speedup.

Is there a proposed fix?

The 2025 paper proposes using a slightly modified HHL algorithm to prepare states approximately in polylogarithmic time. It is a research result, not a deployed method.