1. 量子コンピューター上で逆行列を解く
量子コンピューター上で、
\[A\b{x} = \b{b}\tag{1}\]
という1次方程式を解き、
\[\b{x} = A^{-1}\b{b}\tag{2}\]
を得るアルゴリズムは、その発見者の名前 (Harrow-Hassidim-Lloyd) の頭文字を取って
HHL Algorithm
と呼ばれています。ただし量子コンピューターの特性上、解けるのは\(A\)がエルミート行列であるものに限られます。とは言っても、もし解きたい行列\(B\)がエルミートで無いときは、
\[A=\left(\begin{array}{cc} 0 & B \\ B^\dagger & 0\end{array}\right)\]
のように定義した\(A\)について解けば良いので、エルミート性という条件はそこまで問題にはなりません。
さて、問題を解くスピードはどうでしょうか？\(A\)の条件数 (最小固有値と最大固有値の比) を\(\kappa\)、次元を\(N\)とすると、古典コンピュータでは\(O(\kappa N)\)の時間が掛かるのに対して、HHL Algorithmでは\(O(\kappa^2\log N)\)という時間で解くことができます。\(N\to\log N\)ですから指数的なスピードアップといえますね。
このページではスピードに対する議論は面倒くさいのでしませんが、HHL Algorithmの発想とその全体像を紹介したいと思います。
2.HHL Algorithm
まずは逆行列の計算について少し思い出すために、
\[D = \left(\begin{array}{cccc} d_1&&&\\&d_2&&\\&&\ddots&\\&&&d_n\end{array}\right)\]
という対角行列による連立方程式
\[D\b{x} = \b{b}\tag{3}\]
を解いてみましょう。これは簡単で、各成分を\(d_i\)で割れば良いだけです。つまり
\[x_i = b_i/d_i\tag{4}\]
が(3)の解となります。行列が対角化できれば、逆行列を計算するのはとても簡単なのです。
このことを念頭に、HHL Algorithm を紹介します。
HHL Algorithm は次のことを仮定します。
- ベクトル\(\b{b}\)は量子状態\[\ket{\b{b}} = \sum_k b_k\ket{k}\tag{5}\]として用意されている。
- 解きたいエルミート行列\(A\)について\(U_A = e^{iA}\)という量子ゲートをcontrolledにかけることができる。
一番目の仮定はこれまでのアルゴリズムでも使われていたものですね。量子コンピュータ上にベクトルデータを埋め込むには、\(\ket{k}\)の振幅にその各成分を入れるのが常套手段です。二つ目の仮定も許してください。量子コンピュータの速さの起源は、非常に大きい次元の行列を簡単に演算できるところにもあるのですから。(しかしながら、任意の行列\(A\)について、\(U_A\)を効率的に実行できるような保証はありません。効率的であるためには、例えば行列が十分スパース (0だらけの行列のこと) でないといけないという条件もあります。)
さて、エルミート行列はどんなものでも必ず対角化でき、しかもその固有ベクトルは直交するのでした。\(A\)の固有値を\(\lambda_n\)、固有ベクトル\(\b{a}_n\)としましょう。直交しているということは一次独立ですから、ベクトル\(\b{b}\)を次のように展開することができますね。
\[\b{b} = \sum_n \beta_n\b{a}_n\tag{6}\]
これを量子状態で表すと、そのまま簡単に
\[\ket{\b{b}} = \sum_n \beta_n\ket{\b{a}_n}\tag{7}\]
となります。\(\ket{\b{b}}\)や\(\ket{\b{a}_n}\)は(5)のような状態です。
\(\b{a}_n\)で展開できてしまえば、\(A\)は対角行列とみなせて、
\[A^{-1}\b{a}_n=\frac{\b{a}_n}{\lambda_n}\]
ですから、
\[A^{-1}\b{b}=\sum_n \frac{\beta_n}{\lambda_n}\b{a}_n\tag{8}\]
と、簡単に逆行列の計算をすることができます。簡単な発想ですが、古典コンピュータでは、
- \(A\)の固有値・固有ベクトルを求める。
- \(\b{b}\)を展開した時の係数\(\beta_n\)を求め、\(\b{a}_n\)を基底として展開。
- \(\lambda_n\)で割る。
- 元の基底に戻す。
というステップを踏まないとできません。展開するのはまだしも、固有値・固有ベクトルを求める計算は次元が上がるとかなりしんどいものになります。
しかしながら、量子コンピュータでは、\(\ket{b}\)という状態を用意した時点で、その状態は
\[\ket{\b{b}} = \sum_k b_k\ket{k} = \sum_n \beta_n\ket{\b{a}_n}\tag{9}\]
のように、ある意味自動的に\(\ket{\b{a}_n}\)で展開されています。\(\ket{\b{b}}\)という状態は、(8)式のどちらとも取れる状態です。そして、量子コンピュータではうまいゲートを使うことで、あたかも\(\ket{\b{a}_n}\)によって展開されたベクトルで計算しているかのようにできるのです。
さて、目指す量子状態は(8)式を踏まえて、
\[\b{x} = \sum_n \frac{\beta_n}{\lambda_n}\b{a}_n\]
です。まずは固有値を求めなければいけませんが、ここで量子コンピュータには、あるユニタリ行列とその固有ベクトルが与えられた時、固有値を効率的に求めるアルゴリズムがあったことを思い出しましょう。
Quantum Phase Estimation (QPE) というやつで、これは次のようにレジスターqubitに近似的な固有値を2進数で入れ込むアルゴリズムです。
\[\ket{0}_{\text{register}}\ket{\b{a}_n}\xrightarrow{QPE \text{ of } e^{iA}}\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\tag{10}\]
量子コンピュータのゲートは全て線形変換ですから、(9)のような状態ベクトルをQPEアルゴリズムにかけてやれば、
\[\ket{0}_{\text{register}}\ket{\b{b}} = \sum_n \beta_n\ket{0}_{\text{register}}\ket{\b{a}_n}\xrightarrow{QPE \text{ of } e^{iA}}\sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\tag{11}\]
のように、全ての固有ベクトル\(\ket{\b{a}_n}\)に\(\lambda_n\)がエンタングルされた状態が生まれます。このようにして、「並列的に」固有値を求めることができました。
固有値を求めることができたら、次は固有値でそれぞれのベクトルを割ります。それをするには、もう1つのqubit (ancilla, アンシラ, 補助 qubitと呼ばれます。) を用意してやって、\(\ket{\lambda_n}_\text{register}\)をコントロールqubitとして controlled-rotation を ancilla qubit にかけます。うまいrotationゲートを使えば、
\[\ket{\lambda_n}_\text{register}\ket{0}_\text{anc} \xrightarrow{\text{c-rotation}} \ket{\lambda_n}_\text{register}\left(\frac{1}{\lambda_n}\ket{0} + \sqrt{1-\left(\frac{1}{\lambda_n}\right)^2}\ket{1}\right)_\text{anc}\tag{12}\]
のような状態を作り出せます。
このゲートを(11)にかけてやれば、
\[\sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\ket{0}_\text{anc} \to \sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\left(\frac{1}{\lambda_n}\ket{0} + \sqrt{1-\left(\frac{1}{\lambda_n}\right)^2}\ket{1}\right)_\text{anc}\tag{13}\]
となりますね。最後にancilla qubitを観測します。\(\ket{1}\)が出たときはもう一度最初からやり直しですが、\(\ket{0}\)が出たときは、状態が
\[\sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\left(\frac{1}{\lambda_n}\ket{0} + \sqrt{1-\left(\frac{1}{\lambda_n}\right)^2}\ket{1}\right)_\text{anc}\xrightarrow{\text{measured} \ket{0}_\text{anc}} C\sum_n \frac{\beta_n}{\lambda_n}\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\ket{0}_\text{anc}\tag{14}\]
と収縮します。測定後も状態は規格化されていなければならないために、\(C\)という規格化定数がかかることには少し注意しておきましょう。
(14)の状態は、\(C\)を除けば求めたかったほとんど\(\ket{\b{x}}\)そのものです。最後にQPEの逆変換を掛けて、エンタングルしている\(\ket{\lambda_n}\)を\(\ket{0}\)に戻せば、
\[C\sum_n \frac{\beta_n}{\lambda_n}\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\ket{0}_\text{anc}\xrightarrow{QPE^{-1} \text{ of } e^{iA}}C\ket{0}_\text{register}\left(\sum_n \frac{\beta_n}{\lambda_n}\ket{\b{a}_n}\right)\ket{0}_\text{anc}\tag{15}\]
となり、たしかに\(\ket{\b{b}}\)を\(\ket{\b{x}}=A^{-1}\ket{\b{b}}\)に変換できていることがわかります。
3. まとめ
HHL アルゴリズムは、次のようなアルゴリズムです。
\[
\ket{0}_\text{reg}\ket{\b{b}}\ket{0}_\text{anc} = \ket{0}_\text{reg}\sum_n \left(\beta_n\ket{\b{a}_n}\right)\ket{0}_\text{anc}\\
\xrightarrow{QPE \text{ of } e^{iA}}\sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\ket{0}_\text{anc}\\
\xrightarrow{\text{c-rotation}}\sum_n \beta_n\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\left(\frac{1}{\lambda_n}\ket{0} + \sqrt{1-\left(\frac{1}{\lambda_n}\right)^2}\ket{1}\right)_\text{anc}\\
\xrightarrow{\text{measured} \ket{0}_\text{anc}} C\sum_n \frac{\beta_n}{\lambda_n}\ket{\lambda_n}_\text{register}\ket{\b{a}_n}\ket{0}_\text{anc}\\
\xrightarrow{QPE^{-1} \text{ of } e^{iA}}C\ket{0}_\text{register}\left(\sum_n \frac{\beta_n}{\lambda_n}\ket{\b{a}_n}\right)\ket{0}_\text{anc}\\
=\ket{0}_\text{register}\ket{A^{-1}\b{b}}\ket{0}_\text{anc}
\]
最初に言ったように、このアルゴリズムのスピードに関して突っ込んだ議論はしませんが、量子コンピュータを使った HHL アルゴリズムでは「並列的に」固有値を求め、「並列的に」固有値を割り算できるというところに高速性の起源があります。
また、このアルゴリズムは何も逆行列計算だけでなく、行列をかけることにも使えます。簡単な発想で、行列をかけるときには\(\lambda_n\)で割るのではなくかければ良いだけですから、ancillaのcontrolled rotationを
\[\left(\lambda_n\ket{0} + \sqrt{1-\lambda_n^2}\ket{1}\right)_\text{anc}\]
の形に持っていけば良いわけです。
今回のHHL アルゴリズムの解説はこれで終わりです。発展例としては、Phase Estimationを効率的にしたものなどが提案されてはいますが、まだまだ新しい研究分野ですので、もしこのアルゴリズムの良い応用が思いつけば世界新発見かもしれませんね。