2021-08-01

HHLアルゴリズム

量子コンピュータ

はじめに

　今回は、連立一次方程式を量子コンピュータを用いて解く際に使われるHHL（Harrow-Hassidim-Lloyd）アルゴリズムを紹介する。

一般的な解法

　最初に一般的な解法を示す。 $N$ 次元ベクトル ${\bf x},{\bf b}$ の間に次式が成り立っているとする。

${\displaystyle \begin{equation} A{\bf x}={\bf b}\tag{1} \end{equation} }$

$A$ は、 $N\times N$ のユニタリー行列である。このとき

${\displaystyle \begin{equation} {\bf x}=A^{-1}{\bf b}\tag{2} \end{equation} }$

を求めたい。 $A$ の固有値と固有ベクトルをそれぞれ $\lambda_n,{\bf a}_n$ と置くと

${\displaystyle \begin{equation} A{\bf a}_n=\lambda_n{\bf a}_n\tag{3} \end{equation} }$

が成り立ち、ベクトル ${\bf b}$ を ${\bf a}_n$ で展開することができる。

${\displaystyle \begin{equation} {\bf b}=\sum_{n=0}^{N-1}\beta_n{\bf a}_n\tag{4} \end{equation} }$

式(4)を式(2)に代入すると

${\displaystyle \begin{equation} {\bf x}=\sum_{n=0}^{N-1}\beta_n A^{-1}{\bf a}_n\tag{5} \end{equation} }$

式(3)より

${\displaystyle \begin{equation} A^{-1}{\bf a}_n=\dfrac{1}{\lambda_n} {\bf a}_n \end{equation} }$

これを式(5)に代入して

${\displaystyle \begin{equation} {\bf x}=\sum_{n=0}^{N-1}\dfrac{\beta_n}{\lambda_n} {\bf a}_n\tag{6} \end{equation} }$

を得る。ここまでの式変形を量子コンピュータ上で行う手順を次に示す。

HHLアルゴリズム

　最初に、 ${\bf b}$ を振幅エンコーディングする。

${\displaystyle \begin{equation} |{\bf b}\rangle_A=\sum_{k=0}^{N-1}b_k|k\rangle_A\tag{7} \end{equation} }$

振幅エンコーディングについてはこことここにまとめてある。あとの区別のため、エンコード先をAレジスタと呼ぶことにする。これは複数の量子ビットから構成された量子状態である。さて、量子コンピュータでは顕に固有状態 $|{\bf a}_n\rangle$ を求める必要がないことに注意する。式(7)を得た時点でそれを固有状態 $|{\bf a}_n\rangle$ による展開と同一視することができる。

${\displaystyle \begin{equation} |{\bf b}\rangle_A=\sum_{k=0}^{N-1}b_k|k\rangle_A=\sum_{n=0}^{N-1}\beta_n|{\bf a}_n\rangle_A \end{equation} }$

ここが古典論との大きな違いである。次に、 $U=e^{iA}$ を考える。 $A$ をユニタリー行列としたから $U$ もユニタリー行列であり、次式が成り立つ。

${\displaystyle \begin{equation} U|{\bf a}_n\rangle_A=e^{iA}|{\bf a}_n\rangle_A=e^{i\lambda_n}|{\bf a}_n\rangle_A \end{equation} }$

固有値 $\lambda_n$ を求めるため、量子位相推定（QPE）を行う。QPEを行うため、複数の量子ビットからなるBレジスタを追加する（0で初期化）。

${\displaystyle \begin{equation} |{\bf b}\rangle_A|0\rangle_B=\sum_{n=0}^{N-1}\beta_n|{\bf a}_n\rangle_A|0\rangle_B \end{equation} }$

この状態にQPEを施して $A$ の固有値 $\lambda_n$ をBレジスタに入れる。

${\displaystyle \begin{equation} \sum_{n=0}^{N-1}\beta_n|{\bf a}_n\rangle_A|\lambda_n\rangle_B \end{equation} }$

次に、複数ビットからなるCレジスタを追加し、Bレジスタの値を用いた算術演算（ $f(x)=\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{x}}$ ）を行い、結果をCレジスタに入れる。

${\displaystyle \begin{equation} \sum_{n=0}^{N-1}\beta_n\;|{\bf a}_n\rangle_A\;|\lambda_n\rangle_B\;|\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{\lambda_n}}\rangle_C \end{equation} }$

次に、1ビットからなるDレジスタを追加し、Cレジスタの各ビットを制御ビットとしてDレジスタに回転ゲート $R_y(\pi 2^{-k})$ を施す。このあたりの詳細な式変形はここにまとめてある。

${\displaystyle \begin{equation} \sum_{n=0}^{N-1}\beta_n\;|{\bf a}_n\rangle_A\;|\lambda_n\rangle_B\;|\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{\lambda_n}}\rangle_C \left( \dfrac{1}{\lambda_n}|0\rangle_D+\sqrt{1-\left(\dfrac{1}{\lambda_n}\right)^2}|1\rangle_D \right) \end{equation} }$

Dレジスタを測定し0が得られたとき、次の状態に収縮する。

${\displaystyle \begin{equation} C\sum_{n=0}^{N-1}\dfrac{\beta_n}{\lambda_n}\;|{\bf a}_n\rangle_A\;|\lambda_n\rangle_B\;|\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{\lambda_n}}\rangle_C \;|0\rangle_D \end{equation} }$

ここで、 $C$ は規格化定数である。B,Cレジスタにそれぞれの逆演算を施し初期化する。

${\displaystyle \begin{equation} C\sum_{n=0}^{N-1}\dfrac{\beta_n}{\lambda_n}\;|{\bf a}_n\rangle_A\;|0\rangle_B\;|0\rangle_C \;|0\rangle_D \end{equation} }$

Aレジスタに式(6)が再現されている。

2021-07-24

木構造を使った振幅エンコーディング

量子コンピュータ

はじめに

　前回、振幅エンコーディングの手順を示した。その手法では、確率（前回の式(4)）

${\displaystyle \begin{align*} P=\dfrac{1}{N}\sum_{i=0}^{N-1}v_i^2 \end{align*} }$

が小さいとき、何度も測定を繰り返す必要があり効率が悪くなる。今回は、エンコーディングを行う過程の中に「測定」を含まない手法（木構造を用いた振幅エンコーディング）を説明する。

木構造

　8次元ベクトル ${\bf v}=(v_0,\cdots,v_7)$ を振幅に埋め込んだ状態

${\displaystyle \begin{align} |\psi\rangle &=\sum_{k=0}^{7}v_k|k\rangle\\ &=v_0|000\rangle+v_1|001\rangle+v_2|010\rangle+v_3|011\rangle+v_4|100\rangle+v_5|101\rangle+v_6|110\rangle+v_7|111\rangle \label{eq0} \end{align} }$

を作ることを目的とする。規格化条件

${\displaystyle \begin{align*} \sum_{k=0}^{7}|v_k|^2=1 \end{align*} }$

は満たされているとする。 $v_k$ は実数値である。8次元ベクトルを埋め込むのに必要な最小の量子ビット数は3であるので、ここでは3個の量子ビットを用いる。

　　最初に以下に示す木構造を作る。

次に、3個の量子ビットからなる $A$ レジスタと $m$ 個の量子ビットからなる $B$ レジスタを用意する。すべてのビットは0に初期化されている。

${\displaystyle \begin{align*} |000\rangle_A\;|0\cdots0\rangle_B \end{align*} }$

$A$ レジスタをアドレスとして扱い、木構造からデータを取り出し、 $B$ レジスタに入れる仕組みを作る（実現の仕方はここでは言及しない）。取り出す手順は以下の通り。

$A$ レジスタの値 $a$ を読む。
Node aの左側の子ノードの値を、 $B$ レジスタに基底エンコーディングにより読み込む。

たとえば、最初の操作では $A$ レジスタの最初のビットの値をアドレス $a$ とする。 $a=0$ の場合、 $B$ レジスタにNode 00の値を読み込む。 $a=1$ の場合、 $B$ レジスタにNode 10の値を読み込む。次の操作では $A$ レジスタの最初の2ビットをアドレスとして扱い同じことを繰り返す。 $a=00$ の場合、 $B$ レジスタにNode 000の値を読み込む。 $a=01$ の場合、 $B$ レジスタにNode 010の値を読み込む。

　以下具体的に木構造を用いた振幅エンコーディングの手順を示す。

振幅エンコーディング

1. 初期状態

　上に述べた初期状態を作る。

${\displaystyle \begin{align*} |\psi_1\rangle=|000\rangle_A\;|0\cdots0\rangle_B \end{align*} }$

2. Node 0のデータ取り出し

　rootノードの左側の子ノードNode 0からデータを取り出す。この操作は上の手順を踏まない例外的な操作である。

${\displaystyle \begin{align*} |\psi_2\rangle=|000\rangle_A\;|b(V_1^2)\rangle_B \end{align*} }$

ここで

${\displaystyle \begin{align*} V_1^2=\sum_{i=0}^{3}v_i^2 \end{align*} }$

$b(x)$ は $x$ の2進数表記を表す（前回と同じ）。

3. 算術演算

　 $C$ レジスタを追加して、ここに $B$ レジスタの値 $V^2$ を引数とする関数の値 $f(V_1^2)=\dfrac{1}{\pi}\cos^{-1}{V_1}$ を入力する。

${\displaystyle \begin{align*} |\psi_3\rangle &= |000\rangle_A\;|b(V_1^2)\rangle_B\;|b(\dfrac{1}{\pi}\cos^{-1}{V_1})\rangle_C \\ &= |000\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C \end{align*} }$

2行目の式は、 $C$ レジスタ内の値を2進数で書いたものである。詳細は前回の解説にある。

4. 回転ゲートの適用

　 $A$ レジスタの最初のビットを明示すると

${\displaystyle \begin{align*} |\psi_3\rangle= |0\rangle_A\;|00\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C \\ \end{align*} }$

となる。 $C$ レジスタの各ビットを制御ビットにして、 $A$ レジスタの最初のビットに $R_y(\pi 2^{-k})$ を作用させる。

${\displaystyle \begin{align*} |\psi_4\rangle= \left(V_1|0\rangle_A+\sqrt{1-V_1^2}|1\rangle_A\right) \;|00\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C \end{align*} }$

ここで

${\displaystyle \begin{align*} V_1&=\sqrt{\sum_{i=0}^3 v_i^2}\\ \sqrt{1-V_1^2}&=\sqrt{\sum_{i=4}^7 v_i^2} \end{align*} }$

である。 $|\psi_4\rangle$ を得るまでの計算の詳細は、前回の解説に記載してある。

5. $B,C$ レジスタの初期化

　 $B,C$ レジスタに逆演算を施して初期化する。

${\displaystyle \begin{align} |\psi_5\rangle &= \left(V_1|0\rangle_A+\sqrt{1-V_1^2}|1\rangle_A\right) \;|00\rangle_A\;|0\rangle_B\;|0\rangle_C \nonumber \\ &= V_1|0\rangle_A\;|00\rangle_A\;|0\rangle_B\;|0\rangle_C +\sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|0\rangle_B\;|0\rangle_C \label{eq1} \end{align} }$

6. Node 00のデータの取り出し

　式(\ref{eq1})の第1項を考える。 $A$ レジスタの最初のビット0をアドレスとして、木構造からNode 0の左側の子ノードNode 00の値を取り出し $B$ レジスタに入れる。

${\displaystyle \begin{align*} |\psi_6\rangle = V_1|0\rangle_A\;|00\rangle_A\;|b(V_2^2)\rangle_B\;|0\rangle_C \end{align*} }$

ここで

${\displaystyle \begin{align*} V_2^2=\dfrac{v_0^2+v_1^2}{P} \end{align*} }$

である。

7. Node 10のデータの取り出し

　式(\ref{eq1})の第2項を考える。 $A$ レジスタの最初のビット1をアドレスとして、木構造からNode 1の左側の子ノードNode 10の値を取り出し $B$ レジスタに入れる。

${\displaystyle \begin{align*} |\psi_7\rangle = \sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|b(V_3^2)\rangle_B\;|0\rangle_C \end{align*} }$

ここで

${\displaystyle \begin{align*} V_3^2=\dfrac{v_4^2+v_5^2}{Q} \end{align*} }$

である。

8. Node 00とNode 10のデータを取り出した結果

　 $|\psi_6\rangle$ と $|\psi_7\rangle$ を合わせて

${\displaystyle \begin{align*} |\psi_8\rangle = V_1|0\rangle_A\;|00\rangle_A\;|b(V_2^2)\rangle_B\;|0\rangle_C+ \sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|b(V_3^2)\rangle_B\;|0\rangle_C \end{align*} }$

9. 算術演算と初期化

　 $|\psi_8\rangle$ に以下の操作を行う。

先と同様に $B$ レジスタの値を用いた算術演算を行い $C$ レジスタに値を入れる。
$C$ レジスタ内の各ビットを制御ビットとして、回転ゲートを $A$ レジスタの2つ目のビットに施す。
$B,C$ レジスタに逆演算を施し初期化する。

これらを行うと以下を得る。

${\displaystyle \begin{align*} |\psi_9\rangle &=\left( V_1V_2|00\rangle_A\;|0\rangle_A+ V_1\sqrt{1-V_2^2}|01\rangle_A\;|0\rangle_A+ \sqrt{1-V_1^2}V_3|10\rangle_A\;|0\rangle_A+ \sqrt{1-V_1^2}\sqrt{1-V_3^2}|11\rangle_A\;|0\rangle_A\right)\\ &&\hspace{10cm}\otimes \;|0\rangle_B\;|0\rangle_C\\ &= \left( \sqrt{v_0^2+v_1^2}|00\rangle_A\;|0\rangle_A+ \sqrt{v_2^2+v_3^2}|01\rangle_A\;|0\rangle_A+ \sqrt{v_4^2+v_5^2}|10\rangle_A\;|0\rangle_A+ \sqrt{v_6^2+v_7^2}|11\rangle_A\;|0\rangle_A\right)\\ &\hspace{10cm}\otimes \;|0\rangle_B\;|0\rangle_C \end{align*} }$

10. 最後のステップ

　 $A$ レジスタの最初の2つのビットをアドレスとして木構造からデータを取り出し、 $B$ レジスタに入れる。たとえば、最初の2つのビットが00のとき、Node 00の左側の子ノードNode 000の値を取り出す。算術演算など同様な計算を繰り返すと次の状態を得る。

${\displaystyle \begin{align*} |\psi_{10}\rangle&= \left( \sqrt{v_0^2}|000\rangle_A+ \sqrt{v_1^2}|001\rangle_A+ \sqrt{v_2^2}|010\rangle_A+ \sqrt{v_3^2}|011\rangle_A+ \sqrt{v_4^2}|100\rangle_A \right.\\ &\hspace{5cm}+ \left. \sqrt{v_5^2}|101\rangle_A+ \sqrt{v_6^2}|110\rangle_A+ \sqrt{v_7^2}|111\rangle_A \right)\otimes |0\rangle_B\;|0\rangle_C \end{align*} }$

一番深いノードに格納してある $v_k$ の符号も取り出して根号を外す。

${\displaystyle \begin{align*} |\psi_{10}\rangle&= \bigl( v_0|000\rangle_A+ v_1|001\rangle_A+ v_2|010\rangle_A+ v_3|011\rangle_A+ v_4|100\rangle_A \bigr.\\ &\hspace{5cm}+ \bigl. v_5|101\rangle_A+ v_6|110\rangle_A+ v_7|111\rangle_A \bigr)\otimes |0\rangle_B\;|0\rangle_C \end{align*} }$

目的とする式(\ref{eq0})が得られた。

まとめ

　今回は木構造を利用した振幅エンコーディングを説明した。 $N$ 次元ベクトル ${\bf v}=(v_0\cdots v_{N-1})$ のとき、 $\log_2{N}$ の多項式のオーダでエンコーディングを行うことができる。前回の方法は、エンコーディング過程に測定行為が含まれており、場合によっては効率が悪くなる欠点があった。

参考文献

2021-07-18

振幅エンコーディング

量子コンピュータ