HHL and Quantum Linear Systems: The Fine Print Behind the Exponential Claim

Updated 2026-10-11 | 4 min read | QUANTUM (QNT) community

What the problem is

Solving linear equations, finding x so that Ax equals b, is everywhere: engineering simulations, data fitting, machine learning. When there are millions of unknowns, it is a big cost. In 2008 Aram Harrow, Avinatan Hassidim and Seth Lloyd showed a quantum algorithm (HHL) that seems to need only about log N effort, an exponential improvement. That sounded like a revolution. The fine print is why it turned into a lesson in reading claims carefully.

What HHL actually outputs

This is the first catch. HHL does not hand you the list of numbers x. It produces a quantum state whose amplitudes are proportional to x. You cannot read all those amplitudes out for free, because measuring gives you one sample at a time. The reference below says the algorithm estimates quadratic functions of the solution and "cannot efficiently output the solution x itself." Recovering the whole vector would mean repeating the run roughly N times, erasing the advantage.

So HHL is useful only if what you want is a summary: an average, an overlap with a chosen vector, or a property that feeds further quantum processing.

The runtime and its assumptions

The reference gives the runtime as order log(N) times kappa squared, against order N times kappa for the fastest classical method it cites (or N times the square root of kappa for positive semidefinite matrices), while Gaussian elimination, which produces the full solution, takes order N cubed. That comparison hides four conditions:

• Sparsity. The matrix must be sparse and efficiently describable, so that Hamiltonian simulation of its exponential is cheap. Without it the advantage vanishes, per the reference. Wossnig and coauthors (2018) extended the idea to dense matrices, with weaker gains.
• Condition number kappa. This is the ratio of the largest to smallest eigenvalue, a measure of how touchy the system is. Cost grows as kappa squared. The reference points out that poly-logarithmic dependence on kappa would imply BQP equals PSPACE, believed false, so you cannot just wish this dependence away. Bad kappa means slow runs.
• State preparation. The right-hand side b must be loaded as a quantum state efficiently. The reference cites Aaronson's point that expensive preparation would eliminate the advantage. See the data loading problem.
• Readout. As above, you must be content with a few numbers.

Is the speedup real?

The honest answer is: yes in a narrow, careful sense, and with a twist. The twist is dequantization. In 2018, Ewin Tang gave a classical algorithm for a recommendation-system problem that had been a leading candidate for exponential quantum speedup. Her abstract says the classical method is only polynomially slower than the quantum one, so the quantum algorithm does not give an exponential speedup there. The key was a sampling-style data structure that mimics, classically, what superposition provides. Gilyen, Lloyd and Tang (arXiv, November 2018) then built a classical analogue of HHL for low-rank matrices, and argued many low-rank quantum algorithms could be dequantised into classical sampling algorithms. The HHL reference page summarizes this line of work as finding that, for most quantum machine learning algorithms, classical algorithms match the exponential speedup under similar input assumptions. See dequantization explained.

Important nuance: dequantization applies to low-rank settings and specific input models. It does not kill every linear-algebra speedup. For high-rank, structured problems, such as those where the matrix arises from simulating a quantum or physical system and never needs to be stored, quantum methods may still hold an advantage. That is an active research area, and it is the territory where claims should be checked line by line.

What has been demonstrated

Experiments have been tiny. The reference lists three demonstrations in February 2013 on very small systems (photonic and a 4-qubit NMR run), and an NMR experiment reported around 2018 and 2019 solving an 8 by 8 system. These prove the circuit works in principle, not that it beats classical solvers. Later, theory has improved: Ambainis (2010) improved the runtime with variable-time amplitude amplification, and Childs, Kothari and Somma (2017) made a version with logarithmic dependence on precision.

How to read an HHL-style claim

1. Ask what is the output and whether a full answer vector is required.
2. Ask how the input is loaded and what it costs.
3. Ask for the sparsity and condition number of the real problem.
4. Ask whether a quantum-inspired classical algorithm exists for the same input model.

For a wider view of the machine-learning side, see quantum machine learning and the proven vs promised scorecard. This is education, not financial advice, and the QNT memecoin is independent of Quantinuum Ltd.

Sources and further reading

• Wikipedia: quantum algorithm for linear systems of equations (HHL)
• Tang: A quantum-inspired classical algorithm for recommendation systems (arXiv)
• Gilyen, Lloyd, Tang: Quantum-inspired low-rank stochastic regression (arXiv)

Reported as of 2026-10-09. Theory results are proven only under the stated assumptions, and experimental claims and classical rebuttals keep changing, so check the primary papers. Nothing here is financial advice and nothing here predicts the price of any asset. The QNT memecoin is independent of Quantinuum Ltd, the real company, and of every lab and researcher named on this page.

Frequently asked questions

Share on X

Keep reading

• Dequantization: When Classical Computers Catch Up
  How Ewin Tang's 2018 result and quantum-inspired classical algorithms reshaped expectations for quantum machine learning, and why it is good for science.
• The Data Loading Problem: Quantum Computing's Fine Print for AI
  Why getting big classical data into a quantum computer can erase a speedup, and what Scott Aaronson's fine print means for quantum machine learning.
• Quantum Machine Learning Explained
  What is quantum machine learning? A careful, plain English look at how quantum computers might help AI, what is proven, and what is still hype.

All Quantum computing guides | Back to top | Search the site

Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary