この記事に関して
ここでは量子アルゴリズムの一つである、HHLアルゴリズムについて説明します。
連立一次方程式
一般的な連立方程式は以下のように置けます。
A{\bf x} = {\bf b}
$A$ は行列、${\bf x}, {\bf b}$ はそれぞれベクトルです。
$A$ が正則行列のとき求める解は次のようになります。
{\bf x} = A^{-1}{\bf b}
今回は $A＄ が正則なときを考えます。
古典的解法
$A$ に関して
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$ は直交します。
A = \sum_{i=0}^{n-1}\lambda_i {\bf a}_i {\bf a}^{\dagger}_i
$A$ は上のようにかけるので $A^{-1}$ は
A^{-1} = \sum_{i=0}^{n-1}\lambda^{-1}_i {\bf a}_i {\bf a}^{\dagger}_i
次に ${\bf b}$ は ${\bf a}_i$ を使って以下のように表現できます。
{\bf b} = \sum_{i=0}^{n-1}\beta_i {\bf a}_i
以上から ${\bf x}$ は
{\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アルゴリズム
上の内容をまとめると
- $A$ の固有値、固有ベクトルを求める。
- ${\bf b}$ を $A$ の固有ベクトルで展開する。
- $\lambda_i$ で割って ${\bf x}$ を求める。
という流れになります。これを量子コンピュータで実装します。
このアルゴリズムを HHLアルゴリズムと言います。
回路の作成
\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つの構成に分かれています。
- QPE
- CRy ゲート
- QPEの逆演算
この流れを説明する前に下準備をします。
正規化
各ベクトルを量子ビットで考えます。
まず量子状態として長さが $1$ のベクトルを考えないといけません。
$A$ の固有ベクトル ${\bf a}_i$ は定数倍しても変わらないので以下のように置き直します。
\left|{\bf a}_i\right>_I := \frac{{\bf a}_i}{\|{\bf a}_i\|}
同様に ${\bf b}$ を以下のように変形します。
\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$ より
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を施すと
\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$ で考えて
\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$ とし
\cos(\theta_i) = \frac{1}{\lambda_i}
となるように置きます。
$i$ 番目に着目すると、
\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
よって
\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の逆演算
次に位相推定の逆演算を行います。
\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>$ の場合、式を整理すると
\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