# The HHL Algorithm: Solving Linear Systems with Quantum **Source**: https://quantumsequrity.com/blog/hhl-algorithm-linear-systems **Category**: Quantum Algorithms --- [← Back to Blog](../../blog.html) Quantum Algorithms # The HHL Algorithm: Solving Linear Systems with Quantum 12 min read In 2008 three researchers at MIT and Caltech published an algorithm that, on its face, seemed to break a wall that had stood since the dawn of computing. Aram Harrow, Avinatan Hassidim, and Seth Lloyd showed that a quantum computer could solve a sparse linear system Ax = b in time logarithmic in the number of unknowns, while the best classical methods scale at least linearly. The result, now known as HHL, briefly suggested that quantum computers might one day accelerate everything from machine learning to fluid dynamics. The reality is more nuanced. HHL is a real exponential speedup, but the caveats matter so much that some researchers describe HHL as "the most subtle exponential speedup in quantum computing." ## Why HHL Matters Picture a city with millions of taxis serving millions of riders. A traffic engineer wants to know whether a small change in fares affects average wait times. The mathematics ends up as a giant linear system: thousands or millions of equations in thousands or millions of unknowns. Solving such systems is the bread and butter of scientific computing, and any speedup affects everything from weather prediction to portfolio optimization. HHL claimed an exponential speedup. The fine print determines whether that speedup applies to your problem. ### The 2008 paper Harrow, Hassidim, and Lloyd published "Quantum Algorithm for Linear Systems of Equations" in Physical Review Letters volume 103, page 150502, on October 7, 2009 (preprint arXiv:0811.3171, 2008). The paper proved that for sparse matrices A satisfying certain conditions, a quantum computer could prepare a state proportional to A^{-1} b in time polylog(N), where N is the dimension of the system. Classical methods need at least time linear in N for general A. ## The Problem in Layman's Terms Imagine you have a recipe with thousands of ingredients, and a friend tells you the final dish but not the amounts. To recover the ingredient amounts you would solve a system of equations: each ingredient interacts with the others, and the recipe encodes those relationships in a giant matrix. HHL is a quantum recipe that finds the ingredient amounts faster than classical computation, with three asterisks attached. ### Formal problem Given a square matrix A of size N x N and a vector b of size N, find x such that Ax = b. The classical state of the art uses conjugate gradient or sparse direct solvers. For sparse matrices with condition number kappa, the best classical complexity is roughly O(N s sqrt(kappa) log(1/epsilon)) where s is the sparsity. HHL achieves O(log(N) s^2 kappa^2 / epsilon), turning the linear N dependence into logarithmic. | Method | Time complexity | Output | |---|---|---| | Direct solver (LU) | O(N^3) | Full vector | | Conjugate gradient | O(N s sqrt(kappa) log(1/eps)) | Full vector | | HHL | O(log(N) s^2 kappa^2 / eps) | Quantum state | ## How HHL Works A musical synthesizer takes a complex sound, breaks it into pure tones, modifies each tone, and recombines them. HHL does the same thing with eigenvalues: decompose b into A's eigenvectors, divide each eigenvector amplitude by the corresponding eigenvalue, and recombine. The key trick is doing this without ever writing out the eigenvectors explicitly. ### Step by step 1. Encode the vector b as a quantum state |b> with amplitudes proportional to b's entries. 2. Apply quantum phase estimation (QPE) using e^{i A t} as the unitary. This entangles each eigenvalue lambda of A with a counting register. 3. Add an auxiliary qubit and rotate it conditionally on the counting register so its amplitude becomes proportional to 1/lambda. 4. Uncompute the QPE step. 5. Measure the auxiliary qubit. On the success outcome, the system register is now in a state proportional to A^{-1} b = x. The result is the quantum state |x>, not the explicit vector x. ## The Three Big Caveats A racecar that goes 500 miles per hour but only on a perfectly clean track is interesting; one that needs a vacuum chamber and a special fuel is a curiosity. HHL has three caveats that determine whether your problem is on the clean track or in the vacuum chamber. ### Caveat 1: State preparation You need a way to prepare |b> efficiently. If b is the result of an earlier quantum computation, you have it for free. If b is a classical vector of N numbers, just loading it into a quantum state takes O(N) time, which kills the exponential speedup before HHL even starts. ### Caveat 2: Sparsity and condition number HHL's complexity depends on s (the maximum number of non-zero entries per row) and kappa (the condition number of A, the ratio of largest to smallest eigenvalue magnitude). If s is O(polylog N) and kappa is O(polylog N), HHL gives an exponential speedup. If s or kappa grows polynomially in N, the speedup degrades. ### Caveat 3: Output extraction HHL outputs the quantum state |x>, not the classical vector x. To learn even a single coordinate of x by measurement requires repeating the algorithm many times. To learn all N coordinates is, again, O(N) work. The natural use case is computing some scalar function of x: an inner product , an expectation value , or the success probability of a quantum state. Anything more general loses the speedup. ## Aaronson's Critique and the BQP-Complete Result Scott Aaronson, an MIT-then-Texas computer scientist, wrote a widely cited critique titled "Quantum Machine Learning Algorithms: Read the Fine Print" published in Nature Physics 11, page 291 (2015). His point: HHL gives an exponential speedup over classical algorithms only when all three caveats line up perfectly, and many proposed quantum machine learning algorithms based on HHL fail at least one caveat in practice. ### The complexity-theoretic punchline Harrow, Hassidim, and Lloyd themselves proved that the linear-systems problem they solved is BQP-complete: any quantum computation can be reduced to a linear-system problem of the form HHL solves. That is impressive complexity-theoretically, because it means a fast classical algorithm for the same problem would let classical computers simulate every quantum circuit. But it also means HHL is not generically more useful than any other BQP-complete primitive; it inherits all the limitations of the broader complexity class. ## Where HHL's Speedup Survives A specialty tool can still be valuable if it solves a real problem better than the alternatives. HHL's speedup survives in carefully constrained settings. ### Genuine applications | Application | Reason HHL helps | |---|---| | Quantum chemistry response | Eigenvector amplitudes feed back into a quantum simulation | | Quantum machine learning kernels | Inner products of |x> with another quantum state | | Differential equations on grids | Sparse, well-conditioned operators | | Quantum gradient computation | Output is itself a quantum state used downstream | In each case the quantum state |x> is the natural input to a subsequent quantum computation, sidestepping the output-extraction caveat. ## Improved Versions Researchers have built faster, more robust variants of HHL since 2009. ### Childs-Kothari-Somma 2017 Andrew Childs, Robin Kothari, and Rolando Somma showed in SIAM Journal on Computing 46(6) that HHL's polynomial dependence on epsilon^{-1} can be reduced to logarithmic, using techniques from quantum signal processing. This shaves a major cost factor for high-precision applications. ### Optimal HHL via block encoding Block-encoded matrix arithmetic, developed by Gilyen, Su, Low, and Wiebe in their 2019 STOC paper "Quantum singular value transformation," gives the most efficient known framework for matrix functions on a quantum computer. HHL becomes a special case of applying the function 1/x to a block-encoded matrix. These improvements still leave the three caveats in place. Better complexity inside HHL does not solve the input or output bottlenecks. ## Real Hardware Status A model car can demonstrate steering, braking, and acceleration without ever leaving the showroom. HHL has been demonstrated on real quantum hardware for tiny systems. The first demonstration, published by Cai et al. in Physical Review Letters 110, 230501 (2013), solved a 2 x 2 system on a four-qubit photonic processor. Later demonstrations on superconducting hardware have solved 4 x 4 and 8 x 8 systems with limited fidelity. These are proof-of-concept demonstrations. Cryptographically or scientifically interesting linear systems involve millions or billions of unknowns, far beyond current hardware. Realistic deployments of HHL await fault-tolerant machines. ## Why HHL Does Not Threaten Cryptography Most quantum cryptanalysis lives in the regime of order-finding (Shor) or amplitude amplification (Grover). HHL inverts a matrix, which is not the standard form of any deployed public-key cryptosystem. ### Lattice cryptanalysis and HHL Some researchers have asked whether HHL could speed up the lattice attacks that underpin ML-KEM and ML-DSA's security analysis. Lattice cryptanalysis reduces to short-vector problems (SVP, CVP, BDD) that are not naturally framed as linear-system inversion. As of April 2026, no published analysis suggests HHL gives any meaningful advantage in solving Module-LWE or Module-SIS. NIST's selection of these problems was informed by exactly this kind of resilience. ### Hash-based and code-based schemes SLH-DSA, LMS, and HQC have no algebraic structure that HHL can exploit. Their security rests on hash function preimage resistance and decoding random codes, both far outside the linear-systems framework. ## QNSQY's Approach to Quantum-Era Threats QNSQY ships ML-KEM-512/768/1024, ML-DSA-44/65/87, SLH-DSA, FN-DSA, HQC-128/192/256, and LMS in hybrid mode with X25519 and Ed25519. None of these primitives are vulnerable to HHL or to any other published quantum algorithm with a meaningful speedup. The hybrid construction also keeps current networks safe against the only attack vector that matters today: classical adversaries collecting traffic for later quantum decryption. If a future researcher discovers a way to cast a primitive's underlying problem as a sparse linear system that HHL can solve quickly, the hybrid mode means an attacker would still need to break the classical primitive too. That defense in depth is the entire reason hybrid mode exists. ## Frequently Asked Questions ### Does HHL solve every linear system exponentially faster? No. HHL needs three conditions: efficient state preparation of |b>, low sparsity and condition number of A, and an output that is a scalar derived from |x> rather than the full vector x. Without all three, HHL's exponential advantage shrinks or vanishes. ### Will HHL break cryptography? No published result connects HHL to any deployed cryptosystem in a way that gives meaningful advantage. RSA, ECC, and finite-field Diffie-Hellman fall to Shor's algorithm, not HHL. Lattice and hash-based post-quantum schemes have structures HHL cannot exploit. ### Why is HHL so often cited in quantum machine learning? HHL was central to early proposals for quantum support vector machines, quantum recommendation systems, and quantum principal component analysis. Many of those proposals fail Aaronson's three-caveat test, especially the input bottleneck. Subsequent classical "dequantized" algorithms (Tang 2019, Chia et al. 2020) have shown that several proposed HHL-based ML speedups had classical counterparts when given the same access model. ### What is the difference between HHL and quantum singular value transformation? Quantum singular value transformation (QSVT), introduced by Gilyen-Su-Low-Wiebe in 2019, is a generalized framework that lets you apply polynomial functions to the singular values of a block-encoded matrix. HHL is the special case where the polynomial approximates 1/x. QSVT is now the standard framework for designing matrix-arithmetic quantum algorithms. ### Will my QNSQY-encrypted files be safer because HHL is limited? Your files are protected by hybrid post-quantum encryption that does not rely on the absence of HHL specifically. Even if HHL were generalized into something far more powerful, the underlying lattice and hash assumptions QNSQY uses would still need to be broken. The hybrid mode means classical breaks against current primitives also fail. ## Sources 1. Harrow, A. W., Hassidim, A., Lloyd, S. "Quantum Algorithm for Linear Systems of Equations." Physical Review Letters 103, 150502, 2009. https://arxiv.org/abs/0811.3171 2. Aaronson, S. "Quantum Machine Learning Algorithms: Read the Fine Print." Nature Physics 11, page 291, 2015. 3. Childs, A. M., Kothari, R., Somma, R. D. "Quantum algorithm for systems of linear equations with exponentially improved dependence on precision." SIAM Journal on Computing 46(6), 2017. 4. Gilyen, A., Su, Y., Low, G. H., Wiebe, N. "Quantum singular value transformation and beyond." STOC 2019. https://arxiv.org/abs/1806.01838 5. NIST. FIPS 203, 204, 205. https://csrc.nist.gov/projects/post-quantum-cryptography ## Related Articles - [Quantum machine learning overview](../quantum-machine-learning-overview.html) - [Quantum phase estimation](../quantum-phase-estimation.html) - [What is post-quantum cryptography?](../what-is-post-quantum-cryptography.html) - [Why quantum threatens classical encryption](../why-quantum-threatens-classical-encryption.html) - [ML-KEM explained](../ml-kem-explained.html) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)