The HHL linear systems algorithm and its caveats

Short answer: The HHL algorithm, from Harrow, Hassidim and Lloyd, prepares a quantum state proportional to the solution of a linear system, and can do so exponentially faster than classical methods when the matrix is well conditioned and other conditions hold. Those conditions are the catch. The input must be available as a quantum state, the matrix must be accessible, and the output is a quantum state from which only partial information can be read. Papers from 2008 and 2023 and a caveats study set out these limits. This is algorithm theory, not a demonstrated speedup on a real task.

What the algorithm does

A 2023 arXiv paper describes HHL as a milestone in quantum algorithms for linear algebra. Given a well-conditioned invertible matrix A and a vector u, it prepares, in time polynomial in the logarithm of the matrix size n, a quantum state proportional to a vector close to the solution of Ax = u. That state can then be used to compute some partial information about the solution. The paper says HHL has been very influential and led to several quantum machine learning algorithms.

The original 2008 paper explains where the speedup comes from. The algorithm works only with registers of order log N qubits and never writes down all of A, b or x. When the Hamiltonian simulation and a non-unitary step cost only polylogarithmic overhead, the algorithm takes exponentially less time than a classical computer would need even to write down the output. The authors compare this to classical Monte Carlo algorithms, which achieve large speedups by working with samples rather than writing out a whole distribution, and they prove that any classical algorithm needs in general exponentially more time to perform the same matrix inversion task.

The conditioning condition

The 2008 paper names the condition number, kappa, and the error, epsilon, as important factors. The exponential speedup is achieved when both kappa and 1 over epsilon are polylogarithmic in N. It compares with the classical conjugate gradient method, which for a positive definite matrix uses about the square root of kappa times log(1/epsilon) matrix-vector multiplications, each taking time proportional to N times the sparsity s. The authors pose the open question of whether classical methods can improve when only a summary statistic of the solution is required.

Input assumptions

The 2023 paper stresses that an important assumption in HHL and most extensions is that the input vector is accessible as a quantum state: the quantum computer holds a few copies of the normalised vector on order log n qubits. For HHL to be useful, preparing that state efficiently is therefore crucial. One proposal stores the vector in quantum random access memory (QRAM), in which case one copy of the state can be created in polylogarithmic time under the definition used. The paper adds that similar assumptions are needed on how the algorithm accesses the matrix, and that because of all these assumptions it is difficult to directly compare the performance of such quantum algorithms with classical methods.

Further caveats

A separate study of HHL says it is one of the most important subroutines in many quantum machine learning algorithms, and presents several caveats that had been ignored in the past. The authors say these affect the efficiency, accuracy and practicability of HHL and related quantum machine learning algorithms, and that they affect HHL much deeper than the caveats already noticed. They argue that more attention to these caveats is needed to obtain more practical algorithms with fewer assumptions.

What this does not tell you

These papers do not report running HHL on a useful problem. The speedup statements depend on conditioning, input access and the kind of output wanted, and the caveats study argues some practical costs were overlooked.

FAQ

What does HHL compute?

A quantum state proportional to the solution of a linear system, not the full solution vector.

Where does the speedup come from?

Working with log-size registers and never writing down the matrix or vectors, per the 2008 paper.

What conditions does it need?

A well-conditioned matrix, efficient input state preparation and access to the matrix.

Can you read out the whole answer?

No. The state gives only partial information about the solution.

Is the speedup proven in practice?

The papers describe the algorithm and its caveats, and do not report a practical demonstration.