HHL Algorithm

   

Overview

Objective of the HHL algorithm: Given a Hermitian matrix $A$ and a unit vector $\overrightarrow{b}$, the goal is to solve the equation $A\overrightarrow{x}=\overrightarrow{b}$.

Let $|b⟩=\sum _{j=1}^N{b}_j|j⟩$, where $|j⟩$ represents the basis states. The key of the algorithm lies in simulating $e^{iA\mathrm{\Delta }t}$ on $|b⟩$.

Assume the spectral decomposition of $A$ is as follows:

$$A=\sum _{j=1}^N{\lambda }_j|u_j⟩⟨u_j|$$

Then,

$$e^{iA\mathrm{\Delta }t}=\sum _{j=1}^N{e}^{i{\lambda }_j\mathrm{\Delta }t}|u_j⟩⟨u_j|$$

Express $|b⟩$ in terms of the basis $\left\{|u_j⟩\right\}$: $|b⟩=\sum _{j=1}^N{\beta }_j|u_j⟩$.

Using Quantum Phase Estimation (QPE), where $U=e^{iA\mathrm{\Delta }t}$, the resulting transformation is as follows:

$$|b⟩\stackrel{\text{QPE}}{\to }\sum _{j=1}^N{\beta }_j|u_j⟩|\widetilde{{\lambda }_j}⟩$$

Here, $|\widetilde{{\lambda }_j}⟩$ is the estimation of the eigenvalue ${\lambda }_j$ (the tilde represents an estimation, the same applies in the following).

It is easy to see that the solution to the equation is:

$$|x⟩=A^{-1}|b⟩=\sum _j{\beta }_j({\lambda }_j{)}^{-1}|u_j⟩$$

Therefore, we only need to extract the information from the quantum state $|\widetilde{{\lambda }_j}⟩$.

Steps of the HHL Algorithm

Below, we provide a detailed explanation of the steps involved in the HHL algorithm, including the mathematical derivations.

Data Preprocessing

As mentioned earlier, $A$ needs to be Hermitian, i.e., $A^{†}=A$. However, this condition can be relaxed. If $A$ is not Hermitian, we can construct $\tilde{A}$ as follows:

$$\begin{array}{r}\tilde{A}=\left(\begin{array}{cc}0& A\\ A^{†}& 0\end{array}\right)\end{array}$$

Then, we solve the equation:

$$\begin{array}{r}\tilde{A}\overrightarrow{y}=\left(\begin{array}{c}\overrightarrow{b}\\ 0\end{array}\right)\end{array}$$

It can be easily verified that the solution to this equation, $\overrightarrow{y}$, has the following form:

$$\begin{array}{r}\overrightarrow{y}=\left(\begin{array}{c}0\\ \overrightarrow{x}\end{array}\right)\end{array}$$

where $A\overrightarrow{x}=\overrightarrow{b}$.

For $\overrightarrow{b}$, since HHL is a quantum algorithm, the input should be a quantum state $|b⟩=\sum _{j=1}^N{b}_j|j⟩$. The details of how to prepare such a quantum state and encode classical information into quantum information are beyond the scope of this algorithm. Here, we assume that the quantum state has been prepared accordingly.

Preparation of Operator $U=e^{iA\mathrm{\Delta }t}$

The efficient preparation of the operator $U=e^{iA\mathrm{\Delta }t}$ is a core problem. As we will see later, the complexity of the entire HHL algorithm mainly depends on the operator $U$, so it is necessary to efficiently simulate $U$.

The preparation of this time evolution operator $U=e^{iA\mathrm{\Delta }t}$ belongs to the problem of quantum system simulation (Hamiltonian simulation), which is an important quantum problem that will not be discussed in detail here.

In the original paper, a sparsity constraint was imposed on the matrix $A$ in order to efficiently simulate $e^{iA\mathrm{\Delta }t}$. For general dense matrices $A$, simulating their evolution can be computationally expensive.

Here, we won’t go into the proof of the correctness of QPE. Readers only need to know that the input of QPE is a unitary operator $U$ and its eigenvector $|u⟩$, and the output is an estimate $\tilde{\phi }$ of the phase $\phi$ such that $U|u⟩=e^{2\pi i\phi }|u⟩$.

Specifically, using $t$ auxiliary qubits, the action of QPE is as follows:

$$|b⟩{|0⟩}^{\otimes t}|0⟩=\sum _{j=1}^N{\beta }_j|u_j⟩{|0⟩}^{\otimes t}|0⟩\stackrel{\text{QPE}}{\to }\sum _{j=1}^N{\beta }_j|u_j⟩|\widetilde{{\phi }_j}⟩|0⟩$$

Here, $|\widetilde{{\phi }_j}⟩$ is the estimate of the phase ${\phi }_j$. An additional auxiliary qubit is added after the $t$ auxiliary qubits for the subsequent rotation step.

To better understand, let’s take an example: Take

$$A=Z=|0⟩⟨0|-|1⟩⟨1|$$

Then

$$U=e^{iA\mathrm{\Delta }t}=e^{i\mathrm{\Delta }t}|0⟩⟨0|+e^{-i\mathrm{\Delta }t}|1⟩⟨1|$$

The two phases are ${\phi }_1=\mathrm{\Delta }t/2\pi$ and ${\phi }_2=-\mathrm{\Delta }t/2\pi$.

If we use $t=4$ auxiliary qubits and take $\mathrm{\Delta }t=\pi /4$, then ${\phi }_1=1/8$ and ${\phi }_2=-1/8$.

The estimated values of the two phases are $\widetilde{{\phi }_1}=0.0010\times 2^4=2$ and $\widetilde{{\phi }_2}=0.1110\times 2^4=14$. Since the phase is a decimal between $[0,1)$, multiplying it by $2^t$ gives its corresponding quantum state $|q_{t_1}\dots q_{t_t}⟩$. It should be noted that because the phase is a decimal modulo $1$, $-0.0010$ is mapped to $0.1110$. To restore the phase (to restore $\lambda$), we first select a small enough $\mathrm{\Delta }t$ such that $|\phi |<1/2$. This way, if $|q_{t_1}\dots q_{t_t}⟩<2^{t-1}$ corresponds to a positive number, $|q_{t_1}\dots q_{t_t}⟩>2^{t-1}$ corresponds to a negative number.

Through simple quantitative calculations, we obtain the following mapping relationship:

$$\begin{array}{r}\frac{\lambda \mathrm{\Delta }t}{2\pi }=\phi =\{\begin{array}{lll}\tilde{\phi }/2^t& ,\phi >0& ,\tilde{\phi }<2^{t-1}\\ \tilde{\phi }/2^t-1& ,\phi <0& ,\tilde{\phi }>2^{t-1}\end{array}\end{array}$$

Here, $\lambda$ is the eigenvalue of $A$, $\phi$ is the phase of $U=e^{iA\mathrm{\Delta }t}$, and $\tilde{\phi }$ is the estimate of $\phi$.

Conditional Rotation

After QPE, the overall quantum state is as follows:

$$\sum _{j=1}^N{\beta }_j|u_j⟩|\widetilde{{\phi }_j}⟩|0⟩$$

To extract the information of ${\lambda }_j$ from the quantum state $|\widetilde{{\phi }_j}⟩$, we need to use conditional rotation gates $CR(k)$, which have the following effect:

$$\begin{array}{r}CR(k)|\tilde{\phi }⟩|b⟩=\{\begin{array}{ll}|\tilde{\phi }⟩|b⟩& ,k\ne \tilde{\phi }\\ |\tilde{\phi }⟩R_y(2\arcsin \frac{C}{\lambda })|b⟩& ,k=\tilde{\phi }\end{array}\end{array}$$

In simple terms, the rotation operation is only applied to the subsequent qubits when $k$ selects the correct $\tilde{\phi }$.

Since we don’t know the correct $\tilde{\phi }$, we brute force all possible $CR(k)$, where $k=1,\dots ,2^t-1$.

The effect of the rotation is straightforward:

$$\prod _{k=1}^{2^t-1}I\otimes CR(k)\sum _{j=1}^N{\beta }_j|u_j⟩|\widetilde{{\phi }_j}⟩|0⟩=\sum _{j=1}^N{\beta }_j|u_j⟩|\widetilde{{\phi }_j}⟩(\sqrt{1-{\left(\frac{C}{{\lambda }_j}\right)}^2}|0⟩+\frac{C}{{\lambda }_j}|1⟩)$$

After applying inverse QPE once again, the overall quantum state is as follows:

$$|\psi ⟩=\sum _{j=1}^N{\beta }_j|u_j⟩{|0⟩}^{\otimes t}(\sqrt{1-{\left(\frac{C}{{\lambda }_j}\right)}^2}|0⟩+\frac{C}{{\lambda }_j}|1⟩)$$

Measurement

Measure the last qubit. When the measurement result is $|1⟩$, the probability is

$$p_1=C^2\sum _{j=1}^N({\beta }_j/{\lambda }_j{)}^2$$

After the measurement, the quantum state becomes

$$|{\psi }_1⟩=\frac{1}{{\left(\sum _{j=1}^N{\left({\beta }_j/{\lambda }_j\right)}^2\right)}^{-1}}\sum _{j=1}^N\frac{{\beta }_j}{{\lambda }_j}|u_j⟩{|0⟩}^{\otimes t}|1⟩$$

Clearly, there is no entanglement between the three quantum registers at this point. If we only look at the first quantum register, it is already in the state $|x⟩$ (ignoring a normalization factor).

It should be noted that there is a parameter $C$ in the rotation operation. We see that $C$ does not affect the correctness of the final result, but it does affect the probability $p_1$ of obtaining the result. We certainly hope that $C$ can be as large as possible, so that $p_1$ can be maximized. However, $C\le \left|{\lambda }_j\right|$, it is smaller than the absolute value of all eigenvalues. If there is no prior information about the smallest absolute value of $\lambda$, we can only conservatively choose a very small $C$ and then use amplitude amplification techniques to increase the probability of obtaining the result.

Implementation with MindQuantum

Here, we use MindQuantum to implement a simple example to illustrate the process and correctness of the HHL algorithm.

For convenience, we choose a simple matrix $A=Z=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$, because its time evolution operator $e^{iZ\mathrm{\Delta }t}=R_z(-2\mathrm{\Delta }t)$ is relatively easy to implement.

import numpy as np

A = np.array([[1, 0], [0, -1]])
es, vs = np.linalg.eig(A)

print(f"eigenvalues of A:\n {es}")
print(f"eigenvectors of A:\n {vs}")

b = np.array([0.6, 0.8])
print(f"b: {b}")
print(f"Solution of Ax=b is: {np.linalg.solve(A, b)}")

eigenvalues of A:
 [ 1. -1.]
eigenvectors of A:
 [[1. 0.]
 [0. 1.]]
b: [0.6 0.8]
Solution of Ax=b is: [ 0.6 -0.8]

Here, we import various required functions:

from mindquantum.core.gates import H, X, RY, RZ, Measure, Power, BARRIER
from mindquantum.core.circuit import Circuit
from mindquantum.simulator import Simulator

For the preparation of the quantum state $|b⟩=\cos \theta |0⟩+\sin \theta |1⟩$, it can be achieved using an $R_y(2\theta )$ gate.

The following code prepares the state $|b⟩=0.6|0⟩+0.8|1⟩$ and performs a measurement.

circ = Circuit()
circ += RY(2 * np.arcsin(0.8)).on(0)
circ += Measure().on(0)

sim = Simulator(backend="mqvector", n_qubits=1)
res = sim.sampling(circ, shots=10000)
res.svg()

The following is the step-by-step construction of the complete quantum circuit, with $t=4$, $\mathrm{\Delta }t=\pi /4$, and $C=0.5$.

• First is QPE.

• Then comes $CR(k)$, $k=1,\dots ,15$.

• Next is inverse QPE.

• Finally, measurement is performed.

from mindquantum.algorithm.library import qft

# q1 ~ q4 : for QPE
t = 4
qc = [4, 3, 2, 1]

# store |b> , and store the result |x>
qb = 5

# use for conditional rotation
qs = 0

# choose a time evolution
dt = np.pi / 4

# choose a small C
C = 0.5

circ = Circuit()

# prepare b
circ += RY(2 * np.arcsin(0.8)).on(qb)

# QPE
for i in qc:
    circ += H.on(i)

for (i, q) in enumerate(qc):
    circ += Power(RZ(-2 * dt), 2**i).on(qb, q)

# apply inverse QFT
circ += qft(list(reversed(qc))).hermitian()

# conditional rotate
circ += BARRIER
for k in range(1, 2**t):
    for i in range(t):
        if (k & (1 << i)) == 0:
            circ += X.on(qc[i])
    phi = k / (2**t)
    if k > 2**(t-1):
        phi -= 1.0
    l = 2 * np.pi / dt * phi
    circ += RY(2 * np.arcsin(C / l)).on(qs, qc)

    for i in range(t):
        if (k & (1 << i)) == 0:
            circ += X.on(qc[i])
    circ += BARRIER

# apply inverse QPE
circ += qft(list(reversed(qc)))

for (i, q) in enumerate(qc):
    circ += Power(RZ(2 * dt), 2**i).on(qb, q)

for i in qc:
    circ += H.on(i)

circ.svg()

How do we verify the correctness of our results? Through measurement. Since the result is a quantum state $|x⟩$, currently MindQuantum does not have a method to directly extract the internal values of a specific qubit. Therefore, we can only obtain information about the state through measurement.

sim = Simulator(backend="mqvector", n_qubits=2 + t)
sim.apply_circuit(circ)

circ_m = Circuit()
circ_m += Measure().on(qs)
circ_m += Measure().on(qb)

res = sim.sampling(circ_m, shots=100000)
res.svg()

res.data.get("01", 0) / (res.data.get("01", 0) + res.data.get("11", 0))

0.3612780010344965

By statistically analyzing the measurement results of q5 when q0 is 1, we observe that the proportion of q5 = 0 is 0.36, which is consistent with the expected answer.

However, this method only provides information about the magnitude of the amplitudes. To obtain more information, such as phase, adjustments to the measurement would be required, but we won’t discuss that here.

from mindquantum.utils.show_info import InfoTable

InfoTable('mindquantum', 'scipy', 'numpy')

Software	Version
mindquantum	0.9.11
scipy	1.10.1
numpy	1.23.5
System	Info
Python	3.9.16
OS	Linux x86_64
Memory	8.3 GB
CPU Max Thread	8
Date	Sat Dec 30 23:19:52 2023