1. Problem Statement
Given a Hermitian matrix $A \in \mathbb{C}^{N\times N}$ (sparse, well-conditioned)
and a vector $\mathbf{b} \in \mathbb{R}^N$, solve the linear system:
$$A\mathbf{x} = \mathbf{b} \implies \mathbf{x} = A^{-1}\mathbf{b}$$
Eq. (1) — Classical linear system
Best classical algorithm: conjugate gradient in $O(N \cdot \kappa \cdot \log(1/\epsilon))$ where $\kappa = \|A\|\cdot\|A^{-1}\|$ is the condition number.
HHL goal: Prepare the quantum state:
$$|x\rangle = \frac{A^{-1}|b\rangle}{\|A^{-1}|b\rangle\|}$$
Eq. (2) — Target quantum state encoding the solution
Important distinction: HHL outputs a quantum state $|x\rangle$, not the full vector $\mathbf{x}$. Extracting all $N$ components requires tomography — $O(N)$ measurements — which can negate the speedup. HHL is useful only when downstream processing can be done on the quantum state directly.
2. HHL Algorithm
The algorithm proceeds in three stages using quantum phase estimation (QPE):
Step 1: Eigendecomposition via QPE
Decompose $|b\rangle$ in the eigenbasis of $A$:
$$|b\rangle = \sum_j \beta_j |\psi_j\rangle, \quad A|\psi_j\rangle = \lambda_j|\psi_j\rangle$$
Eq. (3) — Spectral decomposition of $|b\rangle$ in eigenbasis of $A$
Quantum phase estimation encodes eigenvalues $\lambda_j$ into an ancilla register:
$$|b\rangle|0\rangle \xrightarrow{\text{QPE}} \sum_j \beta_j |\psi_j\rangle |\tilde{\lambda}_j\rangle$$
Eq. (4) — QPE encodes eigenvalues into ancilla (approximate: $\tilde{\lambda}_j \approx \lambda_j$)
Step 2: Controlled Rotation
Apply a rotation conditioned on $\tilde{\lambda}_j$ to a single ancilla qubit:
$$\sum_j \beta_j |\psi_j\rangle |\tilde{\lambda}_j\rangle |0\rangle \to \sum_j \beta_j |\psi_j\rangle |\tilde{\lambda}_j\rangle \left(\sqrt{1 - \frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle + \frac{C}{\tilde{\lambda}_j}|1\rangle\right)$$
Eq. (5) — Controlled rotation: encodes $1/\lambda_j$ in amplitude
Step 3: Uncompute QPE + Measure
Uncompute the eigenvalue register, then measure the ancilla in $|1\rangle$:
$$|\text{success}\rangle \propto \sum_j \beta_j \cdot \frac{C}{\lambda_j} |\psi_j\rangle = C \cdot A^{-1}|b\rangle$$
Eq. (6) — Post-selection on $|1\rangle$ gives $|x\rangle \propto A^{-1}|b\rangle$
3. HHL Circuit
HHL Circuit Schematic:
Ancilla: |0⟩ ──────────────────────────────────[R(λ)]──────────────── Meas
│ (controlled on clock)
Clock: |0⟩ⁿ ──[H⊗ⁿ]──[Controlled-U²ᵏ]──[QFT†]──────────────[QFT]──[H]──
(k=0..n-1) ↑ ↑
QPE maps Inverse QPE
λⱼ → |λ̃ⱼ⟩ (uncompute)
Input: |b⟩ ──[State prep]─────────────────────────────────────────────────
Result: ancilla=1 → |x⟩ ∝ A⁻¹|b⟩ (post-selected)
Gates:
H = Hadamard
Controlled-U²ᵏ = controlled e^{iAt·2^k} (Hamiltonian simulation)
QFT† = inverse Quantum Fourier Transform
R(λ) = Ry(2 arcsin(C/λ)) (amplitude encoding of 1/λ)
4. Complexity & Caveats
$$T_{\text{HHL}} = O\!\left(\log(N)\cdot \frac{\kappa^2}{\epsilon}\right) \quad \text{vs.} \quad T_{\text{classical}} = O(N\kappa\log(1/\epsilon))$$
Eq. (7) — HHL exponential speedup in $N$, quadratic in $\kappa$
Four caveats that can negate the speedup:
1. State preparation: Loading $|b\rangle$ from classical data requires $O(N)$ gates (or $O(\text{polylog}(N))$ with QRAM).
2. Readout: Extracting $\mathbf{x}$ from $|x\rangle$ requires $O(N)$ measurements (tomography).
3. Sparsity: $A$ must be $s$-sparse; complexity includes factor $s^2$.
4. Condition number: Complexity is $O(\kappa^2)$ — poorly conditioned matrices give polynomial (not exponential) advantage.
5. Dequantization (Tang 2019)
Ewin Tang (2019) showed that classical sampling-based algorithms can achieve similar complexities
to HHL for many ML tasks, given similar data access assumptions (sample access to $\mathbf{b}$ and $A$).
$$T_{\text{Tang}} = O\!\left(\text{poly}(\kappa, 1/\epsilon) \cdot \text{polylog}(N)\right)$$
Eq. (8) — Classical dequantized algorithm (comparable to HHL under same data access)
Impact: Tang's result shows that many claimed quantum ML speedups (recommendation systems, PCA, clustering) are not exponential when classical algorithms are also given quantum-inspired data access (sample + query access). It does NOT disprove all quantum advantage — only for specific tasks.
6. QSVT Framework
Quantum Singular Value Transformation (QSVT, Gilyén et al. 2019) is a unifying framework
that generalises HHL, phase estimation, amplitude amplification, and dozens of quantum algorithms.
Core idea: Given a block-encoding of $A$, apply any polynomial transformation $P(A)$ to its singular values using quantum signal processing (QSP).
$$\text{QSVT: } A \xrightarrow{\text{block-encoding}} U_A \xrightarrow{\text{QSP phases }\Phi} P^{SV}(A)$$
Eq. (9) — QSVT applies polynomial $P$ to singular values of $A$
7. Block Encoding
A unitary $U_A$ is an $(\alpha, a, \epsilon)$-block-encoding of $A$ if:
$$\left\|\langle 0|^{\otimes a} U_A |0\rangle^{\otimes a} - \frac{A}{\alpha}\right\| \leq \epsilon$$
Eq. (10) — Block-encoding: $A/\alpha$ appears in top-left block of $U_A$
Visually:
U_A = ┌──────────────────┐
│ A/α · · · │ ← top-left block is A/α
│ · · · · │
│ · · · · │
└──────────────────┘
Ancilla register |0⟩ᵃ selects the top-left block:
⟨0|ᵃ U_A |0⟩ᵃ = A/α
8. Quantum Signal Processing
QSP applies a degree-$d$ polynomial $P(\lambda)$ to each singular value $\lambda$ of $A$,
using a sequence of single-qubit rotations with phases $\Phi = (\phi_0, \phi_1, \ldots, \phi_d)$:
$$U_\Phi = e^{i\phi_0 Z}\prod_{k=1}^{d} \left(W(\lambda)\, e^{i\phi_k Z}\right)$$
Eq. (11) — QSP sequence ($W(\lambda) = $ signal rotation, $e^{i\phi Z} = $ processing rotation)
\begin{pmatrix} P(\lambda) & \cdot \\ \cdot & \cdot \end{pmatrix} = \langle +|U_\Phi|+\rangle
Eq. (12) — Top-left element implements $P(\lambda)$ for any polynomial satisfying parity/norm conditions
QSVT Unified Algorithm View
| Algorithm |
Polynomial $P$ |
QSVT instantiation |
| HHL |
$P(\lambda) \approx 1/\lambda$ |
Polynomial approximation to $1/x$ via QSVT |
| Phase estimation |
$P(\lambda) = e^{i\lambda t}$ |
Chebyshev approximation |
| Amplitude amplification |
$P(\lambda) = $ threshold |
Sign function approximation |
| Hamiltonian simulation |
$P(\lambda) = e^{-iH\tau}$ (Chebyshev) |
Optimal product formula |
9. Applications to QML
Quantum Kernel Methods
Kernel matrix $K_{ij} = |\langle\phi(x_i)|\phi(x_j)\rangle|^2$ computed via SWAP test. SVM dual problem solved via HHL. Caveat: kernel concentration in high dimensions.
Quantum PCA
QSVT extracts top eigenvectors of covariance matrix. Exponential speedup over classical PCA — but dequantized by Tang 2018.
Quantum Boltzmann Machines
Gibbs sampling via quantum MCMC (Layden et al.). QSVT used to simulate the Gibbs state $e^{-\beta H}/Z$ preparation.
Quantum LLM Inference
Attention matrix multiplication: $O \propto A^{-1}b$ via HHL. Key open problem: efficient QRAM for token embeddings.
10. Quantum-Enhanced MCMC (Layden et al. Nature 2023)
Classical MCMC (Metropolis-Hastings) is limited by mixing time $\tau_{\text{mix}}$ of the Markov chain. Quantum MCMC uses quantum coherence to propose non-local moves:
$$\text{Quantum proposal: } |\psi\rangle = \frac{1}{\sqrt{Z_\beta}} \sum_x e^{-\beta E(x)/2} |x\rangle$$
Eq. (13) — Coherent Gibbs state proposal distribution
$$\tau_{\text{mix}}^{\text{quantum}} \in O\!\left(\sqrt{\tau_{\text{mix}}^{\text{classical}}}\right) \quad \text{(quadratic speedup)}$$
Eq. (14) — Quadratic speedup in mixing time via quantum proposals
Demonstrated on 27-qubit IBM processors. Key application: Boltzmann machine training, lattice field theory, drug discovery sampling.