1. このページの目的
このページでは、グローバーのアルゴリズムの一般化として、俗に Szegedy walk とか、staggerd quantum walk と呼ばれている量子ウォークを実行するゲートの一般形を紹介する。特に、このゲートの固有値を導出することが目標である。
僕には、なぜこのページに書いた操作が量子ウォークと呼ばれるのかはわからない。命名の直感的な理解を誰か教えてほしいな。
2. グローバーのアルゴリズム
まずグローバーのアルゴリズムを簡単にまとめておこう。
\(\{\ket{i}\}\) を \(N\) 個の正規直交するベクトルとする。
グローバーのアルゴリズムは、
\[\ket{\psi_0} = \frac{1}{\sqrt{N}}\sum_{i=1}^n \ket{i}\]
という状態から、あるベクトル \(\ket{x} \in \{\ket{i}\}\) の取り出すアルゴリズムだった。具体的には、Grover iteration と呼ばれるゲート \(G\) を \(n = O(\sqrt{N})\) 回かけることにより、
\[G^n\ket{\psi_0} \approx \ket{x}\]
とするアルゴリズムである。また、\(G\) は次のように 2 つの反転操作を繰り返したものとして定義されていた。
\[G = \left(2\ket{\psi_0}\bra{\psi_0} -I\right)\left(2\ket{x}\bra{x} -I\right)\]
\(I\) は単位行列である。
3. 一般化
グローバーのアルゴリズムではある 2 つのベクトル \(\ket{\psi_0}, \ket{x}\) に関する反転操作を行ったが、ここではその一般化として、複数のベクトルに関する反転操作を考え、量子ウォークの演算子 \(W\) を定義しよう。
反転に使うベクトルを \(\{\ket{a_i}\}\)\((i = 1, 2, \cdots, n)\) と \(\{\ket{b_j}\}\) \((j = 1, 2, \cdots, m)\) としよう。どちらも \(N\) 次元のベクトルで、\(\ket{a_i}\) 同士、\(\ket{b_j}\) 同士は正規直交しているものとする。(逆に \(\ket{a_i}\) と \(\ket{b_j}\) は直交している必要は無い。) これらを用いて演算子 \(W\) を
\[W = \left(2\sum_{i=1}^n\ket{a_i}\bra{a_i} -1\right)\left(2\sum_{j=1}^m \ket{b_j}\bra{b_j} -1\right)\]
と定義する。
このページでは、この演算子 \(W\) の固有値・固有ベクトルを、\(\ket{a_i}, \ket{b_j}\) で表すことが目標である。
結論を先に書いておこう。
\(D\) を \(D_{ij} = \braket{a_i}{b_j}\) を成分とする \(n\times m\) の行列とする。また、\(D\) の右特異ベクトルのうち、任意にとってきたものを \(\b{v}\), 対応する左特異ベクトルを \(\b{u}\)、特異値を \(\sigma = \cos \theta\) とする。このとき \(W\) は
\[\left\{\sum_{i=1}^n u_i\ket{a_i}, \sum_{j=1}^m v_j\ket{b_j}\right\}\]
という2つのベクトルによって張られる空間を不変部分空間として持つ。また、\(\theta\) はこの2つのベクトルが成す角度である。
この空間における \(W\) の固有値は
\[w_{\pm} = e^{\pm i2\theta}\]
であり、対応する固有ベクトル \(\ket{w_{\pm}}\) は
\begin{align}
\ket{w_+} &= e^{i\theta} \sum_{i=1}^n u_i\ket{a_i} + \sum_{j=1}^m v_j\ket{b_j} \\
\ket{w_-} &= e^{-i\theta} \sum_{i=1}^n u_i\ket{a_i} + \sum_{j=1}^m v_j\ket{b_j}
\end{align}
となる。(ただし \(\sigma\neq 0,1\) の場合。\(\sigma = 0,1\) のときは特に難しくないし面白くないのでここでは解説しない。)
この形の演算子 \(W\) は様々な量子アルゴリズムに登場して、重要な役割を担っている。
4. グラム行列との関係
表記の簡単化のため、\(\{\ket{a_i}\}\) が張る空間を \(A\), \(\{\ket{b_i}\}\) が張る空間を \(B\) と書く。そして、
\begin{align}
P_A &= \sum_{i=1}^n\ket{a_i}\bra{a_i} \\
P_B &= \sum_{j=1}^m\ket{b_j}\bra{b_j}
\end{align}
と書こう。\(P_A\), \(P_B\) はそれぞれ \(A\), \(B\) への射影演算子である。
さて、\(W\) の作用を具体的に見てみよう。\(W\) が作用する空間のベクトルは、複素数 \(\alpha_i, \beta_j\) を用いて一般に
\[\sum_{i=1}^n \alpha_i \ket{a_i} + \sum_{j=1}^n \beta_j \ket{b_j} \]
とかけるだろう。(もちろん、\(\ket{a_i}\), \(\ket{b_j}\) は一般に線型独立でないから、適当なベクトル \(\ket{\psi}\) が与えられたとき、上の形への分解は一意では無い。)
このベクトルを
\[\ket{\b{\alpha}, \b{\beta}} := \sum_{i=1}^n \alpha_i \ket{a_i} + \sum_{j=1}^m \beta_j \ket{b_j} \]
と書くことにする。
\(\ket{\b{\alpha}, \b{\beta}}\) に対する \(W\) の作用を計算していこう。\(W=4P_AP_B - 2P_A - 2P_B + I\) なので、一つ一つの項に分けて計算していく。
\begin{align}
P_A\ket{\b{\alpha}, \b{\beta}}
&= \sum_{i=1}^n \alpha_i \ket{a_i} + \sum_{i=1}^n\sum_{j=1}^m \beta_j \braket{a_i}{b_j} \ket{a_i}\\\\
P_B\ket{\b{\alpha}, \b{\beta}}
&= \sum_{i=1}^n\sum_{j=1}^m \alpha_i \braket{b_j}{a_i}\ket{b_j} + \sum_{j=1}^m \beta_j \ket{b_j}\\\\
P_A P_B\ket{\b{\alpha}, \b{\beta}}
&= P_A\left(\sum_{i=1}^n\sum_{j=1}^m \alpha_i \braket{b_j}{a_i}\ket{b_j} + \sum_{j=1}^m \beta_j \ket{b_j}\right)\\
&= \left(\sum_{i=1}^n\sum_{i'=1}^n\sum_{j=1}^m \alpha_i \braket{b_j}{a_i}\braket{a_{i'}}{b_j} \ket{a_{i'}} + \sum_{j=1}^m \beta_j \braket{a_{i'}}{b_j}\ket{a_{i'}}\right)\\
\end{align}
\(\braket{a_{i}}{b_j}\) というのがたくさん出てきたので、ここで行列 \(D\) をその \((i,j)\) 成分が
\[D_{ij} = \braket{a_i}{b_j}\]
となるものとして定義しよう。定義から \(D\) は \(n\times m\) 行列である。このようにベクトルの内積をその成分に持つような行列を
グラム行列という。
そうすると、例えば \(P_A\ket{\b{\alpha}, \b{\beta}}\) は
\[P_A\ket{\b{\alpha}, \b{\beta}} = \ket{\b{\alpha} + D\b{\beta}, 0_m}\]
とかけるだろう。\(0_m\) は \(m\) 次元の 0 ベクトルとする。
また、
\[D_{ji}^* = \braket{b_j}{a_i}\]
だから、
\[P_B\ket{\b{\alpha}, \b{\beta}} = \ket{0_n, D^\dagger \b{\alpha} + \b{\beta}}\]
も言える。最後に \(P_A P_B\ket{\b{\alpha}, \b{\beta}}\) は
\[P_A P_B\ket{\b{\alpha}, \b{\beta}} = \ket{DD^\dagger \b{\alpha} + D\b{\beta}, 0_m}\]
である。\(D^\dagger\) は \(D\) のエルミート共役。
したがって、\(W\) の \(\ket{\b{\alpha}, \b{\beta}}\) に対する作用は以下のように書ける。
\[W\ket{\b{\alpha}, \b{\beta}} = \ket{(4DD^\dagger-I_n)\b{\alpha} + 2D\b{\beta}, -2D^\dagger \b{\alpha} - \b{\beta}}\tag{1}\]
ここで \(I_n\) は \(n\) 次元の単位行列である。
5. \(D\) の特異値と \(W\) の固有値
さて、上の式は
\[\left(\begin{array}{c}\b{\alpha}\\\b{\beta}\end{array}\right)\]
\(n+m\) 次元のベクトルを使うと、このベクトルに対する \(W\) の作用は
\[\left(\begin{array}{c}\b{\alpha}\\\b{\beta}\end{array}\right) \xrightarrow{W}
\left(\begin{array}{cc}4DD^\dagger - I_n & 2D \\ -2D^\dagger & - I_m\end{array}\right)\left(\begin{array}{c}\b{\alpha}\\\b{\beta}\end{array}\right)\]
と書けるだろう。したがって \(W\) の固有値は、
\[\left(\begin{array}{cc}4DD^\dagger - I_n & 2D \\ -2D^\dagger & - I_m\end{array}\right)\]
という行列の固有値と同じだ。\(W\) の固有値を \(w\) とすると、固有値方程式は
\begin{align}
\text{det}\left(\begin{array}{cc}4DD^\dagger - (1+w)I_n & 2D \\ -2D^\dagger & - (1+w)I_m\end{array}\right) = 0
\end{align}
である。\(w\neq -1\) のとき、
ブロック行列の行列式の公式をつかって展開できる。
\begin{align}
\text{det}\left(4DD^\dagger - (1+w)I_n - \frac{4}{1+w} DD^\dagger\right) = 0
\end{align}
少し変形すると
\begin{align}
\text{det}\left(DD^\dagger - \frac{(1+w)^2}{4w}I_n\right) = 0
\end{align}
を得る。これは \(DD^\dagger\) という行列の固有値方程式そのものである。この計算から、\(DD^\dagger\) の固有値・固有ベクトル、すなわち行列 \(D\) の特異値・特異ベクトルが、\(W\) の固有値と密接な関係にあると気づくことができるだろう。
6. \(W\) の不変部分空間
上の議論から、\(D\) の特異ベクトルを使って、\(W\) の作用を表すことを試みよう。
\(D\) の右特異ベクトルの一つを \(\b{v}\)、対応する左特異ベクトルを \(\b{u}\) とする。これらのベクトルに対応する特異値を \(\sigma^2\) としたとき、特異値分解の性質から
\begin{align}
D\b{v} &= \sigma \b{u} \\
D^\dagger \b{u} &= \sigma \b{v} \\
\end{align}
が成り立つ。
このベクトル \(\b{v}\), \(\b{u}\) を使って、
\[\ket{\b{u},\b{v}} = \sum_{i=1}^n u_i \ket{a_i} + \sum_{j=1}^m v_j \ket{b_j}\]
を作ると、このベクトルに対する \(W\) の作用は (1) 式から
\[W\ket{\b{u},\b{v}} = \ket{(4\sigma^2 + 2\sigma - 1)\b{u}, -(2\sigma + 1)\b{v}}\]
である。ここで気づくのは、\(W\) を作用させた前後でどちらも、\(\ket{\b{u},\b{v}}\) は \(\ket{\b{u}, 0_m}\) と \(\ket{0_n,\b{v}}\) の線形結合で表されていることである。そこでこの空間が \(W\) に関する不変部分空間になっているのではないかと考えられる。
\(\ket{\b{u}, 0_m}\) と \(\ket{0_n,\b{v}}\) に \(W\) をかけて確かめてみよう。
\begin{align}
W\ket{\b{u}, 0_m} &= \ket{(4\sigma^2 - 1)\b{u}, -2\sigma \b{v}} \\
W\ket{0_n, \b{v}} &= \ket{2\sigma \b{u}, -\b{v}}
\end{align}
となり、確かにそうなることがわかった。
\(D\) の右特異ベクトルを \(\b{v}\), 対応する左特異ベクトルを \(\b{u}\) とし
\begin{align}
\ket{\b{u}, 0_m} &= \sum_{i=1}^n u_i \ket{a_i}\\
\ket{0_n, \b{v}} &= \sum_{j=1}^m v_j \ket{b_j}
\end{align}
という2つのベクトル \(\{\ket{\b{u}, 0_m}, \ket{0_n, \b{v}}\}\) を定義する。\(W\) はこの2つによって張られる空間を不変部分空間として持つ。すなわち、\(W\) の作用はこの部分空間において \(2\times 2\) 行列で表すことができ、基底を \(\ket{\b{u}, 0_m}, \ket{0_n, \b{v}}\) にとり、
\begin{align}
\ket{\b{u}, 0_m} &\to \left(\begin{array}{c}1 \\ 0\end{array}\right) \\
\ket{0_n, \b{v}} &\to \left(\begin{array}{c}0 \\ 1\end{array}\right)
\end{align}
と対応付けたとき、この部分空間における \(W\) の作用は
\[W \to \left(\begin{array}{cc}4\sigma^2 -1 & 2\sigma \\ -2\sigma & -1 \end{array}\right)\]
と表すことができる。
7. \(W\) の固有値・固有ベクトル
\(W\) の固有値 \(w\) は、上の 2×2 行列の固有値だから
\begin{align}
-(4\sigma^2 -(1 + w))(1+w) + 4\sigma^2 &= 0\\
(1 + w)^2 - 4\sigma^2(1+w) + 4\sigma^2 &= 0\\
\end{align}
という方程式から求められて
\[w_{\pm} = 2\sigma^2-1 \pm 2\sigma \sqrt{\sigma^2 - 1}\]
となる。
\(D\) の特異値 \(\sigma\) は、最初に述べたように、\(\ket{\b{u}, 0_m},\ket{0_n, \b{v}}\)という2つのベクトルが成す角と関係がある。実際にこれらのベクトルの内積を計算してみると
\begin{align}
\braket{\b{u}, 0_m}{0_n, \b{v}} &= \left(\sum_{i=1}^n u_i^* \bra{a_i}\right)\left(\sum_{j=1}^m v_j \ket{b_j}\right) \\
&= \sum_{i=1}^n\sum_{j=1}^m u_i^* D_{ij} v_j \\
&= \b{u}^\dagger D \b{v} \\
&= \sigma \b{u}^\dagger \b{u}\\
&= \sigma
\end{align}
となる。よって \(\ket{\b{u}, 0_m},\ket{0_n, \b{v}}\) が成す角を \(\theta\) とすると \(\sigma = \cos\theta\) である。これを固有値 \(w_{\pm}\) の表式に代入すれば
\[w_\pm = e^{\pm i2\theta}\]
と表せる。それぞれの固有値 \(w_\pm\) に対応する固有ベクトル \(\ket{w_{\pm}}\) も簡単な計算によって求められて、
\begin{align}
\ket{w_+} &= e^{i\theta} \sum_{i=1}^n u_i\ket{a_i} - \sum_{j=1}^m v_j\ket{b_j} \\
\ket{w_-} &= e^{-i\theta} \sum_{i=1}^n u_i\ket{a_i} - \sum_{j=1}^m v_j\ket{b_j}
\end{align}
である。
8. ベクトルの動き
最後に、\(W\) が作り出す動きについて説明して終わりにしよう。グローバーのアルゴリズムで使われるゲート
\[G =\left(2\ket{\psi_0}\bra{\psi_0} -I\right)\left(2\ket{x}\bra{x} -I\right)\]
は、\(\ket{\psi_0}\) を \(\{\ket{\psi_0}, \ket{x}\}\) が張る平面内で \(2\theta\) だけ回転させるという作用があった。導出を見ればわかるように、今回のゲート \(W\) もそれと全く同じような作用を持つ。つまり、\(W\) は \(\sum_{i=1}^n u_i\ket{a_i}\) と \(\sum_{j=1}^m v_j\ket{b_j}\) が張る平面内で、\(2\theta\) の回転をするゲートである。