qbraid_algorithms.hhl

Harrow-Hassidim-Lloyd (HHL) Algorithm

Harrow-Hassidim-Lloyd (HHL)

This module provides an implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm, a quantum algorithm for solving systems of linear equations. The HHL algorithm offers exponential speedup over classical methods for certain classes of sparse, well-conditioned matrices, making it fundamental for quantum machine learning, optimization, and scientific computing applications. The algorithm combines quantum phase estimation, controlled rotations, and amplitude amplification to encode the solution of \(A\mathbf{x} = \mathbf{b}\) in quantum amplitudes, enabling efficient extraction of linear system solutions.

FORMULATION

Linear System Problem: Given a Hermitian matrix \(A \in \mathbb{C}^{N \times N}\) and vector \(|b\rangle\), find the solution \(|x\rangle\) to: \(A|x\rangle = |b\rangle\)

Algorithm Steps:

  1. State Preparation: Prepare the input state \(|b\rangle\) and ancilla qubits:

    \(|\psi_0\rangle = |b\rangle \otimes |0\rangle_{\text{clock}} \otimes |0\rangle_{\text{ancilla}}\)

  2. Quantum Phase Estimation: Apply QPE to estimate eigenvalues \(\lambda_j\) of \(A\):

    \(|\psi_1\rangle = \sum_j \beta_j |u_j\rangle \otimes |\tilde{\lambda}_j\rangle \otimes |0\rangle\)

  3. Controlled Rotation: Apply controlled rotation based on eigenvalue estimates:

    \(|\psi_2\rangle = \sum_j \beta_j |u_j\rangle \otimes |\tilde{\lambda}_j\rangle \otimes \left(\sqrt{1-\frac{C^2}{\tilde{\lambda}_j^2}}|0\rangle + \frac{C}{\tilde{\lambda}_j}|1 \rangle\right)\)

  4. Uncomputation: Reverse QPE and measure ancilla in \(|1\rangle\) state:

    \(|x\rangle = \frac{1}{\sqrt{\sum_j |\beta_j|^2/\lambda_j^2}} \sum_j \frac{\beta_j}{\lambda_j} |u_j\rangle\)

Complexity: The algorithm achieves \(\mathcal{O}(\log(N) s^2 \kappa^2 / \epsilon)\) runtime, where \(s\) is the sparsity, \(\kappa\) is the condition number, and \(\epsilon\) is the desired precision.

Requirements: Efficient state preparation for \(|b\rangle\), well-conditioned matrix \(A\), and sparse Hamiltonian simulation for \(e^{iAt}\).

Classes

HHLLibrary(*args, **kwargs)

HHL library using base Phase Estimation implementation