HHL Algorithm

Given an N × N Hermitian matrix A and a vector b, the linear system problem asks us to find x such that Ax = b. Classically, solving this system exactly using Gaussian elimination requires O(N³) operations, while iterative methods for sparse matrices require O(N s κ log(1/ε)) operations, where s is the sparsity, κ is the condition number, and ε is the desired precision. For very large systems arising in machine learning, partial differential equations, and optimization, these costs become prohibitive.

The HHL algorithm assumes that A is Hermitian (or can be made so by embedding), s-sparse (each row has at most s nonzero entries), and has condition number κ = |λ_max| / |λ_min|. The vector b is provided as a quantum state |b⟩, and the algorithm produces a quantum state |x⟩ proportional to A^{-1}|b⟩. The runtime scales as O(log(N) s² κ² / ε), which is exponentially faster in N than classical methods. However, reading out all components of x classically still requires O(N) measurements, so the speedup is most valuable when the goal is to compute global properties of x such as expectation values ⟨x|M|x⟩.

• •Hermitian Matrix: A must be Hermitian; non-Hermitian systems can be embedded into a larger Hermitian matrix.
• •Sparsity: Sparse matrices enable efficient Hamiltonian simulation, a key subroutine in the HHL algorithm.
• •Condition Number: The runtime scales as κ², so well-conditioned matrices (small κ) are essential for efficiency.
• •State Preparation: The input b must be encoded as a quantum state |b⟩; classical vector entry-wise readout is inefficient.

The HHL algorithm consists of three main stages, each operating on distinct quantum registers. First, Quantum Phase Estimation is performed on the unitary U = e^{iAt} using the b-register as the eigenstate register and a clock register of n qubits. This encodes the eigenvalues λ_j of A into the computational basis states of the clock register, transforming the state to ∑_j β_j |λ̃_j⟩ |u_j⟩, where |b⟩ = ∑_j β_j |u_j⟩ and |λ̃_j⟩ is the binary approximation of λ_j.

Second, a conditional rotation is applied to an ancilla qubit controlled on the clock register. The rotation angle for each eigenvalue component is chosen to be arcsin(C/λ̃_j), where C is a normalization constant satisfying C ≤ min_j |λ_j|. This operation entangles the ancilla with the other registers, giving amplitudes proportional to C/λ_j for the ancilla being in |1⟩. Third, the inverse QPE is applied to uncompute the clock register, returning it to |0⟩^⊗n. Conditioning on measuring the ancilla in |1⟩ yields the state |x⟩ ∝ ∑_j (β_j/λ_j) |u_j⟩, which is exactly the solution to the linear system.

• •Stage 1: QPE: Estimate eigenvalues of A by applying phase estimation to e^{iAt}, encoding them in the clock register.
• •Stage 2: Conditional Rotation: Rotate an ancilla qubit by arcsin(C/λ̃), creating amplitudes proportional to the inverse eigenvalues.
• •Stage 3: Uncomputation: Apply inverse QPE to disentangle and reset the clock register to its initial state.
• •Post-Selection: Measure the ancilla; the conditioned b-register contains the normalized solution state |x⟩.