Quantum Algorithms Database
HHL Algorithm
Solves systems of linear equations exponentially faster than classical methods, under specific conditions.
Year
2008 (arXiv); 2009 (Physical Review Letters)
Inventor(s)
Aram Harrow, Avinatan Hassidim, and Seth Lloyd
Speedup Type
Exponential Speedup
Difficulty
★★★★★
Overview
The HHL algorithm solves a linear system of equations. Given a matrix A and a vector b, it prepares a quantum state whose amplitudes are proportional to the solution x of A x = b. For a sparse, well-conditioned N by N matrix, it does this in time that scales as a polynomial in the logarithm of N, compared with a time at least linear in N for classical methods.
The headline result is an exponential speedup, but it comes with significant fine print. You do not get the full solution vector, only a quantum state that encodes it, from which you can estimate a quantity such as an inner product. The algorithm also requires fast access to the input vector and a matrix that has a particular structure. HHL is still among the most influential algorithms in quantum computing because it introduced the idea of quantum linear algebra.
The problem it solves
Solving a system of linear equations (Ax = b) — a problem underlying enormous amounts of scientific computing and machine learning.
History and background
Aram Harrow, Avinatan Hassidim, and Seth Lloyd posted the paper in 2008, and it appeared in Physical Review Letters in 2009. It sparked a wave of work on quantum machine learning, because linear systems and matrix operations sit at the core of regression, support vector machines, and principal component analysis.
The first experimental demonstrations came in 2013 on tiny two-by-two systems, using photonic and NMR devices. In 2015 Scott Aaronson wrote an influential essay, Read the Fine Print, that described the conditions under which the speedup holds. In 2018, Ewin Tang showed that a closely related quantum machine learning algorithm for recommendation systems could be matched by a classical algorithm with similar sampling access, which led to a wave of dequantization results. Improvements by Childs, Kothari, and Somma in 2017, and by Gilyén and coauthors in 2019 using quantum singular value transformation, reduced the dependence on precision and condition number.
How it works
Encodes the linear system into a quantum state, uses quantum phase estimation to find eigenvalues, and inverts them to construct the solution — all without ever writing out the full solution vector classically.
The key idea is to diagonalize the matrix without ever writing it down. Any invertible Hermitian matrix A has eigenvectors and eigenvalues, and A inverse acts on each eigenvector by dividing by its eigenvalue. If you could write the input vector b in the eigenbasis of A, and divide each component by the corresponding eigenvalue, you would have the solution.
HHL does this with quantum phase estimation. It applies the evolution e to the i A t, so that the eigenvalues appear as phases, and uses phase estimation to write each eigenvalue into an ancilla register in superposition. It then performs a controlled rotation that multiplies each eigencomponent by a factor proportional to 1 over its eigenvalue, undoes the phase estimation to uncompute the eigenvalue register, and finally measures an ancilla qubit. If the result is 1, the main register holds the solution state.
This is why the matrix must be sparse and well conditioned. Sparsity lets e to the i A t be implemented efficiently, and a small condition number kappa, the ratio of the largest to the smallest eigenvalue, keeps the controlled rotation from amplifying noise and keeps the success probability reasonable.
Step by step
- Prepare the quantum state b, the amplitudes of which are the entries of the vector, in an input register. This requires efficient state preparation, for example from a quantum memory or a structured circuit.
- Add a clock register of ancilla qubits and apply quantum phase estimation with the unitary e to the i A t, entangling the eigenvalues of A with the clock register.
- Add a single ancilla qubit and apply a controlled rotation, conditioned on the clock register, that sets the ancilla amplitude proportional to a constant divided by the eigenvalue.
- Apply the inverse of the phase estimation circuit to uncompute the clock register.
- Measure the ancilla qubit. If the result is 1, the input register holds the normalized solution state. If the result is 0, repeat; amplitude amplification can reduce the number of repetitions.
- Extract the information you want, such as an expectation value of an observable on the solution state, by repeating the whole procedure many times and measuring.
A worked example
Take the two-by-two system in which A has 1.5 on both diagonal entries and 0.5 on both off-diagonal entries, and b is the vector (1, 0). The eigenvalues of A are 1 and 2, with eigenvectors (1, -1) over the square root of 2 and (1, 1) over the square root of 2. The vector b is an equal-weight combination of those two eigenvectors. HHL multiplies the first component by 1 over 1 and the second by 1 over 2 and then normalizes. The exact solution is x = (3/4, -1/4), so the output state is proportional to (3, -1), which is what the quantum circuit prepares.
Early experiments verified this kind of two-by-two example. They confirmed that the structure works, but they could not demonstrate any speedup, since solving a two-by-two system classically is trivial.
Complexity and resources
| Item | Detail |
|---|---|
| Quantum runtime | O(log N times s squared times kappa squared divided by epsilon), where s is sparsity, kappa the condition number, and epsilon the precision |
| Best classical (exact, sparse) | O(N s kappa log of 1 over epsilon) using conjugate gradient |
| Improved quantum versions | Polylogarithmic in 1 over epsilon and linear in kappa with later techniques |
| Output | A quantum state proportional to the solution, not the explicit vector |
| Qubits | About log N plus ancillas for the clock and rotation registers |
What hardware it needs
- Fault-tolerant hardware with deep circuits, because phase estimation and Hamiltonian simulation of A are expensive.
- A way to prepare the vector b efficiently and, for classical data, a quantum memory that may not exist at scale.
- Sparse access to the matrix, so that e to the i A t can be simulated efficiently.
Applications
- Solving differential equations by discretizing them into large sparse linear systems, as in fluid dynamics and electromagnetic scattering.
- Quantum machine learning subroutines that rely on matrix inversion, such as regression and support vector machines.
- Estimating properties of the solution, such as the electromagnetic scattering cross section, rather than reading out the whole vector.
- Serving as a theoretical anchor: matrix inversion with these constraints is BQP-complete.
Limitations and caveats
- The input vector must be loaded into a quantum state, which can cost as much as the classical solution.
- The output is a quantum state, so reading all N entries would take about N repetitions and wipe out the speedup.
- The matrix must be sparse and have a small condition number.
- For machine learning tasks, classical dequantized algorithms can match the speedup when low-rank assumptions hold.
Common misconceptions
- HHL does not give you the solution vector. It gives a quantum state from which you can sample or estimate expectation values.
- The exponential speedup does not apply to arbitrary linear systems. It requires sparsity, good conditioning, and efficient input and output.
- It has not been used to solve a practical large problem. Experiments so far are on tiny systems.
How it compares
- Classical conjugate gradient is polynomial in N, but it returns the full solution and has no input-output issues.
- Variational linear solvers such as VQLS aim to run on near-term devices, but they offer no proven speedup.
- Quantum singular value transformation generalizes HHL to many matrix functions with better scaling.
Real-world impact
Has significant caveats (requires the matrix to be 'sparse' and well-conditioned, and the output is a quantum state, not a classical answer), but is foundational to quantum machine learning research.
Why it matters
HHL shows that quantum computers can in principle perform linear algebra on exponentially large objects in logarithmic time, and it started the field of quantum machine learning. Many later algorithms are built from its ingredients: phase estimation, controlled rotations, and amplitude amplification.
It is equally valuable as a case study in how to read speedup claims. Aaronson's fine print, followed by dequantization, shows how input assumptions, output limits, and classical competition shape what a speedup really means.
Frequently asked questions
What does the HHL algorithm do?
It prepares a quantum state proportional to the solution of a linear system A x = b, for a sparse, well-conditioned matrix A.
Is HHL exponentially faster than classical solvers?
In its query model, yes, but only when state preparation, sparsity, conditioning, and the limited form of output are all favorable. In many practical settings the advantage disappears.
Can I use HHL to speed up machine learning?
Possibly for specific structured problems. For many learning tasks, dequantized classical algorithms can match the quantum speedup under comparable access assumptions.
What is the condition number?
The ratio of the largest to the smallest eigenvalue of the matrix. A large condition number makes the problem harder and increases the cost of HHL.
Has HHL been run on real hardware?
Yes, on tiny systems such as two-by-two matrices, using photonic, NMR, and superconducting devices. These were demonstrations of the structure, not of speedup.
Keep learning
- Related algorithm: Quantum Phase Estimation (QPE)
- Related algorithm: Quantum Singular Value Transformation (QSVT)
- Related algorithm: Variational Quantum Linear Solver (VQLS)
- Related algorithm: Quantum Principal Component Analysis
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.