HHL algorithm: does your linear-system problem qualify?
The HHL algorithm (Harrow, Hassidim and Lloyd, 2009) does not hand back the solution x of Ax = b. It prepares a quantum state proportional to x, in time that grows with log N but also with the condition number of A, and it is fast only if b loads cheaply, A can be simulated cheaply, A is well conditioned, and you need a few numbers about x rather than x itself. No application has been shown to meet all four end to end, and hardware runs of the full circuit have stayed at toy sizes, 2×2 systems in the best-known experiments.
Updated
At a glance
- What it outputs
- A quantum state proportional to , after a measurement on an ancilla succeeds; not the vector
- Cost of the original algorithm
- Order [1] for an -sparse matrix with condition number and error
- Classical comparison in the paper
- Order [1] to find x, or estimate a property of it, for a sparse system
- Best known scaling since
- Order [3] queries to the matrix, which is optimal in
- Qubits
- for the system, plus a clock register for phase estimation, plus one ancilla
- In eigenkit
- An HHL solver for an exact simulator, with a gate-level "honest" mode; it reads the full statevector
Does my problem qualify? Five checks
Aaronson's "Read the fine print" lists four conditions under which HHL keeps its exponential speed-up[2]. Each one, if it fails, costs the whole advantage on its own, so a problem has to pass all of them. A fifth check, dequantisation, came later.
Can |b⟩ be prepared in about log N steps?
The right-hand side has to become a quantum state whose amplitudes are the entries of . If is a table of numbers, that needs a quantum memory (QRAM) that does not exist at scale, and writing numbers into anything takes steps. Aaronson's point is that if preparing takes a polynomial in , the speed-up is gone in the first step[2]. A b given by a short formula, such as a point load, passes.
Can e^(iAt) be applied cheaply?
The original analysis assumes A is sparse and that its non-zero entries can be computed on demand[1]. Sparse in the matrix sense is not always enough in practice: eigenkit's gate-level mode builds the evolution from a sum of Pauli strings, and its docs show which matrices are actually cheap: a random diagonal matrix, one non-zero per row, still needs N Pauli terms.
Is the condition number small?
is the ratio of the largest to the smallest eigenvalue in size. HHL's cost grows as ; the best later solvers grow as [3]. If grows like a power of , the advantage over classical solvers, which also depend on , is lost. Discretised differential equations are the usual trap: refining the grid raises . For the one-dimensional finite-difference matrix in the code below, is 9.5 at and 32.2 at , and it grows about as .
Do you need only a few numbers about x?
A measurement of gives statistics, such as an expectation value or an overlap with a fixed vector. Learning any one entry of in general means running the algorithm about times[2], which removes the speed-up. If the downstream task needs the whole vector, as portfolio weights or a pressure field usually do, the problem does not qualify.
Is A far from low rank?
If A is close to low rank and the data sits in a structure that allows sampling rows by their norm, classical "quantum-inspired" algorithms run in time independent of the dimension too. Chia and colleagues extend this to essentially all known quantum linear-algebra techniques in that input model, including low-rank regression[4]. In that case there is no exponential gap left to exploit.
Applied problems that reduce to Ax = b, and where they stall
Most proposed uses of HHL turn an applied task into a linear system. These are the common ones, with the check each most often fails.
| Task | The linear system | The check it usually fails |
|---|---|---|
| Portfolio optimisation | The optimality (KKT) conditions of a mean-variance problem, or the Newton step of an interior point method | Readout: the weights are the answer, so the state has to be read back by tomography, a dominant cost in end-to-end estimates; the systems are also poorly conditioned |
| Least-squares regression | The normal equations of the design matrix | Loading: the data matrix has to sit in QRAM; with a low-rank design matrix the task is dequantised |
| Partial differential equations | A finite-difference or finite-element matrix on a grid | Conditioning: rises as the grid is refined, and the field itself is usually the wanted output |
| Kernel methods and classifiers | A kernel or Gram matrix | Loading and rank: kernel matrices are often close to low rank, and the training data has to be loaded first |
A task can still be worth studying when it fails one check, but then the speed-up has to come from somewhere other than HHL's scaling in N.
What the end-to-end estimates say
The most detailed published estimate costs a whole application, not the linear solver alone. Dalzell and colleagues compiled a quantum interior point method for portfolio optimisation, with a quantum linear-system solver at its core, down to logical qubits and T gates, and measured the instance parameters on small simulated cases built from historical stock data[5]. They used the optimal-scaling solver of Costa et al., not HHL itself, so HHL would cost more.
At 100 assets and a precision of , their Table I gives logical qubits[5], T gates[5] and a T-depth of [5], spread over about circuits[5] run one after another. Even at gigahertz clock speeds that depth would take millions of years[5], while a laptop solves the same 100-stock problem in seconds. The authors name the causes: large constant factors, poorly conditioned linear systems, and the tomography needed to read the solution out. Those are checks three and four above.
Their numbers are not the final word, and the paper says so: better subroutines will lower them. But the gap is many orders of magnitude, and the obstacles are the structural conditions, not engineering details. For a problem of your own, the same exercise applies: estimate and the readout you need before estimating qubits.
What has run on hardware
The full HHL circuit, with phase estimation, the controlled rotation and uncomputation, has been run on systems. Cai et al. used four photonic qubits and reported solution fidelities from 0.825 to 0.993[6] across input vectors. Barz et al. solved systems on a two-qubit photonic processor[7]. Zheng et al. ran it on four superconducting qubits and measured a process fidelity of 0.837 ± 0.006[8].
In each of them was chosen so that its eigenvalues fit a clock register of one or two qubits exactly, which is what a demonstration allows. They show that the pieces work, not that the algorithm scales. Larger systems need a longer phase-estimation stage and a deeper Hamiltonian simulation for every extra bit of eigenvalue resolution, and that depth is what today's noise does not survive.
An 8×8 system in eigenkit, gate by gate
import numpy as np
from eigenkit import HHL
# The 1D finite-difference matrix, 8 x 8, with a unit load on the first node
A = 2 * np.eye(8) - np.eye(8, k=1) - np.eye(8, k=-1)
b = np.zeros(8)
b[0] = 1.0
result = HHL(n_eigenvalue_qubits=6, mode="honest").solve(A, b)
print(round(np.linalg.cond(A), 1)) # 32.2
print(np.round(result.solution.real, 3)) # 0.869 0.739 0.621 0.515 0.411 0.305 0.205 0.103
print(np.round(np.linalg.solve(A, b), 3)) # 0.889 0.778 0.667 0.556 0.444 0.333 0.222 0.111
print(round(result.residual, 3)) # 0.019, that is ‖Ax − b‖ / ‖b‖
print(round(1 / result.readout_probability)) # 27 state preparations per usable readoutHonest mode builds from elementary gates on 10 qubits (3 for the system, 6 for the clock, 1 ancilla) and runs on the built-in NumPy simulator in a few seconds. The vector is read from the exact statevector, which no hardware can do; a device would return counts for one observable, and only 1 run in 27 would be usable.
Run it on a real QPU with EigenOrbit RouterThe honest-mode circuit for a 2×2 system, where a device returns counts for one observable of |x⟩, not the vector.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).
Questions
What is the HHL algorithm used for?
It prepares a quantum state proportional to the solution of a linear system Ax = b, so that a property of the solution, such as an expectation value, can be measured. It has been proposed for portfolio optimisation, regression, differential equations and machine learning, but none of these has a demonstrated end-to-end advantage, and in practice it is a subroutine studied on simulators.
Is HHL exponentially faster than classical solvers?
Only under four conditions at once: the vector b can be loaded in about log N steps, the matrix can be simulated cheaply, the condition number is small, and only a few numbers about the solution are needed. If any one fails, the exponential gap disappears. For low-rank matrices, classical sampling algorithms close the gap as well.
Can HHL run on a real quantum computer?
The full circuit has run for 2×2 systems on four photonic or superconducting qubits, with the eigenvalues known in advance. Larger systems need deeper circuits than today's noise allows, so the algorithm is studied on simulators.
Why does the condition number matter for HHL?
The condition number κ is the ratio of the largest to the smallest eigenvalue of A in size. The success probability of HHL's final measurement falls with κ, so its cost grows as κ squared, and the best later solvers still grow linearly in κ. Matrices from fine grids or nearly singular models have large κ, which removes the advantage.
Does HHL give me the solution vector x?
No. It gives a quantum state whose amplitudes are proportional to x. Reading every entry would take about N repetitions, which cancels the speed-up. Simulators, including eigenkit's, can return the whole vector because they hold the exact state, which hardware does not.
Is there a better quantum linear solver than HHL?
Yes, in scaling. Later algorithms reduce the dependence on precision and on the condition number, and the solver of Costa et al. (2022) is optimal in κ. They keep the same input and output conditions, so the checklist on this page applies to them unchanged, and the published end-to-end estimates use them and still find costs far beyond any planned machine.
Sources
- A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters 103, 150502, 2009. arXiv:0811.3171.
- S. Aaronson. Read the fine print. Nature Physics 11, 291–293, 2015.
- P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, D. W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum 3, 040303, 2022. arXiv:2111.08152.
- N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang, C. Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. Journal of the ACM 69(5), 2022. arXiv:1910.06151.
- A. M. Dalzell, B. D. Clader, G. Salton, M. Berta, C. Y.-Y. Lin, D. A. Bader, N. Stamatopoulos, M. J. A. Schuetz, F. G. S. L. Brandão, H. G. Katzgraber, W. J. Zeng. End-to-end resource analysis for quantum interior point methods and portfolio optimization. PRX Quantum 4, 040325, 2023. arXiv:2211.12489.
- X.-D. Cai, C. Weedbrook, Z.-E. Su, M.-C. Chen, M. Gu, M.-J. Zhu, L. Li, N.-L. Liu, C.-Y. Lu, J.-W. Pan. Experimental quantum computing to solve systems of linear equations. Physical Review Letters 110, 230501, 2013. arXiv:1302.4310.
- S. Barz, I. Kassal, M. Ringbauer, Y. O. Lipp, B. Dakić, A. Aspuru-Guzik, P. Walther. A two-qubit photonic quantum processor and its application to solving systems of linear equations. Scientific Reports 4, 6115, 2014. arXiv:1302.1210.
- Y. Zheng, C. Song, M.-C. Chen, B. Xia, W. Liu, Q. Guo, L. Zhang, D. Xu, H. Deng, K. Huang, Y. Wu, Z. Yan, D. Zheng, L. Lu, J.-W. Pan, H. Wang, C.-Y. Lu, X. Zhu. Solving systems of linear equations with a superconducting quantum processor. Physical Review Letters 118, 210504, 2017. arXiv:1703.06613.
Run it yourself with eigenkit
eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.
$ pip install eigenkit