Tech Blog

勉強したことをまとめます。

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)が再現されている。