VQE algorithm (Variational Quantum Eigensolver)

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

## 勾配法
VQE に必要な勾配法をまず説明します。
勾配法は関数の傾きによって最大・最小問題を解くアルゴリズムのことです。

例えば $y=x^2$ について
![img_y=x2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/517405/b339289a-6c59-178d-4d5f-8e749be4d45e.png)
x = 0 で最小値を取りますがこれは傾き y' = 0 の点でもあります。
この x を勾配法によって求めます。

まずは適当に x を取りその点の傾きを考えます。
傾きが正ならば x を小さくして、負なら x を大きくしていきます。

これを繰り返していくと 0 に近づいていくことがわかります。
このような傾きを使うアルゴリズムを勾配法特に今回は最急降下法といいます。

## VQE
このアルゴリズムはエルミート行列の最小・最大固有値を量子コンピュータと古典コンピュータの両方を用いて近似解を求めるアルゴリズムです。

ユニタリ行列の固有値を求める量子位相推定は[こちら](https://qiita.com/KeiichiroHiga/items/acee41426809f3ad1257)に説明しています。

### 量子変分原理
VQEを使う上で重要な量子変分原理を証明します。
エルミート行列を $H$ とします。(ハミルトニアン)
エルミート行列の固有値は実数となるのでその最小値を $E_0$ と置き、
その固有ベクトルを $\left|\psi_0\right>$ とすると

``` math
H\left|\psi_0\right> = E_0\left|\psi_0\right>
```
が成り立ちます。

量子変分原理とは任意の状態を $\left|\psi\right>$ とすれば

``` math
\left<\psi\right|H\left|\psi\right> ≧ E_0 
```
が成り立つことを言います。

#### 証明
$H$ の固有値、固有ベクトルをそれぞれ $E_i, \left|\psi_i\right>$ と置きます。
$H$ はエルミート行列なので、各 $\left|\psi_i\right>$ は正規直交基底となります。

よって任意の状態 $\left|\psi\right>$ を考えると、複素数 $c_i$ を用いて、

``` math
\left|\psi\right> = \sum_{i = 0}^{n-1}c_i\left|\psi_i\right>
```
と置けます。

従って、$\left<\psi\right|H\left|\psi\right>$ は

``` math
\begin{align}\left<\psi\right|H\left|\psi\right> &= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\overline{c_i}c_jE_j\left<\psi_i\right|\psi_j\rangle \\
&= \sum_{i=0}^{n-1}\left|c_i\right|^2E_i
\end{align}
```
ここで $E_0 > E_i$ より、

``` math
\sum_{i=0}^{n-1}\left|c_i\right|^2E_i > \sum_{i=0}^{n-1}\left|c_i\right|^2E_0 = 
\left<\psi\right|\psi\rangle E_0 \\
\therefore \frac{\left<\psi\right|H\left|\psi\right>}{\left<\psi\right|\psi\rangle}≧E_0
```
$\left<\psi\right|\psi\rangle = 1$ から

``` math
\left<\psi\right|H\left|\psi\right> ≧ E_0
```
証明できました。

### アルゴリズム
エルミート行列 $H$ は $2^n$ 次の行列とします。

まず $\theta$ で パラメータ表示された状態 $\left|\psi(\theta)\right>$ を作ります。$(0≦\theta<2\pi)$
このパラメータ表示された状態とは主に $\left|0\right>$ にある回転ゲート $U(\theta)$ を作用させた状態のことを言います。
(パラメータがあれば回転ゲートでなくても良い)
(ex $\left|\psi(\theta)\right> = R_x(\theta)\left|0\right>$、 $\left|\psi(\theta)\right> = R_y(\theta)\left|0\right>$ )

このときエルミート行列 $H$ の期待値を $E(\theta)$ と置くと、

``` math
\left<\psi(\theta)\right|H\left|\psi(\theta)\right> = E(\theta) \\
```
またこの期待値 $E(\theta)$ は量子変分原理から

``` math
E(\theta) ≧ E_0
```
よって $E(\theta)$ の最小値を求められれば固有値を導くことができます。

ただし、量子コンピュータ上ではユニタリ行列しか考えることができないので
ユニタリ行列を使うことを考えます。

#### エルミート行列の変換
一般にエルミート行列 $H$ はユニタリ行列を使って以下のように置き換えることができます。

``` math
H = \sum_{i\alpha}^{}{h^i}_{\alpha}{\sigma^i}_{\alpha} +
\sum_{ij\alpha\beta}^{}{h^{ij}}_{\alpha\beta}{\sigma^i}_{\alpha}{\sigma^j}_{\beta} + \ldots
```
まず $\sigma_{\alpha}$ は量子ゲートで 2次のユニタリ行列です。 $\alpha, \beta$ にはゲートの種類が入ります。
例えば $\alpha = x$ なら $\sigma_{\alpha}$ は x ゲートとなります。

${h^i}_\alpha$ はユニタリ行列にかかる係数で実数をとります。

次に $i, j$ について、これは上で定義した量子ゲートをどこに作用させるかを示しています。

また、ユニタリ行列は積、テンソル積で閉じているので $\sigma_{\alpha}\sigma_{\beta}$ もユニタリ行列です。

これらのことから上の式はユニタリ行列の多項式だとわかります。

エルミート行列がユニタリ行列で書き表せるのはエルミート行列の性質から
$e^{-iH}$ がユニタリ行列となるので逆写像を考えるとわかります。

### 続き
この期待値 $\left<\psi(\theta)\right|H\left|\psi(\theta)\right>$ は線型性から以下のようになります。

``` math
\left<\psi(\theta)\right|H\left|\psi(\theta)\right> =
\sum_{i\alpha}^{}{h^i}_{\alpha}\left<{\sigma^i}_{\alpha}\right> +
\sum_{ij\alpha\beta}^{}{h^{ij}}_{\alpha\beta}\left<{\sigma^i}_{\alpha}{\sigma^j}_{\beta}\right> + \ldots \\
\left<{\sigma^i}_{\alpha}\right> = \left<\psi(\theta)\right|{\sigma^i}_{\alpha}\left|\psi(\theta)\right>
```
各ユニタリ行列の期待値 $\left<{\sigma^i}_{\alpha}\right>$ は量子コンピュータで作り出すことができます。

以上から $\left<\psi(\theta)\right|H\left|\psi(\theta)\right>$ は $\left<{\sigma^i}_{\alpha}\right>$ の和で求めることができます。

この和の部分は古典コンピュータで計算します。

最終的にはこの最小値を上で述べた勾配法で古典コンピュータを使って求めます。 [^1]
これで説明ができました。

[^1]: 量子状態を考えた場合、全体の位相のズレは等しくなるので期待値は必ずしも期待通りの値が出力される訳ではない。

全体図は以下の通り

<img width="707" alt="スクリーンショット 2020-01-19 12.51.47.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/517405/5657c24f-d271-b6c5-4b4f-814903c24578.png">

量子コンピュータで各ユニタリ行列の期待値を求め
古典コンピュータで和を取り最適化させているのがわかります。

## 補足
@YuichiroMinatoさんの[VQEアルゴリズム](https://qiita.com/YuichiroMinato/items/62444351b712743d83b7)の記事を考えてみました。

$R_x(\theta)$ では

``` math
\left|\psi(\theta)\right> = R_x(\theta)\left|0\right> = \left(\begin{array}{c} \cos\left(\frac{\theta}{2}\right) \\ -i\sin\left(\frac{\theta}{2}\right) \end{array} \right) \xrightarrow{\frac{d}{d\theta}} \frac{1}{2}\left(\begin{array}{c} -\sin\left(\frac{\theta}{2}\right) \\ -i\cos\left(\frac{\theta}{2}\right) \end{array} \right)
```
より

``` math
\begin{align}
\frac{d}{d\theta}\left<\psi(\theta)\right|H\left|\psi(\theta)\right> &=
\left<\psi'(\theta)\right|H\left|\psi(\theta)\right> +
\left<\psi(\theta)\right|H\left|\psi'(\theta)\right> \\
&=-\frac{1}{2}\sin\theta -\frac{1}{2}\sin\theta = -\sin\theta
\end{align}
```
これより勾配法を用いれば最小値を決めることができます。

$R_y(\theta)$ では

``` math
\left|\psi(\theta)\right> = R_y(\theta)\left|0\right> = \left(\begin{array}{c} \cos\left(\frac{\theta}{2}\right) \\ \sin\left(\frac{\theta}{2}\right) \end{array} \right) \xrightarrow{\frac{d}{d\theta}} \frac{1}{2}\left(\begin{array}{c} -\sin\left(\frac{\theta}{2}\right) \\
\cos\left(\frac{\theta}{2}\right) \end{array} \right)
```
より

``` math
\begin{align}
\frac{d}{d\theta}\left<\psi(\theta)\right|H\left|\psi(\theta)\right> &=
\left<\psi'(\theta)\right|H\left|\psi(\theta)\right> +
\left<\psi(\theta)\right|H\left|\psi'(\theta)\right> \\
&=-\frac{1}{2}\sin\theta -\frac{1}{2}\sin\theta = -\sin\theta
\end{align}
```
これより勾配法を用いれば最小値を決めることができます。

$R_z(\theta)$ では

``` math
\left|\psi(\theta)\right> = R_z(\theta)\left|0\right> = \left(\begin{array}{c} e^{-\frac{\theta}{2}i} \\ 0 \end{array} \right) \xrightarrow{\frac{d}{d\theta}} -\frac{i}{2}\left(\begin{array}{c} e^{-\frac{\theta}{2}i} \\ 0 \end{array} \right)
```
より

``` math
\begin{align}
\frac{d}{d\theta}\left<\psi(\theta)\right|H\left|\psi(\theta)\right> &=
\left<\psi'(\theta)\right|H\left|\psi(\theta)\right> +
\left<\psi(\theta)\right|H\left|\psi'(\theta)\right> \\
&=-\frac{i}{2} +\frac{i}{2} = 0
\end{align}
```
これは常に傾きが 0 なので勾配法を用いることができません。
このようにパラメータを作るためのゲートはうまく取らなければいけません。

## まとめ
今回は VQE について説明しました。
次回は QAOA について説明しようと思います。

## 参考文献
A variational eigenvalue solver on a quantum processor
https://arxiv.org/pdf/1304.3061.pdf