この記事に関して
ここでは量子アルゴリズムの一つである、量子位相推定( Quantum Phase Estimation )について、説明します。
量子位相推定
このアルゴリズムはユニタリ行列の固有値を求めるアルゴリズムです。
ユニタリ行列、固有値、固有ベクトルに関しては別の記事で説明します。
ユニタリ行列の固有値の絶対値は 1 なので $\lambda$ と置くと
$\lambda = e^{\theta i}$ と書けます。$(0≦\theta<2\pi)$
このことから $\theta$ が導出できれば固有値が求められることがわかります。
考えるユニタリ行列を $U$ とします。
この固有ベクトルを $\left|u\right>$ と置くと
U\left|u\right> = e^{\theta i}\left|u\right> = e^{2\pi ij}\left|u\right> \\
(0≦j<1)
と書けます。
また $U$ を $2^k$ かけると以下のように表せます。
U^{2^k}\left|u\right> = e^{\theta i 2^k}\left|u\right> = e^{2\pi i2^kj}\left|u\right> \\
(0≦j<1)
ここで $j$ は以下のように書けるとします。
j = \frac{j_1}{2^1} + \frac{j_2}{2^2} + \cdots + \frac{j_{n-1}}{2^{n-1}} + \frac{j_n}{2^n}
このように ２進数表示に書き直すことで $2^kj$ は以下のようになります。
e^{2\pi i 2^kj} = e^{2\pi i(\frac{j_{k+1}}{2}\cdots \frac{j_n}{2^{n-k}})} = e^{2\pi i0.j_{k+1}\cdots j_n}
これを用いて以下の状態を考えると量子フーリエ変換後と似たようなものになります。
\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{0}j}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{1}j}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{n-1}j}\left|1\right>\right)\\
=\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right)
もしこのように書き表すことができれば逆量子フーリエ変換を施して、$j$ を取り出すことができます。
\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right) \xrightarrow{QFT^{-1}} j
これらから上の状態を作り出せることができれば良いことがわかります。
状態の作成
上の状態を作り出すために Hゲートを CUゲートを用います。
まずはじめの状態は $\left|00\cdots00\right> \otimes \left|u\right>$ とします。
$\left|00\cdots00\right>$ にHゲートを施すと以下のようになります。
H\left|0\right> \otimes H\left|0\right> \otimes \cdots \otimes H\left|0\right> = \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>)
ここで最初のビットの $\left|1\right>$ のみ $U$ を施すと $U\left|u\right> = e^{2\pi i 0.j_1j_2\cdots j_n}\left|u\right>$ より
\frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_1j_2\cdots j_n}\left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \left|u\right>
次に最初から 2番目のビットの $\left|1\right>$ に $U^{2^1}$ を施すと $U^{2^1}\left|u\right> = e^{2\pi i 0.j_2j_3\cdots j_n}\left|u\right>$ より
\frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_1j_2\cdots j_n}\left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_2j_3\cdots j_n}\left|1\right>) \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \left|u\right>
以下同様にして繰り返し、最後のビットの $\left|1\right>$ に $U^{2^{n-1}}$ を施すと $U^{2^{n-1}}\left|u\right> = e^{2\pi i 0.j_n}\left|u\right>$ より
\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right)
上手く状態を作ることができました。
まとめ
今回は量子位相推定( Quantum Phase Estimation )について説明しました。
次回は Bernstein-Vaziraniのアルゴリズムについて説明しようと思います。