HHL アルゴリズム

## この記事に関して
ここでは量子アルゴリズムの一つである、HHLアルゴリズムについて説明します。

### 連立一次方程式
一般的な連立方程式は以下のように置けます。

``` math
A{\bf x} = {\bf b}
```
$A$ は行列、${\bf x}, {\bf b}$ はそれぞれベクトルです。
$A$ が正則行列のとき求める解は次のようになります。

``` math
{\bf x} = A^{-1}{\bf b}
```
今回は $A＄ が正則なときを考えます。

#### 古典的解法
$A$ に関して

``` math
A' = \left(\begin{array}{cc}
0&A\\
A&0
\end{array}\right)
```
と置き直せばエルミート行列としても一般性は失われません。

$A$ は $n \times n$ のエルミート行列とします。
固有値、固有ベクトルをそれぞれ $\lambda_i, {\bf a}\_i$ とおくと、
エルミート行列の性質から $\lambda_i$ は実数となり、各 ${\bf a}\_i$ は直交します。

``` math
A = \sum_{i=0}^{n-1}\lambda_i {\bf a}_i {\bf a}^{\dagger}_i
```
$A$ は上のようにかけるので $A^{-1}$ は

``` math
A^{-1} = \sum_{i=0}^{n-1}\lambda^{-1}_i {\bf a}_i {\bf a}^{\dagger}_i
```
次に ${\bf b}$ は ${\bf a}\_i$ を使って以下のように表現できます。

``` math
{\bf b} = \sum_{i=0}^{n-1}\beta_i {\bf a}_i
```
以上から ${\bf x}$ は

``` math
{\bf x} = A^{-1}{\bf b} = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\lambda^{-1}_i \beta_j
{\bf a}_i {\bf a}^{\dagger}_i {\bf a}_j =
\sum_{i=0}^{n-1} \lambda^{-1}_i \beta_i {\bf a}_i \\
\left({\bf a}^{\dagger}_i {\bf a}_j = 
\left\{\begin{array}{c}
0 & (i \neq j) \\
1 & (i = j)
\end{array}\right.\right)
```
求められました。

### HHLアルゴリズム
上の内容をまとめると

1. $A$ の固有値、固有ベクトルを求める。
2. ${\bf b}$ を $A$ の固有ベクトルで展開する。
3. $\lambda_i$ で割って ${\bf x}$ を求める。

という流れになります。これを量子コンピュータで実装します。
このアルゴリズムを HHLアルゴリズムと言います。

#### 回路の作成

``` math
\begin{array}{lcccc}
\left|0\right>_S &-&-&-&-&-&Ry(\lambda^{-1})&-&-&-&-&-& \\
&&&&&&|&&&&\\
\left|0\right>^{\otimes n}_C &-&H^{\otimes n}&*&QFT^{-1}&-&*&-&QFT&*&H^{\otimes n}&- \\
&&&|&&&&&&|&\\
\left|{\bf b}\right>_I &-&-&U&-&-&-&-&-&U&-&\rightarrow&\left|{\bf x}\right> \\
\end{array}
```
どのビットかわかるように添え字をつけています。
この回路は3つの構成に分かれています。
1. QPE
2. CRy ゲート
3. QPEの逆演算

この流れを説明する前に下準備をします。
#### 正規化
各ベクトルを量子ビットで考えます。
まず量子状態として長さが $1$ のベクトルを考えないといけません。
$A$ の固有ベクトル ${\bf a}\_i$ は定数倍しても変わらないので以下のように置き直します。

``` math
\left|{\bf a}_i\right>_I := \frac{{\bf a}_i}{\|{\bf a}_i\|}
```

同様に ${\bf b}$ を以下のように変形します。

``` math
\left|{\bf b}\right>_I := \frac{{\bf b}}{\|{\bf b}\|} = 
\sum_{i=0}^{n-1}\frac{\beta_i}{\|{\bf b}\|}\left|{\bf a}_i\right>_I = 
\sum_{i=0}^{n-1}b_i\left|{\bf a}_i\right>_I \\
\left(b_i := \frac{\beta_i}{\|{\bf b}\|}\right)
```
長さを $1$ にできました。また $\left|{\bf x}\right>\_I := A^{-1}\left|{\bf b}\right>_I$ とします。

#### 1. QPE
$U = e^A$ とおくと $U\left|{\bf a}\_i\right>_I = e^{i\lambda}\left|{\bf a}\_i\right>\_I$ より

``` math
U\left|{\bf b}\right>_I = \sum_{i=0}^{n-1}e^{i \lambda_i} b_i \left|{\bf a}_i\right>_I
```
ここで $\left|{\bf a}\_i\right>_I$ に[QPE](https://qiita.com/KeiichiroHiga/items/acee41426809f3ad1257)を施すと

``` math
\left|0\right>^{\otimes n}_C \otimes \left|{\bf a}_i\right>_I \xrightarrow{QPE}
\left|\lambda_i\right>_C \otimes \left|{\bf a}_i\right>_I \\
\left(\lambda_i = 2\pi \times 0.\lambda_{i,0}\cdots \lambda_{i,n-1}\ ,\ 
\left|\lambda_i\right>_C = \left|\lambda_{i,0}\right> \otimes \cdots \otimes
\left|\lambda_{i,n-1}\right>\right)
```
ここで位相推定の性質から各 $\lambda_i$ は $0≦\lambda_i≦2\pi$ でないといけません。
従ってQPEを各 $\lambda_i$ で考えて

``` math
\left|0\right>^{\otimes n}_C \otimes \left|{\bf b}\right>_I = 
\sum_{i=0}^{n-1}b_i\left|0\right>^{\otimes n}_C \otimes \left|{\bf a}_i\right>_I \xrightarrow{QPE}
\sum_{i=0}^{n-1} b_i \left|\lambda_i\right>_C \otimes \left|{\bf a}_i\right>_I
```

#### 2. CRy ゲート
次に $CRy(\theta)$ ゲートを施します。このゲートは $\left|\lambda_i\right>$ の各量子ビットから始めのビットへそれぞれ作用させます。
従って、$n$ 個の $CRy(\theta)$ ゲートを作ることになります。

構成としては $i$ 番目の角度を $\theta_i$ とし

``` math
\cos(\theta_i) = \frac{1}{\lambda_i}
```
となるように置きます。
$i$ 番目に着目すると、

``` math
\left|0\right>_S \otimes \left|\lambda_i\right>_C \xrightarrow{CRy(\theta_i)}
(\cos(\theta_i)\left|0\right> + \sin(\theta_i)\left|1\right>)_S \otimes
\left|\lambda_i\right>_C \\
= \left( \frac{1}{\lambda_i} \left|0\right> +
\sqrt{1 - \frac{1}{\lambda^2_i}}\left|1\right>\right)_S \otimes \left|\lambda_i\right>_C
```
よって

``` math 
\sum_{i=0}^{n-1} b_i \left|0\right>_S \otimes \left|\lambda_i\right>_C \xrightarrow{CRy(\theta_i)} 
\sum_{i=0}^{n-1} b_i\left( \frac{1}{\lambda_i} \left|0\right> +
\sqrt{1 - \frac{1}{\lambda^2_i}}\left|1\right>\right)_S \otimes \left|\lambda_i\right>_C
```
この $CRy(\theta)$ ゲートは理論的には構成できますが、具体的な構成方法はわかっていません。

#### 3. QPEの逆演算
次に位相推定の逆演算を行います。

``` math
\xrightarrow{QPE^{-1}}\sum_{i=0}^{n-1} b_i\left( \frac{1}{\lambda_i} \left|0\right> +
\sqrt{1 - \frac{1}{\lambda^2_i}}\left|1\right>\right)_S \otimes \left|0\right>^{\otimes n} _C
\otimes \left|{\bf a}_i\right>_I
```
始めのビットが $\left|0\right>$ の場合、式を整理すると

``` math
\left|0\right>_S \otimes \left|0\right>^{\otimes n}_C
\otimes \sum_{i=0}^{n-1}\frac{b_i}{\lambda_i}\left|{\bf a}_i\right>_I
```
最後のビットが $\left|{\bf x}\right>_I$ になっていることが分かります。

よって ${\bf x} = \\|{\bf b}\\| \left|{\bf x}\right>_I$ から解が求められました。

## まとめ
今回は HHLアルゴリズムについて説明しました。

## 参考文献
連立一次方程式を量子コンピューターで解く - HHLアルゴリズム
https://whyitsso.net/physics/quantum_mechanics/HHL.html

7-2. Harrow-Hassidim-Lloyd (HHL) アルゴリズム
https://dojo.qulacs.org/ja/latest/notebooks/7.2_Harrow-Hassidim-Lloyd_algorithm.html

D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, L. Wossnig, "Quantum linear systems algorithms: a primer"
https://arxiv.org/pdf/1802.08227.pdf

量子位相推定(Quantum Phase Estimation)
https://qiita.com/KeiichiroHiga/items/acee41426809f3ad1257

blueqat で量子位相推定
https://qiita.com/KeiichiroHiga/items/1bd7fea4571fd91185c1