Method

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 ∣x⟩|x\rangle proportional to A−1∣b⟩A^{-1}|b\rangle, after a measurement on an ancilla succeeds; not the vector xx
Cost of the original algorithm
Order log⁡(N) s2κ2/ε\log(N)\, s^2 \kappa^2/\varepsilon[1] for an ss-sparse N×NN \times N matrix with condition number κ\kappa and error ε\varepsilon
Classical comparison in the paper
Order NκN\sqrt{\kappa}[1] to find x, or estimate a property of it, for a sparse system
Best known scaling since
Order κlog⁡(1/ε)\kappa \log(1/\varepsilon)[3] queries to the matrix, which is optimal in κ\kappa
Qubits
log⁡2N\log_2 N for the system, plus a clock register for phase estimation, plus one ancilla
On hardware
The full circuit for 2×22 \times 2 systems on four qubits[6][8]
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.

  1. Can |b⟩ be prepared in about log N steps?

    The right-hand side has to become a quantum state whose NN amplitudes are the entries of bb. If bb is a table of numbers, that needs a quantum memory (QRAM) that does not exist at scale, and writing NN numbers into anything takes NN steps. Aaronson's point is that if preparing ∣b⟩|b\rangle takes a polynomial in NN, the speed-up is gone in the first step[2]. A b given by a short formula, such as a point load, passes.

  2. 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.

  3. Is the condition number small?

    κ\kappa is the ratio of the largest to the smallest eigenvalue in size. HHL's cost grows as κ2\kappa^2; the best later solvers grow as κ\kappa[3]. If κ\kappa grows like a power of NN, the advantage over classical solvers, which also depend on κ\kappa, is lost. Discretised differential equations are the usual trap: refining the grid raises κ\kappa. For the one-dimensional finite-difference matrix in the code below, κ\kappa is 9.5 at N=4N = 4 and 32.2 at N=8N = 8, and it grows about as N2N^2.

  4. Do you need only a few numbers about x?

    A measurement of ∣x⟩|x\rangle gives statistics, such as an expectation value ⟨x∣M∣x⟩\langle x|M|x\rangle or an overlap with a fixed vector. Learning any one entry of xx in general means running the algorithm about NN 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.

  5. 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.

TaskThe linear systemThe check it usually fails
Portfolio optimisationThe optimality (KKT) conditions of a mean-variance problem, or the Newton step of an interior point methodReadout: 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 regressionThe normal equations of the design matrixLoading: the data matrix has to sit in QRAM; with a low-rank design matrix the task is dequantised
Partial differential equationsA finite-difference or finite-element matrix on a gridConditioning: κ\kappa rises as the grid is refined, and the field itself is usually the wanted output
Kernel methods and classifiersA kernel or Gram matrixLoading 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 10−710^{-7}, their Table I gives 8×1068 \times 10^{6} logical qubits[5], 7×10297 \times 10^{29} T gates[5] and a T-depth of 2×10242 \times 10^{24}[5], spread over about 6×10126 \times 10^{12} 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 κ\kappa 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 2×22 \times 2 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 2×22 \times 2 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 AA was chosen so that its eigenvalues fit a clock register of one or two qubits exactly, which is what a 2×22 \times 2 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 readout

Honest mode builds eiAte^{iAt} 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

  1. A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters 103, 150502, 2009. arXiv:0811.3171.
  2. S. Aaronson. Read the fine print. Nature Physics 11, 291–293, 2015.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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