harrow_hassidim_lloyd#

Functionality#

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm [19] may demonstrate a quantum speedup over its classical counterpart for solving linear equations.

The problem is formed as follows: Given the linear equation $A\vec{x} = \vec{b}$, where $A$ is an $N \times N$ matrix. In the quantum circuit that will be performed $N=2^{n}$ where $n$ will be the number of qubits in the circuit. The restrictions on $A$ is that it has to be an $s$-sparse Hermitian matrix, meaning that $A$ has at most $s$ elements in each row/column.

`hhl.py`#

Callee HarrowHassidimLloyd

For this algorithm, we show the relation between registers and their indexes as follows:

Index	$0 \sim (n-1)$	$n \sim (2n-1)$	$2n \sim (2n+n_t-1)$	$2n+n_t$
Register	Input qubits (b-register)	Auxiliary qubits	Clock qubits for QPE	Objective qubit (a-register)

where $n$ is the number of qubits in the b-register, while $n_t$ is the number of qubits in the clock register.

The steps for the HHL algorithm are the following, with the state after each step:

Initialize two quantum registers and the ancilla qubit. The b-register register has $n$ data qubits initialized to $\ket{b}_n = \ket{b_{n-1}, b_{n-2}, \ldots, b_0}$, given $\vec{b} = [b_0, b_1, \ldots, b_{n-1}]^{\top}$. Therefore, the initial state inherently in the program is

\[ \ket{\psi_0} = \ket{0}_1 \otimes \ket{0}_{n_t} \otimes \ket{0}_{n} \otimes \ket{b}_n. \]
Apply the Hadamard gate to create an equal superposition of the clock qubits, creating an equal superposition state. Then, the state becomes

\[ \ket{\psi_1} = \ket{0}_1 \otimes \frac{1}{\sqrt{2^{n_t}}} \sum_{k=0}^{2^{n_t}-1} \ket{k}_{n_t} \otimes \ket{0}_{n} \otimes \ket{b}_n. \]
Apply controlled rotation portion of the QPE where $U=e^{iAt}$. Since $U$ is unitary, $U\ket{b}_n=e^{2\pi i \phi}\ket{b}_n$. After the controlled $U$ rotation,

\[\begin{split} \begin{aligned} \ket{\psi_2} & = \ket{0}_1 \otimes \frac{1}{\sqrt{2^{n_t}}} \sum_{k=0}^{2^{n_t}-1} \ket{k}_{n_t} \otimes \ket{0}_{n} \otimes U^k\ket{b}_n \\ & = \ket{0}_1 \otimes \frac{1}{\sqrt{2^{n_t}}} \sum_{k=0}^{2^{n_t}-1} e^{2\pi i k \phi} \ket{k}_{n_t} \otimes \ket{0}_{n} \otimes \ket{b}_n. \end{aligned} \end{split}\]
Apply the inverse QFT to the clock qubits to obtain an estimate of $\phi$ in the clock register. Let $\ket{b}_n$ be denoted as the supperposition of eigenvectors of $A$, i.e., $\ket{b}_n = \sum_j \beta_j \ket{u_j}_n$ where $\ket{u_j}$ is the eigenvector of $A$ with eigenvalue $\lambda_j$ (Here, $A^{-1}\ket{u_j}_n = \frac{1}{\lambda_j}\ket{u_j}_n$). After applying the inverse QFT, the state becomes

\[ \begin{aligned} \ket{\psi_3} = \ket{0}_1 \otimes \sum_{j=0}^{2^{n_b}-1} \beta_j \ket{\tilde{\phi}_j}_{n_t} \otimes \ket{0}_{n} \otimes \ket{u_j}_n, \end{aligned} \]

where, each $\ket{u_j}$ corresponds to an estimate of the eigenvalue $\tilde{\lambda}_j = 2\pi \tilde{\phi}_j / t$ with the eigenvector $\ket{\tilde{\phi}_j}$ stored in the clock register.
To achieve the inverse effect of matrix $A$, it is necessary to couple the ancilla qubit with the clock register and implement it through conditional rotation:

\[ R_y\left[\tilde{\lambda}_j\right]: \ket{0}_1 \mapsto \sqrt{1 - \frac{C^2}{\tilde{\lambda}_j^2}} \ket{0}_1 + \frac{C}{\tilde{\lambda}_j} \ket{1}_1. \]

where $C$ is a normalization constant, and is suggested to be $C \leq \min_j |\tilde{\lambda}_j|$ to ensure valid rotation angles. After this step, the state becomes

\[ \ket{\psi_4} = \sum_{j=0}^{2^{n}-1} \beta_j \left( \sqrt{1 - \frac{C^2}{\tilde{\lambda}_j^2}} \ket{0}_1 + \frac{C}{\tilde{\lambda}_j} \ket{1}_1 \right) \otimes \ket{\tilde{\phi}_j}_{n_t} \otimes \ket{0}_{n} \otimes \ket{u_j}_n. \]
Apply inverse QPE to disentangle the clock register from the b-register. The state becomes

\[ \ket{\psi_5} = \sum_{j=0}^{2^{n}-1} \beta_j \left( \sqrt{1 - \frac{C^2}{\tilde{\lambda}_j^2}} \ket{0}_1 + \frac{C}{\tilde{\lambda}_j} \ket{1}_1 \right) \otimes \ket{0}_{n_t} \otimes \ket{0}_{n} \otimes \ket{u_j}_n. \]
Measure the ancilla qubit. If the measurement result is 1, the b-register collapses to

\[ \ket{\psi_{6}'}_{n} = \frac{\sum_{j=0}^{2^{n}-1} \beta_j \frac{1}{\tilde{\lambda}_j} \ket{u_j}_n}{\sqrt{\sum_{j=0}^{2^{n}-1} \left| \beta_j \frac{1}{\tilde{\lambda}_j} \right|^2}}, \]

This state encodes the solution vector $\vec{x}$ to the linear equation $A\vec{x} = \vec{b}$. This is because $\ket{x}_n = A^{-1}\ket{b}_n = \sum_{j=0}^{2^n-1} \beta_j \frac{1}{\lambda_j} \ket{u_j}_n$. Note that the solution encoded by $\ket{\psi_{6}'}_{n}$ is an approximation due to the finite precision of the Quantum Phase Estimation step, i.e., $|\tilde{\lambda}_j - \lambda_j| > 0$ in general.

Notes:

Owing to b being an integer, the initial state $\ket{b}_n$ is a computational basis state and each element of $\vec{b}$ is either 0 or 1. Thus, the algorithm solves $A\vec{x} = \vec{b}$ where $\vec{b}$ is a basis vector.
Initialization of $\ket{b}_n$ has been done in the program.
The matrix $A$ must follow the constraints mentioned below:
- Hermitian check: $A = A^{\dagger}$
- Sparse check: $A$ is an $s$-sparse matrix (i.e., at most $s$ non-zero elements in each row/column, and $s < N$)
- Non-singular / minimal eigenvalue: $A$ is non-singular (i.e., all eigenvalues are non-zero)
Besides, as a soft constraint, we wish the condition number $\kappa$ of $A$ to be small to reduce the complexity of the algorithm.
For testing the HHL algorithm, quantum measurements should be performed on the b-register after measuring the ancilla qubit to obtain the solution vector $\vec{x}$, where the solution is valid only when the ancilla qubit measurement result is 1; otherwise, the solution should be discarded. Besides, post-processing is required to extract $\vec{x}$ from the measurement results.
Numerical Approximation

The HHL algorithm is inherently approximate when implemented with a finite number of clock qubits in Quantum Phase Estimation (QPE). Since the eigenvalues $\lambda_i$ of $A$ are represented with finite precision (determined by the number of clock qubits $n_t$), the algorithm effectively applies the transformation $\lambda_i^{-1} \rightarrow \tilde{\lambda}_i^{-1}$, where $\tilde{\lambda}_i$ is a discretized approximation of $\lambda_i$.

As a consequence:
- The output state is an approximation of the ideal normalized solution $\ket{x} \propto A^{-1}\ket{b}$.
- The fidelity between the quantum output and the exact classical solution is generally strictly less than 1, even in the absence of implementation errors.
- The approximation error scales as $O\!\left({\kappa}/{2^{n_t}}\right)$, where $\kappa$ is the condition number of $A$ and $n_t$ is the number of clock qubits.
- Therefore, fidelity thresholds used in testing should allow reasonable tolerance (e.g., 0.7–0.8 for small $n_t$).
Increasing $n_t$ improves precision but enlarges circuit depth and resource cost.

Test expectations:

The final quantum state reflects the solution to the linear equation, encoded in the amplitudes of the b-register, conditioned on a measurement of the ancilla qubit as 1. Then extract the probability distribution or state vector of the b-register, and compare it with the expectation solution $\ket{x}$.

Doc references: [20]

API#

qolumbina.programs.harrow_hassidim_lloyd.hhl#

HHL Benchmark Program - Qiskit

class HarrowHassidimLloyd(A, b, num_clock_qubits, C=0.25, if_barrier=False, name=None)[source]#

Bases: QuantumCircuit

Generate top-level circuit for HHL algorithm $A\vec{x} = \vec{b}$

Parameters:

A (ndarray) – The Hermitian matrix $A$ in the linear equation $A\vec{x} = \vec{b}$.
b (int) – The integer to initialize the b-register to the basis state $\ket{b}_n$.
num_clock_qubits (int) – The number of clock qubits $n_t$ used in the QPE.
C (float) – The normalization constant used in the controlled rotation step. Default is 1/4.
if_barrier (bool) – Whether to add barriers in the circuit.
name (str | None) – Optional name for the circuit.

Raises:

ValueError – If b is not between 0 and the dimension of A - 1.
ValueError – If C is not between 0 and 1.
ValueError – If A is not a valid input matrix (e.g., not Hermitian, not sparse, or singular).

IQFT(qreg)[source]#

inverse QFT

Parameters:: qreg (QuantumRegister) – QuantumRegister belonging to qc
Return type:: None

Note

This method does not include SWAP at end of the circuit

QFT()[source]#

Parameters:: qreg (QuantumRegister) – QuantumRegister belonging to qc
Return type:: None

Note

This method does not include SWAP at end of circuit

alpha2theta(alpha)[source]#

Parameters:

alpha (list[float]) – list of angles that get applied controlled on $0,...,2^n-1$
theta – list of angles occuring in circuit construction

Return type:

ndarray

conversion_matrix(N)[source]#

Compute the conversion matrix from alpha to theta

Parameters:: N (int)
Return type:: ndarray

ctrl_u(exponent)[source]#

Construct the U gates for A

Parameters:: exponent (int) – exponent of U
Return type:: tuple

ctrl_ui(exponent)[source]#

Construct the U^-1 gates for A

Parameters:: exponent (int) – exponent of U
Return type:: tuple

dot_product(str1, str2)[source]#

Compute the dot product between 2 binary strings

Parameters:

str1 (str)
str2 (str)

Return type:

int

initialize_state(qc, qreg, b)[source]#

Parameters:

b (int) – initial basis state $\ket{b}_n$ to prepare on qreg
qc (QuantumCircuit)
qreg (QuantumRegister)

Return type:

QuantumCircuit

inv_qft_gate(input_size, method=1)[source]#

Parameters:

input_size (int)
method (int)

Return type:

QuantumCircuit

inv_qpe(clock, target, extra_qubits, ancilla, A, method=1)[source]#

Append a series of Inverse Quantum Phase Estimation gates to the circuit

Parameters:

clock (QuantumRegister) – clock register qubits
target (QuantumRegister) – target register qubits
extra_qubits (QuantumRegister) – extra qubits for Hamiltonian simulation
ancilla (QuantumRegister) – ancilla qubit
A (ndarray) – sparse Hermitian matrix
method (int) – method for QFT implementation

qft_gate(input_size, method=1)[source]#

Parameters:

input_size (int)
method (int)

qpe(clock, target, extra_qubits, ancilla, A, method=1)[source]#

Parameters:

clock (QuantumRegister)
target (QuantumRegister)
extra_qubits (QuantumRegister)
ancilla (QuantumRegister)
A (ndarray)
method (int)

harrow_hassidim_lloyd

Contents

harrow_hassidim_lloyd#

Functionality#

hhl.py#

API#

qolumbina.programs.harrow_hassidim_lloyd.hhl#

`hhl.py`#