The HHL Algorithm

Understand the HHL algorithm for solving linear systems exponentially faster.

The HHL Algorithm: Quantum Linear Systems

The HHL algorithm (Harrow, Hassidim, Lloyd: 2009) solves systems of linear equations Ax = b exponentially faster than classical algorithms: under specific conditions. It is one of the most studied quantum speedups with potential applications in machine learning and simulation.

The problem:

Given an N×N Hermitian matrix A and a vector b, find x such that:

Ax = b → x = A⁻¹b

Classically, Gaussian elimination runs in O(N³). The best iterative methods (conjugate gradient) run in O(N·s·√κ·log(1/ε)) for sparse systems, where s is the sparsity and κ is the condition number of A. HHL runs in O(κ² log(N) / ε) (up to sparsity factors): polylogarithmic in N. For sparse, well-conditioned systems that is exponentially faster in N than any classical solver, with the state-preparation and readout caveats below.

How HHL works:

HHL has four major subroutines:

1.State preparation: Encode b as a quantum state $∣ b ⟩ \propto \sum b_{i} ∣ i ⟩$
2.QPE on A: Use quantum phase estimation with $e^{i A t}$ as the unitary to find eigenvalues $λ_{k}$ of A
3.Ancilla rotation: Rotate an ancilla qubit by $C / λ_{k}$ (the reciprocal of each eigenvalue): this implements the $1/ λ$ scaling needed for inversion
4.Inverse QPE: Uncompute the eigenvalue register, leaving the solution state

The output is not x itself, but the quantum state $∣ x ⟩ \propto \sum (b_{k} / λ_{k}) ∣ v_{k} ⟩$ where $v_{k}$ are eigenvectors of A. You can then estimate properties of x (like ⟨x|M|x⟩ for some observable M) efficiently.

The fine print: when HHL actually helps

HHL's exponential speedup comes with strict requirements. First, the state preparation of |b⟩ must be efficient (classically-efficient amplitude encoding is generally hard). Second, you cannot read out all components of x efficiently: only properties of x that can be expressed as expectation values. Third, κ (condition number) must be small, or the speedup vanishes. These caveats mean HHL is practically useful only for specific problem structures, not as a general linear solver.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A guided reading lesson with interactive knowledge checks. Concepts are explained step by step with circuit diagrams and runnable examples, and you confirm understanding before moving on.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonShor's Algorithm Capstone Next lessonVariational Eigensolver Basics

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground