物理とか

Index

グローバーのアルゴリズムの一般化としての量子ウォーク


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\) の回転をするゲートである。