HHL Algorithm

2021 年 12 月 11 日
本文字数：7363 字
阅读完需：约 24 分钟

HHL Algorithm

HHL is the basis of many more advanced algorithms and is important in various applications such as machine learning and modelling of quantum systems.

1. Linear System Problem and Overview of HHL Algorithm

A linear system problem (LSP) can be represented as the following

A x = b

where $A$ is an $N_{b} \times N_{b}$ Hermitian matrix and $x$ and $b$ are $N_{b}$ -dimensional vectors. For simplicity, it is assumed $N_{b} = 2^{n_{b}} . A$ and $b$ are known and $x$ is the unknown to be solved, i.e.

x = A^{- 1} b

The figure below shows the schematic of the HHL algorithm and the corresponding circuit. The HHL algorithm has 5 main components, namely state preparation, quantum phase estimation (QPE), ancilla bit rotation, inverse quantum phase estimation (IQPE), and measurement.

Circuits

{:width="512px"}

The clock qubits are used to store the encoded eigenvalues of A and larger n results in higher accuracy when the encoding is not exact.

The matrix $A$ , which is a Hamiltonian, may be written as a linear combination of its eigenvectors, $∣ u_{i} ⟩$ weighted by its eigenvalues, $λ_{i}$ .

A = i = 0 \sum 2^{n_{b} - 1} λ_{i} ∣ u_{i} ⟩ ⟨ u_{i} ∣

Since $A$ is diagonal in its eigenvector basis, its inverse is simply, $A^{- 1} = \sum_{i = 0}^{2^{n} b - 1} λ_{i}^{- 1} ∣ u_{i} ⟩ ⟨ u_{i} ∣$ . $b$ can be also expressed in the basis of $A$ , such that

∣ b ⟩ = j = 0 \sum 2^{n} b - 1 b_{j} ∣ u_{j} ⟩

Therefore, it can be encoded as,

∣ x ⟩ = A^{- 1} ∣ b ⟩ = i = 0 \sum 2^{n_{b} - 1} λ_{i}^{- 1} b_{i} ∣ u_{i} ⟩

by using the fact that $⟨ u_{i} ∣ u_{j} ⟩ = δ_{i j}$ . The goal of the HHL algorithm is to find the solution in this form and $∣ x ⟩$ is stored in the b-register.

2. State Preparation

There are total $n_{b} + n + 1$ qubits and they are initialized as

∣ Ψ_{0} ⟩ = ∣ 0 \dots 0 ⟩_{b} ∣ 0 \dots 0 ⟩_{c} ∣ 0 ⟩_{a} = ∣ 0 ⟩^{\otimes n_{b}} ∣ 0 ⟩^{\otimes n} ∣ 0 ⟩

In the state preparation, $∣ 0 \dots 0 ⟩_{b}$ in the b-register needs to be rotated to have the amplitudes correspond to the coefficients of $b$ . That is

b = ⎝ ⎜ ⎜ ⎜ ⎛ β_{0} b e t a_{1} v d o t s b e t a_{N_{b} - 1} ⎠ ⎟ ⎟ ⎟ ⎞ \Leftrightarrow β_{0} ∣ 0 ⟩ + β_{1} ∣ 1 ⟩ + \dots + β_{N_{b} - 1} ∣ N_{b} - 1 ⟩ = ∣ b ⟩

The vector $b$ is represented in a column form on the left with coefficients $β^{'} s$ which is also a valid representation of $∣ b ⟩$ . On the right, the corresponding basis of the Hilbert space formed by the $n_{b}$ qubits is written explicitly. Therefore,

∣ Ψ_{1} ⟩ = ∣ b ⟩_{b} ∣ 0 \dots 0 ⟩_{c} ∣ 0 ⟩_{a}

From now on, some of the subscripts of the kets will be omitted when there is no ambiguity. Since the state preparation depends on the actual value of $b$ , it will be discussed in more detail in the numerical example.

3. Phase Estimation

Quantum phase estimation (QPE) is also an eigenvalue estimation algorithm. QPE has three components, namely the superposition of the clock qubits through Hadamard gates, controlled rotation, and Inverse Quantum Fourier Transform (IQFT). Here we assume the readers are already familiar with IQFT and it will not be explained in detail. In the first step where a superposition of the clock qubits is created, Hadamard gates are applied to the clock qubits to obtain,

∣ Ψ_{2} ⟩ = I^{\otimes n_{b}} \otimes H^{\otimes n} \otimes I ∣ Ψ_{1} ⟩ & = ∣ b ⟩ \frac{1}{2 ^{\frac{n}{2}}} (∣ 0 ⟩ + ∣ 1 ⟩)^{\otimes n} ∣ 0 ⟩

Circuit

In the controlled rotation part, $U$ is applied to $∣ b ⟩$ with the clock qubits as the control qubits (Figure 2). For simplicity, we begin by assuming that $∣ b ⟩$ is an eigenvector of $U$ with eigenvalue $e^{2 π i ϕ}$ . Therefore

U ∣ b ⟩ = e^{2 π i ϕ} ∣ b ⟩

When the control clock qubit is $∣ 0 ⟩, ∣ b ⟩$ will not be affected. If the clock bit is $∣ 1 ⟩, U$ will be applied to $∣ b ⟩$ . This is equivalent to multiplying $e^{2 π i ϕ 2^{i}}$ in front of the $∣ 1 ⟩$ of the $i - t h$ clock qubit. Therefore, after the controlled- $U$ operation, we have

∣ Ψ_{3} ⟩ = ∣ b ⟩ \otimes (\frac{1}{2 ^{\frac{n}{2}}} (∣ 0 ⟩ + e^{2 π i ϕ 2^{n - 1}} ∣ 1 ⟩) \otimes (∣ 0 ⟩ + e^{2 π i ϕ 2^{n - 2}} ∣ 1 ⟩) \otimes \dots \otimes (∣ 0 ⟩ + e^{2 π i ϕ 2^{0}} ∣ 1 ⟩)) \otimes ∣ 0 ⟩_{a} & = ∣ b ⟩ \frac{1}{2 ^{\frac{n}{2}}} k = 0 \sum 2^{n} - 1 e^{2 π i ϕ k} ∣ k ⟩ ∣ 0 ⟩_{a}

In the IQFT part, only the clock qubits are affected. Note that in certain literature, this is called Quantum Fourier Transform (QFT).

∣ Ψ_{4} ⟩ = ∣ b ⟩ I Q F T (\frac{1}{2 ^{\frac{n}{2}}} k = 0 \sum 2^{n} - 1 e^{2 π i ϕ k} ∣ k ⟩) ∣ 0 ⟩_{a} & = ∣ b ⟩ \frac{1}{2 ^{\frac{n}{2}}} k = 0 \sum 2^{n} - 1 e^{2 π i ϕ k} (I Q F T ∣ k ⟩) ∣ 0 ⟩_{a} & = ∣ b ⟩ \frac{1}{2 ^{n}} k = 0 \sum 2^{n} - 1 e^{2 π i ϕ k} (y = 0 \sum 2^{n} - 1 e^{- 2 π i y k / N} ∣ y ⟩) ∣ 0 ⟩_{a} & = \frac{1}{2 ^{n}} ∣ b ⟩ y = 0 \sum 2^{n} - 1 k = 0 \sum 2^{n} - 1 e^{2 π i k (ϕ - y / N)} ∣ y ⟩ ∣ 0 ⟩_{a}

Due to interference, only for $∣ y ⟩$ satisfying the condition $ϕ - y / N = 0$ will have a finite amplitude of $\sum_{k = 0}^{2^{n} - 1} e^{0} = 2^{n}$ . Otherwise, the amplitude is $\sum_{k = 0}^{2^{n} - 1} e^{2 π i k (ϕ - y / N)} = 0$ due to destructive interference. By ignoring the states with zero amplitude, we may rewrite $∣ Ψ_{4} ⟩$ as

∣ Ψ_{4} ⟩ = ∣ b ⟩ ∣ N ϕ ⟩ ∣ 0 ⟩_{a}

Therefore, in QPE, the clock qubits are used to represent the phase information of $U$ , which is $ϕ$ , and the accuracy depends on the number of qubits, $n$ .In Hamiltonian encoding, $U$ is related to $A$ through

U = e^{i A t}

where $t$ is the evolution time for that Hamiltonian. $U$ is obviously also diagonal in $A^{'} s$ eigenvector, $∣ u_{i} ⟩$ , basis. If $∣ b ⟩ = ∣ u_{j} ⟩$ ,

U ∣ b ⟩ = e^{i λ_{j} t} ∣ u_{j} ⟩

By equating $i λ_{j} t$ to $2 π i ϕ$ in Eq. (11), we get $ϕ = λ_{j} t / 2 π$ and Eq. (14) becomes

∣ Ψ_{4} ⟩ = ∣ u_{j} ⟩ ∣ N λ_{j} t / 2 π ⟩ ∣ 0 ⟩_{a}

Thus the eigenvalues of $A$ have been encoded in the clock qubits (basis encoding). However, in general, $∣ b ⟩ = \sum_{j = 0}^{2^{n} b - 1} b_{j} ∣ u_{j} ⟩$ (Eq. 4), by using superposition,

∣ Ψ_{4} ⟩ = j = 0 \sum 2^{n_{b} - 1} b_{j} ∣ u_{j} ⟩ ∣ N λ_{j} t / 2 π ⟩ ∣ 0 ⟩_{a}

$λ_{j}$ are usually not integers. We will choose $t$ so that $\tilde{λ} j = N λ j t / 2 π$ are integers. Therefore, the encoded values

$\tilde{λ} j$ can be different from $λ j .$

can be rewritten as

∣ Ψ_{4} ⟩ = j = 0 \sum 2^{n_{b} - 1} b_{j} ∣ u_{j} ⟩ ∣ ∣ ∣ ∣ \tilde{λ} j ⟩ ∣ 0 ⟩ a

4. Controlled Rotation and Measurement of the Ancilla Qubit

The next step is to rotate the ancilla qubit, $∣ 0 ⟩_{a}$ , based on the encoded eigenvalues in the c-register, such that

∣ Ψ_{5} ⟩ = j = 0 \sum 2^{n_{b} - 1} b_{j} ∣ u_{j} ⟩ ∣ ∣ ∣ ∣ \tilde{λ_{j}} ⟩ (1 - \frac{C ^{2}}{λ _{j} ~ ^{2}} ∣ 0 ⟩_{a} + \frac{C}{λ _{j} ~} ∣ 1 ⟩_{a})

where $C$ is a constant. When the ancilla qubit is measured, the ancilla qubit wavefunction will collapse to either $∣ 0 ⟩$ or $∣ 1 ⟩$ . If it is $∣ 0 ⟩$ , the result will be discarded and the computation will be repeated until the measurement is $∣ 1 ⟩$ . Therefore, the final wavefunction of interest is

∣ Ψ_{6} ⟩ = \frac{1}{\sum _{j = 0}^{2^{n} b - 1} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} j = 0 \sum 2^{n} b - 1 b_{j} ∣ u_{j} ⟩ ∣ ∣ ∣ ∣ \tilde{λ} j ⟩ \frac{C}{λ j ~} ∣ 1 ⟩_{a}

where the prefactor is due to normalization after measurement. Since $∣ ∣ ∣ ∣ \frac{C}{λ _{j}} ∣ ∣ ∣ ∣^{2}$ is the probability of obtaining $∣ 1 ⟩$ when the ancilla bit is measured, $C$ should be chosen to be as large as possible. Compared to Eq. (5), the result resembles the answer $∣ x ⟩$ that we are looking for. However, it is entangled with the clock qubits, $∣ ∣ ∣ ∣ \tilde{λ}_{j} ⟩$ . This means that we cannot factorize the result into a tensor product of the c-register and b-register. Therefore, we need to uncompute the state to unentangle them.

The measurement can be and is usually performed after uncomputation. However, since the ancilla bit is not involved in any operations after the controlled rotation, measuring the ancilla bit before the uncomputation gives the same result. For simplicity in the derivation, it is thus performed before the uncomputation.

5. Uncomputation - Inverse QPE

Firstly, QFT is applied to the clock qubits.

$$\left\vert \Psi_{7}\right\rangle=\frac{1}{\sqrt{\sum_{j=0}^{2^{n_{-}-1}}\left\vert \frac{b_{\frac{b}{\lambda}} C_{1}}{\lambda_{1}}\right\vert ^{2}}} \sum_{j=0}^{2 m_{b}-1} \frac{b_{j} C}{\hat{\lambda}{j}}\left\vert u{j}\right\rangle Q F T\left\vert \hat{\lambda_{j}}\right\rangle\vert 1\rangle_{a}$$

Then inverse controlled-rotations of the b-register by the clock qubits are applied with $U^{- 1} = e^{- i A t}$ . Similar to the forward process, when the control clock qubit is $∣ 0 ⟩, ∣ u_{j} ⟩$ will not be affected. If the clock bit is $∣ 1 ⟩, U^{- 1}$ will be applied to $∣ u_{j} ⟩$ . This is equivalent to multiplying $e^{- i λ_{j} t}$ in front of the $∣ 1 ⟩$ of the $i - t h$ clock bit. Therefore,

∣ Ψ_{8} ⟩ = \frac{1}{2 ^{n / 2} \sum _{j - 0}^{2 n - 1} ∣ ∣ ∣ ∣ \frac{b _{2} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} j = 0 \sum 2^{n b - 1} \frac{b _{j} C}{λ _{j}} ∣ u_{j} ⟩ (e^{- i λ_{j} t} j = 0 \sum 2^{n} - 1 e^{2 π i y λ_{j} / N} ∣ y ⟩) ∣ 1 ⟩_{a}

Since we have set$$\bar{\lambda}{j}=N \lambda{j} t / 2 \pi$$, therefore, the two exponential terms cancel each other and

∣ Ψ_{s} ⟩ = \frac{1}{2 ^{n / 2} \sum _{j = 0}^{2^{n - 1}} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} j = 0 \sum 2^{n_{0} - 1} \frac{b _{j} C}{λ _{j}} ∣ u_{j} ⟩ y = 0 \sum 2^{n} - 1 ∣ y ⟩ ∣ 1 ⟩_{a} & = \frac{1}{2 ^{n / 2} \frac{N t}{2 x} \sum _{j = 0}^{2 n_{b} - 1} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} j = 0 \sum 2^{n_{3} - 1} \frac{b _{j} C}{λ _{j}} ∣ u_{j} ⟩ j = 0 \sum 2^{n} - 1 ∣ y ⟩ ∣ 1 ⟩_{a} & = \frac{C}{2 ^{n / 2} \sum _{j - 0}^{2^{n b} - 1} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} ∣ x ⟩ y = 0 \sum 2^{n} - 1 ∣ y ⟩ ∣ 1 ⟩_{a}

The clock qubits and the b-register are now unentangled and the b-register stores $∣ x ⟩$ . By applying the Hadamard gate on the clock qubits, finally, we have

∣ Ψ_{9} ⟩ = \frac{1}{\sum _{j = 0}^{2^{n} b - 1} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} j = 0 \sum 2^{m b} - 1 \frac{b _{j} C}{λ _{j}} ∣ u_{j} ⟩ ∣ 0 ⟩^{β n} ∣ 1 ⟩_{a} & = \frac{1}{\sum _{j = 0}^{2^{2 n} - 1} ∣ ∣ ∣ ∣ \frac{b _{j} C}{λ _{j}} ∣ ∣ ∣ ∣ ^{2}} ∣ x ⟩_{b} ∣ 0 ⟩_{c}^{β n} ∣ 1 ⟩_{a}

6. Example

For example, take $N = 2$ ,

A = (1 - 1 / 3 - 1 / 3 1), x = (x_{1} x_{2}) and b = (10)

Then the problem can also be written as find $x_{1}, x_{2} \in C$ such that

x_{1} - \frac{x _{2}}{3} = 1 - \frac{x _{1}}{3} + x_{2} = 0

The eigenvectors of A are, respectively,

∣ u_{1} ⟩ = (1 - 1) and ∣ u_{2} ⟩ = (11)

The eigenvalues of them are,

λ_{1} = 2 / 3 and λ_{2} = 4 / 3

2 qubits are needed by encoding $λ_{1}$ and $λ_{2}$ as $∣ 01 ⟩$ $∣ 10 ⟩$ so that it maintains the ratio of e1/e0 = 2

it maintains the ratio of $e_{1} / e_{0} = 2 .$ This means $\tilde{λ}_{0} = 1$ $a n d$ $\tilde{λ}_{1} = 2$ or in other words,

∣ ∣ ∣ ∣ \tilde{λ_{0}} ⟩ = ∣ 01 ⟩

∣ ∣ ∣ ∣ \tilde{λ_{1}} ⟩ = ∣ 10 ⟩

to achieve the encoding scheme since $\tilde{λ} j = N λ j t / 2 π$ .

On outcome 1 when measuring the auxiliary qubit, the state is

\frac{\frac{1}{2} ∣ 0 0 ⟩ ∣ u _{1} ⟩ \frac{1}{2} ∣ 1 ⟩ + \frac{1}{2} ∣ 0 0 ⟩ ∣ u _{2} ⟩ \frac{1}{4} ∣ 1 ⟩}{5 / 3 2}

A quick calculation shows that

\frac{\frac{1}{2 2} ∣ u _{1} ⟩ + \frac{1}{4 2} ∣ u _{2} ⟩}{5 / 3 2} = \frac{∣ x ⟩}{∣ ∣ x ∣ ∣}

Since $b$ is a 2-dimensional complex vector, it can be encoded using 1 qubit and, thus, $n_{b} = 1$ .

We can use $∣ u_{1} ⟩$ and $∣ u_{2} ⟩$ to find what is x.

The solution to the LSP is found to be

x = (\frac{3}{8} \frac{9}{8})

whereby, the ratio of

∣ x_{0} ∣^{2} to ∣ x_{1} ∣^{2} is 1 : 9

Reference:

1. Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information." (2002): 558-559.

2. Asfaw, Abraham, et al. "Learn quantum computation using qiskit." Accessed: Oct 24 (2020): 2020.

3. Susskind, Leonard, and Art Friedman. Quantum mechanics: the theoretical minimum. Basic Books, 2014.

4. Morrell Jr, Hector Jose, and Hiu Yung Wong. "Step-by-Step HHL Algorithm Walkthrough to Enhance the Understanding of Critical Quantum Computing Concepts." arXiv preprint arXiv:2108.09004 (2021).

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/bcaae7aa34f47e574efc90c7e】。未经作者许可，禁止转载。

Si Yuan

关注

还未添加个人签名 2021.11.13 加入

华南理工大学专业第一毕业生 | 国家奖学金 | 雅思7.5 | Global CBDC Challenge Finalist | Quantum Computing Research

发布

暂无评论

创作场景