What is HHL and why did its fine print kill so many claims?

Status as of: September 15, 2026. This is a dictionary entry with a body count. HHL — the Harrow–Hassidim–Lloyd algorithm for linear systems (Phys. Rev. Lett. 103, 150502, 2009) — carries the most famous fine print in quantum computing: four conditions attached to its exponential speedup. Between 2014 and 2016 a wave of quantum machine-learning claims was built on top of it; between 2018 and 2022, classical «dequantization» algorithms took most of that wave down. Rosetta Quantum files the algorithm, the four conditions, and the scoreboard — every number with its source.

What does HHL actually do?

It prepares a quantum state — not a spreadsheet of numbers. Given a linear system A·x = b, the algorithm of Harrow, Hassidim and Lloyd (posted November 2008 as arXiv:0811.3171; published in Phys. Rev. Lett. 103, 150502, 2009) produces a quantum state |x⟩ proportional to the solution A⁻¹|b⟩, using a circuit whose size grows only polylogarithmically with the dimension N of the system — for the state-preparation task, exponentially better in N than writing out all N entries. Its engine is quantum phase estimation, the subroutine Rosetta filed yesterday in the QPE entry.

Three structural facts frame everything below:

• The problem is as hard as quantum computing itself. The original paper shows matrix inversion in this access model is BQP-complete (HHL 2009) — a fast classical simulation of HHL on all inputs would collapse the quantum/classical distinction. The theorem is not in dispute; the applications were.
• The cost scales with the fine print, not just with N. Runtime depends on the sparsity s, the condition number κ and the precision ε (HHL 2009). Childs, Kothari and Somma cut the precision cost exponentially, to polylogarithmic in 1/ε (SIAM J. Comput. 46, 2017); Costa et al. reached optimal κ·log(1/ε) scaling via a discrete adiabatic theorem (arXiv:2111.08152, 2021); and in March 2026 Low and Su made the query count to the state-preparation oracle optimal too, Θ(1/√p) (Quantum, 2026). The solver keeps getting sharper. The conditions do not go away.
• «Prepares a state» is doing all the work. Reading out the full solution vector entry by entry costs roughly N repetitions, which cancels the exponential gain (Aaronson, Nat. Phys. 11, 291–293, 2015). What HHL offers is not «solve my spreadsheet faster»; it is «sample properties of the solution of an enormous, sparse, well-conditioned system you can load without looking at it».

What exactly is the fine print?

Four conditions, spelled out in Scott Aaronson's 2015 commentary «Read the fine print» (Nat. Phys. 11, 291–293; full technical version):

1. Loading. The input vector b must become the quantum state |b⟩ quickly — which requires either an explicit formula for its entries or a quantum RAM. QRAM at useful scale does not exist as deployed hardware; Rosetta filed that bottleneck separately in the QRAM entry.
2. Simulation. The computer must be able to apply e^(−iAt) efficiently — true when A is sparse or otherwise structured; false in general.
3. Conditioning. The runtime grows roughly linearly with the condition number κ (Aaronson 2015). If κ grows polynomially with N, the exponential speedup is gone.
4. Readout. The output is the state |x⟩. You may sample from it or estimate observables ⟨x|M|x⟩; extracting the concrete entries of x generally costs of order N repetitions (Aaronson 2015).

None of this is a scandal, and none of it was hidden — the caveats are in the 2009 paper itself. The scandal, where there was one, was downstream: applications that quietly waived one condition or another and advertised the headline speedup anyway.

Which claims did the fine print kill?

The wave that fell was quantum machine learning, 2014–2016: quantum PCA, quantum support-vector machines, and the Kerenidis–Prakash quantum recommendation-systems algorithm (arXiv:1603.08675, 2016), all built on HHL-style linear algebra. In July 2018, Ewin Tang showed a classical sampling algorithm that matches the recommendation-systems speedup up to polynomial factors (arXiv:1807.04271) — the claimed exponential advantage evaporated. The same «quantum-inspired» toolkit then dequantized quantum PCA and supervised clustering (arXiv:1811.00414, 2018) and low-rank matrix inversion itself (Gilyén, Lloyd and Tang, arXiv:1811.04909, 2018; generalized into a full framework by Chia et al., J. ACM, 2022).

The pattern is exact, and it is the reason this entry exists: every dequantized claim had waived part of the fine print — almost always by assuming low-rank data. Low rank is precisely the regime where a classical computer can imitate quantum access by clever sampling; Tang's own heuristic is that low-dimensional linear algebra «likely can be dequantized», while the genuinely high-dimensional sparse regime is where a quantum speedup can survive (Tang, overview, 2019). Rosetta published the full autopsy of that episode in the dequantization entry and the machine-learning verdict in is quantum useful for ML; this post files the algorithm those claims were built on.

What survives in September 2026?

The theorem survives intact — what died was a marketing shortcut. What remains standing, with sources:

• BQP-completeness (HHL 2009): the problem class is as powerful as quantum computation; it will not be dequantized wholesale without collapsing that class.
• The surviving regime: sparse, genuinely high-dimensional, well-conditioned systems whose input arrives quantum-natively (from a physics simulation, not from a CSV that would need QRAM) and whose answer is an observable, not a vector (Tang 2019; Aaronson 2015).
• An algorithm line that is still moving in 2026: optimal κ scaling (Costa et al. 2021) and optimal state-preparation queries (Low & Su, Quantum, mar-2026) are real, recent theory improvements.

What has not happened, in the future tense it deserves: an end-to-end HHL advantage on a real dataset — load, solve, read out, beat the best classical pipeline at equal budget — will have to be demonstrated; as of September 15, 2026 no such demonstration exists in the public record, and HHL end-to-end is accordingly absent from Rosetta's list of problems with proven quantum advantage. Rosetta has not run HHL on its own bench either — our ledger records zero advantaged solves involving HHL, ours or anyone's — so the verdict above rests on the public record, not on house data.

What has actually run on hardware?

Dimension 2 in 2013; dimension 8 in 2024. The first experimental demonstrations solved 2×2 systems on photonic processors (Cai et al., Phys. Rev. Lett. 110, 230501, 2013). Eleven years later, the record application demonstration is the hybrid HHL++ run by JPMorganChase researchers on Quantinuum H-series trapped-ion hardware: 4×4 portfolio-optimization systems, a scaling study at 8×8, two-qubit gate depth up to 291, and a median degradation of 4.17% versus noiseless simulation — self-described as «the largest experimental demonstrations of HHL for an application to date» (Sci. Rep. 14, 20610, sep-2024). Fifteen years after the paper, the measured frontier of the algorithm with the exponential promise is an 8×8 matrix. That is not an insult; it is the honest scale of early fault-tolerant-adjacent hardware — and it is the number that belongs on the cover.

What we don't know

• Whether a commercially relevant dataset satisfying all four conditions exists. The surviving regime is well defined in theory; nobody has yet exhibited a named industrial linear system, with its loading path and observable, that lives in it. Absence of the exhibit is not proof of absence.
• Whether the sparse high-rank regime will also fall. There is no dequantization of it today and no proof that one is impossible (Tang 2019). Both directions remain open.
• What has run privately. Our hardware count covers the public record; industrial runs beyond 8×8 that were never published would sit outside it.
• Future cost curves. The 2022–2026 solver improvements will keep compounding or they will plateau; we will not forecast which. We will update this entry when the public record moves.

Rosetta Quantum publishes verdicts with raw, reproducible data. This is educational content, not a product claim.