| HHL algorithm | |
|---|---|
| Name | HHL algorithm |
| Inventor | Harold Kroto |
| Developer | Peter W. Shor |
| Introduced | 2009 |
| Paradigm | Quantum algorithm |
| Problem | Solving linear systems of equations |
HHL algorithm
The HHL algorithm is a quantum algorithm for solving linear systems of equations on a quantum computer. Developed in 2009, it offers a potential exponential speedup in specific regimes compared to classical methods, making it significant for quantum algorithms in Quantum Physics and numerical simulation. The algorithm connects quantum simulation, quantum linear algebra and applications across physics and engineering.
The HHL algorithm was introduced in 2009 by Aram Harrow, Avinatan Hassidim and Seth Lloyd in the paper "Quantum algorithm for linear systems of equations" published in Physical Review Letters. It built on earlier work in quantum computing such as Shor's algorithm and quantum simulation techniques pioneered by Richard Feynman and Seth Lloyd. The proposal sparked substantial interest because solving large sparse linear systems is central to scientific computing, and an asymptotic speedup could transform computational tasks in condensed matter physics, many-body physics and computational fluid dynamics. Following its introduction, researchers at institutions including MIT, Harvard University, Caltech, and IBM pursued theoretical refinements and experimental implementations on platforms like superconducting qubits and trapped ion systems.
HHL addresses the problem of preparing a quantum state proportional to the solution |x⟩ of a linear system A x = b, where A is an N×N Hermitian, sparse, well-conditioned matrix and |b⟩ is a quantum state encoding the right-hand side. In quantum physics, many problems reduce to linear systems or eigenvalue problems: discretized versions of the Schrödinger equation, linear response calculations, Green's function evaluations, and inverse problems in quantum tomography. The algorithm is particularly relevant when observables are expectation values ⟨x|O|x⟩ rather than full classical representations of x, aligning with quantum measurement paradigms used in quantum chemistry and materials science.
HHL combines several quantum primitives: - State preparation: encode the vector b as a quantum state |b⟩ using techniques from quantum state tomography and amplitude encoding. - Hamiltonian simulation: implement e^{-iAt} using sparse Hamiltonian simulation methods such as those developed by Andrew Childs and others, employing trotterization or more advanced simulation routines. - Quantum phase estimation (QPE): apply quantum phase estimation to estimate eigenvalues λ_j of A with an ancilla register, exploiting the unitary e^{-iAt}. - Controlled rotation and amplitude amplification: use estimated eigenvalues to perform a conditional rotation that maps |λ_j⟩|b_j⟩ to |λ_j^{-1}b_j⟩, then uncompute QPE and measure ancilla to obtain |x⟩ up to normalization. The workflow depends critically on access to oracles for sparse matrix entries and efficient implementations of controlled unitaries. Core references include the original HHL paper and subsequent algorithmic improvements by researchers at University of Waterloo and Perimeter Institute.
The original complexity claims give runtime polylogarithmic in N under assumptions: A is sparse with O(polylog N) simulation cost, condition number κ = O(polylog N), and efficient state preparation of |b⟩. The overall cost scales as O(poly(log N) κ^2 / ε), where ε is target precision, though many refinements improve dependence on κ and ε. Resource requirements include qubit registers for the data and phase estimation, quantum circuits for Hamiltonian simulation, and ancilla qubits for rotations and measurements. Practical performance is highly sensitive to sparsity, condition number, and the cost of state preparation; in regimes where those assumptions fail, classical algorithms such as conjugate gradient method or direct solvers remain competitive.
Error sources include Hamiltonian simulation error, phase estimation inaccuracies, finite precision in controlled rotations, and decoherence in physical qubits. Stability issues arise from large condition numbers κ: small eigenvalues amplify noise during inversion, degrading the fidelity of |x⟩. Regularization techniques analogous to classical Tikhonov regularization and truncated spectral inversion have been proposed to mitigate ill-conditioning. The algorithm's reliance on oracular access to A and efficient |b⟩ preparation is a practical bottleneck; transforming classical data into amplitude encodings can incur O(N) cost, offsetting asymptotic speedups. Fault-tolerant quantum error correction, as pursued by John Preskill and experimental groups, is often assumed for large-scale, high-precision deployments.
Proof-of-principle demonstrations of HHL or subroutines have been performed on small systems using photonic quantum computing, nuclear magnetic resonance (NMR), trapped ion platforms, and superconducting qubits. Notable experiments include implementations of two- and three-qubit instances that reproduce simple linear solves and validate controlled-rotation steps; these were conducted by research groups at University of Science and Technology of China and collaborative teams at IBM Research and University of Vienna. Software toolkits such as Qiskit and Cirq include modules for quantum linear algebra and simulation that enable small-scale emulation. Large-scale practical realization awaits scalable qubit counts, improved coherence, and efficient state-loading hardware such as quantum random access memory (QRAM).
When applicable, HHL can accelerate tasks in quantum chemistry (electronic structure linearizations), solving discretized linear partial differential equations in computational fluid dynamics and electromagnetics, and inverse problems in seismology and medical imaging. In machine learning, HHL-inspired routines underpin quantum algorithms for least-squares fitting and support-vector machines developed by researchers at Google Quantum AI and academic groups. In physics research, faster linear solvers may benefit density functional theory workflows and time-dependent simulations where repeated linear solves dominate cost. Practical impact depends on matching problem structure to the algorithm's assumptions and integrating HHL within broader workflows that respect national priorities for stable, reliable scientific infrastructure.
Category:Quantum algorithms