A quantum linear-system algorithm does not normally hand you every entry of x in Ax=b. It prepares a quantum state proportional to the solution, so the useful question must be something that can be extracted from that state without reading all N coordinates.
Linear systems sit beneath differential equations, optimisation, regression, network models and numerical simulation. The Harrow–Hassidim–Lloyd algorithm—HHL—is historically important because it showed that, under strong access and conditioning assumptions, a quantum computer can prepare a representation of a linear-system solution with complexity logarithmic in the matrix dimension while depending on sparsity, condition number, precision and state preparation. [1,2]
The algorithm is best learned as a spectral construction. Diagonalise A, estimate its eigenvalues, apply an inverse-dependent amplitude rotation, then uncompute the eigenvalue register. This guide derives that chain, explains why small eigenvalues are expensive, and makes the output limitation explicit.
Ax=b → spectral basis → encode 1/λ → solution state |x⟩ → extract a compact observable.
1. Classical linear systems first
Given an invertible N×N matrix A and vector b, the exact solution is x=A⁻¹b. Writing an inverse symbol does not solve the computational problem; practical algorithms exploit matrix structure, sparsity, conditioning and preconditioning.
Quantum algorithms do not abolish these issues. They change the representation of the input and output. A typical quantum linear-system algorithm assumes efficient access to A and a quantum state |b⟩ proportional to b, then seeks a quantum state |x⟩ proportional to A⁻¹|b⟩.
If the final task truly requires all N entries of x as classical numbers, reading them out generally costs at least order N data. The strongest quantum advantage belongs to problems where a compact property of x is enough.
2. Hermitian spectral decomposition
Start with Hermitian A. Let
A=Σ_j λ_j |u_j⟩⟨u_j|
with real nonzero eigenvalues λj. Expand
|b⟩=Σ_j β_j|u_j⟩.
Then formally
A^{-1}|b⟩=Σ_j (β_j/λ_j)|u_j⟩.
The linear-system problem has become a scalar transformation on each eigenvalue: λ→1/λ.
3. Worked two-dimensional example
Let A=diag(1,2) and |b⟩=(|0⟩+|1⟩)/√2. Then
A^{-1}|b⟩=(1/√2)|0⟩+(1/(2√2))|1⟩.
The squared norm is 1/2+1/8=5/8. After normalisation,
|x⟩=(2|0⟩+|1⟩)/√5.
Measuring in the computational basis gives probabilities 4/5 and 1/5. These probabilities describe the normalised direction of the solution, not the original scale of the classical vector x.
4. HHL uses phase estimation to label eigenvalues
Choose a unitary generated by A, such as U=eiAt under an appropriate scaling that prevents phase aliasing. If |uj⟩ is an eigenvector of A, then
U|u_j⟩=e^{iλ_jt}|u_j⟩.
Quantum phase estimation correlates an ancilla register with an approximation to λjt modulo 2π while preserving the eigenvector label. Applied to the superposition |b⟩, it produces a coherent superposition of eigenvalue estimates correlated with the βj|uj⟩ components.
This step reuses the mathematics of Guide 10 on phase estimation.
5. The reciprocal enters through a controlled rotation
Once the eigenvalue estimate is available in a register, attach another ancilla qubit and rotate it by an angle chosen so that its |1⟩ amplitude is proportional to C/λj, where C is small enough to keep |C/λj|≤1 over the promised spectrum.
Schematically,
|λ_j⟩|0⟩ → |λ_j⟩(√(1-C²/λ_j²)|0⟩+(C/λ_j)|1⟩).
The reciprocal is now stored in amplitude. This is the non-unitary mathematical operation A⁻¹ represented indirectly inside a larger unitary computation.
6. Uncompute the eigenvalue register
Reverse the phase-estimation circuit. Ideally, the eigenvalue register returns to its initial state and disentangles, while the reciprocal weighting remains in the rotation ancilla.
Conditional on measuring the ancilla in |1⟩, the system register is proportional to
Σ_j β_j(C/λ_j)|u_j⟩ ∝ A^{-1}|b⟩.
After normalisation, this is the desired solution state |x⟩.
7. Condition number measures spectral difficulty
For an invertible matrix, the 2-norm condition number is κ=σmax/σmin. For a Hermitian matrix with eigenvalue magnitudes scaled so that the largest is one, the smallest relevant magnitude is at least 1/κ.
Small eigenvalues are hard because inversion makes them large. An eigencomponent at λ=0.01 is amplified one hundred times relative to a unit eigenvalue before normalisation.
This creates both numerical sensitivity and quantum resource costs. Greater phase precision is needed to distinguish small eigenvalues accurately, and the reciprocal-controlled rotation has a lower success amplitude when C must be chosen on the scale of λmin.
8. Worked conditioning comparison
Compare A₁=diag(1,1/2) with A₂=diag(1,1/100). Their condition numbers are 2 and 100.
For the equal-superposition right-hand side, the first inverse weighting is proportional to (1,2); the second is proportional to (1,100). A small uncertainty in the tiny eigenvalue of A₂ can strongly change the final direction.
Condition number is therefore not merely a runtime parameter. It tells us how sensitive the linear system is to perturbations and how extreme the spectral reweighting must become.
9. Postselection probability and amplitude amplification
In the basic HHL construction, the probability of observing the rotation ancilla in |1⟩ depends on the weighted sum of C²/λj² across the input spectrum. Choosing C no larger than the smallest eigenvalue magnitude ensures valid rotations but can make success probability small.
Amplitude amplification can improve the cost of obtaining the successful branch. Modern quantum linear-system algorithms also use more advanced spectral-transformation methods to improve dependence on κ and precision.
HHL should therefore be learned as the canonical spectral blueprint, not automatically quoted as the best currently known algorithm for every access model.
10. The input state is part of the problem
HHL assumes efficient preparation of |b⟩. If b is an arbitrary classical vector with N unrelated entries, loading it into amplitudes can itself cost order N operations or require a specialised data-access model.
Consequently, “polylogarithmic in N” runtime claims must state how A and b are accessed. Efficient sparse-matrix or block-encoding oracles and efficient state preparation are substantive assumptions.
If data loading dominates, the linear-system subroutine may not deliver an end-to-end advantage.
11. What does the solution state let us compute?
Suppose |x⟩ is available. We can estimate an expectation ⟨x|M|x⟩ for an efficiently measurable observable M. This may represent a global property of the solution direction.
We can also estimate overlap with another efficiently prepared state, sample in a convenient basis or feed |x⟩ into another coherent quantum subroutine.
But if the requested answer is “print x₁,x₂,…,xN to ten decimal places,” tomography or repeated coordinate sampling removes the exponential-looking output advantage.
Quantum linear-system speedup belongs to compact downstream questions, not to free extraction of an exponentially long classical vector.
12. The scale of x is lost unless separately reconstructed
The state |x⟩ represents x/||x||. Multiplying the classical solution by any positive scalar gives the same quantum state after normalisation.
If the norm ||x|| is required, it must be estimated separately through the success amplitude, additional routines or problem-specific information.
This matters in applications. Direction-only information may be sufficient for an expectation ratio but insufficient for a physical quantity whose magnitude carries meaning.
13. Non-Hermitian systems
HHL is often introduced for Hermitian A because phase estimation naturally accesses real eigenvalues. A general matrix can be embedded into a larger Hermitian matrix, for example
H=[[0,A],[A†,0]].
This Hermitian dilation has singular values of A encoded in its spectrum. Solving the enlarged system can recover information about the original problem, with additional bookkeeping.
Modern block-encoding and QSVT frameworks handle general singular-value transformations more directly, which is one reason Guide 18 precedes this article.
14. Preconditioning is still important
Classical numerical linear algebra improves difficult systems by preconditioning: transform Ax=b into an equivalent or related system with more favourable conditioning.
A quantum preconditioner must be useful in the quantum access model too. It should reduce κ without becoming more expensive to implement than the original problem.
There is no benefit in reducing the iteration complexity through a preconditioner whose coherent implementation requires an intractable amount of work.
15. Precision enters through several doors
Phase estimation has finite precision. Hamiltonian simulation or block encoding has finite error. The reciprocal rotation approximates a nonlinear function. State preparation and measurement can be imperfect.
These are different error sources. A final solution-state error bound must track how spectral estimation error is amplified by 1/λ near the smallest eigenvalues.
Higher numerical precision is especially expensive for ill-conditioned systems because the inverse function changes rapidly near zero.
16. Verify on a solvable instance
For A=diag(1,2) and b=(1,1), the unnormalised solution is x=(1,1/2). The solution-state probabilities are 4/5 and 1/5.
A useful test implementation should reproduce those probabilities, then vary the second eigenvalue from 2 to 4 and confirm that the second component shrinks from 1/2 to 1/4 before normalisation.
Next change b. If b=(0,1), the exact solution direction remains |1⟩ regardless of the scaling 1/λ₂. This is a good reminder that condition number alone does not determine the actual difficulty of one specific right-hand side; overlap with difficult spectral components matters too.
17. Residual checks
Classically, a candidate x can be checked using residual r=b−Ax. A small residual is meaningful when interpreted relative to ||A||, ||x|| and ||b|| and to the conditioning of the problem.
For a quantum solution state, directly reading every residual coordinate is usually undesirable. Instead, one can design overlap or norm-estimation tests when A and b are coherently accessible.
Verification is part of the resource cost. A claimed quantum speedup should not assume that correctness can be certified by an exponentially expensive classical reconstruction of x.
18. HHL and QSVT are two views of spectral inversion
HHL explicitly estimates eigenvalues and performs a reciprocal-controlled rotation. QSVT can approximate inverse-like functions directly as bounded polynomials on the singular spectrum of a block-encoded matrix.
The conceptual target is the same: amplify spectral components by approximately 1/λ while avoiding or controlling the singular region around zero.
Modern quantum linear-system methods often improve on the original HHL dependence on precision and condition number by using these more advanced primitives. The historical HHL circuit remains valuable because every step exposes the Mathematics visibly.
19. Common misconception: HHL solves Ax=b exponentially faster in every sense
No. The advantage depends on sparse or structured access to A, efficient preparation of b, favourable conditioning, an appropriate precision regime and a compact output question. Strong classical solvers may also exploit sparsity and structure.
20. Common misconception: measuring |x⟩ gives x
A computational-basis measurement samples coordinate probabilities proportional to |xj|². It does not reveal signs or complex phases directly, and one sample reveals only one index. Full reconstruction requires many measurements and suitable bases.
21. Common misconception: a large condition number means the algorithm is simply slower
It also signals sensitivity. Small perturbations in A or b can produce large changes in x, so an extremely ill-conditioned system may demand higher data and arithmetic precision even before quantum implementation details are considered.
22. Worked synthesis problem
Let A=diag(1,1/4) and |b⟩=(√3/2)|0⟩+(1/2)|1⟩.
Step 1: Condition number. With maximum eigenvalue magnitude 1 and minimum 1/4, κ=4.
Step 2: Apply the inverse. The unnormalised coefficients are √3/2 and 2.
Step 3: Norm. The squared norm is 3/4+4=19/4, so the norm is √19/2.
Step 4: Normalise. The solution state is
|x⟩=(√3|0⟩+4|1⟩)/√19.
Step 5: Probabilities. The computational-basis probabilities are 3/19 and 16/19.
Interpretation. The smaller eigenvalue receives greater inverse weighting, so the second spectral component becomes dominant.
23. Practice set
- Write the spectral expression for A⁻¹|b⟩.
- What output does HHL aim to prepare?
- Why is phase estimation useful?
- What does the controlled rotation encode?
- Define the 2-norm condition number.
- Why do small eigenvalues cause difficulty?
- What is lost when x is normalised into |x⟩?
- Why can data loading erase an apparent exponential advantage?
- Give one compact quantity that can be estimated from |x⟩.
- How can a non-Hermitian A be embedded into a Hermitian matrix?
- Why is preconditioning relevant?
- What is the difference between the historical HHL blueprint and modern QSVT-based linear-system methods?
Answers
Σ_j(β_j/λ_j)|u_j⟩.- A normalised quantum state proportional to A⁻¹b.
- It coherently associates eigenvalue estimates with eigenvector components.
- An amplitude proportional to 1/λ.
κ=σ_max/σ_minfor an invertible matrix.- Inversion amplifies them strongly and requires finer spectral control.
- The overall classical norm/scale of x.
- Preparing arbitrary amplitude data can require O(N) work.
- An expectation ⟨x|M|x⟩ for an efficiently measurable M.
[[0,A],[A†,0]].- It can reduce κ if efficiently implementable.
- HHL explicitly estimates eigenvalues and rotates by reciprocals; modern methods can approximate inverse spectral functions through block encodings and polynomial transformations.
Sources and further study
[1] Aram W. Harrow, Avinatan Hassidim and Seth Lloyd, Quantum algorithm for solving linear systems of equations. The original HHL algorithm and its input/output model.
[2] Aram W. Harrow, Review of Quantum Algorithms for Systems of Linear Equations. A review of HHL assumptions, follow-up work and related methods.
[3] András Gilyén, Yuan Su, Guang Hao Low and Nathan Wiebe, Quantum singular value transformation and beyond. A modern spectral-transformation framework containing improved matrix-inversion primitives.
Continue through Quantum Mathematics
Guide 17: Quantum Walks, Graph Spectra and Search develops graph-based spectral dynamics. Guide 18: Block Encodings, Singular Value Transformation and Polynomial Approximation gives the modern matrix-function language. Guide 20: Adiabatic Quantum Evolution, Spectral Gaps and Optimisation uses spectral gaps rather than inversion to control a computation.