Qiskit HHL Solver for Linear Systems

This sitory contains a functional quantum computing implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm using Qiskit to solve linear systems of equations of the form:

$$A \vec{x} = \vec{b}$$

Our implementation extends the standard HHL algorithm by automatically supporting non-power-of-two matrix dimensions (via intelligent zero-padding) and non-Hermitian matrices (using the normal equations transformation $A^\dagger A \vec{x} = A^\dagger \vec{b}$).

---

Algorithm Pipeline

The HHL algorithm solves linear systems by encoding the solution vector in the amplitudes of a quantum register. The pipeline implemented follows these key stages:

1. State Preparation ($b$-register encoding): Encodes the normalized vector $\vec{b}$ into the amplitudes of the $b$-register using Qiskit's StatePreparation component.
2. Quantum Phase Estimation (QPE): Estimates the eigenvalues of the matrix $A$ (or the transformed Hermitian matrix) into a dedicated precision register ($c$-register).
   • Hadamard gates create a uniform superposition in the $c$-register.
   • Controlled Hamiltonian evolution steps ($e^{-i A t}$) are synthesized using a Trotter-Suzuki product formula (specifically SuzukiTrotter order 1).
   • An Inverse Quantum Fourier Transform ($QFT^\dagger$) translates the phase information into binary eigenvalue representations.
3. Controlled Reciprocal Rotation: Applies a controlled rotation onto an auxiliary (ancilla) register qubit using an ExactReciprocalGate. The rotation angle is proportional to $\arcsin(s/\lambda)$, where $\lambda$ represents the estimated eigenvalues and $s$ is a scaling factor to guarantee valid rotation bounds.
4. Inverse Quantum Phase Estimation (Uncomputation): Reverses the QPE steps (QFT and controlled evolution) to uncompute the eigenvalue registers, leaving the $c$-register clean at $|0\rangle$ and disentangled from the $b$-register.
5. Measurement & Post-selection: Measures the system. Conditioned on measuring the auxiliary qubit in the $|1\rangle$ state, the $b$-register collapses into the solution ket $|\x\rangle$.

---

Repository Structure

• hhl.py: The core implementation containing the HHLCircuit class. It manages the construction of the quantum registers, circuit operations, Trotter evolution scaling, and contains a default 2x2 example run.
• tests.py: A comprehensive test suite containing 11 validation scenarios. It tests matrices of various dimensions (up to 16x16), dense/sparse patterns, non-Hermitian systems, and checks the Total Variation Distance (TVD) between the quantum simulator outputs and classical numpy results.
• requirements.txt: Python package dependencies.

---

Setup Instructions

Prerequisites

• Python 3.8 or higher is recommended.

---

Running the Project

Execute the Demo Circuit

Ensure pip is updated, then install the required packages:

pip install --upgrade pip
pip install -r requirements.txt

Then you can run the main script to build, draw, and simulate the default HHL system:

python hhl.py

This runs the solver for a small example. And outputs a textual circuit diagram along with a side-by-side comparison of the quantum simulation counts vs. the classical analytical solution.

Run the Test Suite

The automated test suite runs 11 different linear systems and validates the correctness by computing the Total Variation Distance (TVD) against classical results.

python tests.py

The test cases verify:

1. 2x2 Diagonal Matrix (eigenvalues 1.0, 2.0)
2. 2x2 Off-Diagonal Matrix (eigenvalues 1.0, 2.0)
3. 4x4 Diagonal Matrix (eigenvalues 1.0, 2.0, 3.0, 4.0)
4. 4x4 Off-Diagonal Matrix (symmetric matrix using Householder reflection)
5. 8x8 Diagonal Matrix (eigenvalues 1.0 to 8.0)
6. 16x16 Sparse Block-Diagonal Matrix
7. 16x16 Dense Matrix
8. 3x3 Diagonal Matrix (requires padding to 4x4)
9. 5x5 Off-Diagonal Matrix (requires padding to 8x8)
10. 2x2 Non-Hermitian Matrix (transformed via normal equations)
11. 5x5 Non-Hermitian Matrix (requires normal equations transformation and padding to 8x8)

A test is flagged as SUCCESS if the TVD is within the 5% threshold (0.05) to account for QPE approximation errors and finite shots.

License

This project is available under the MIT license

Authors

The authors of this project are Salvatore Biamonte and Davide Pirrò