量子フーリエ変換と量子位相推定の証明

ネット上の証明に不満があったので，ここに量子フーリエ変換と量子位相推定の証明をかいておく．

量子計算機のアルゴリズムの計算は大変で．特に指数関数を全部書いてると数字が小さくなり，かっこが入れ子になり本質が見えなくなる．これから紹介する指数係数記法は二進数表記をさらに推し進めたもので，指数関数を楽に書き，操作していることの本質がわかりやすくなる手法．(だと個人的に思っている)

そこでこの指数係数表記を紹介したのちにそれの使用例として証明を行う．

指数係数表記

最初に定義から始める．

定義 指数係数 : $\{k_j\mid k_j\in\{0,1\}\}_j$ とする．$\{k_j\}_j$ を指数係数として持つ定数 $C$ の量子状態 $\psi$ とは，以下を満たすものをいう．ここで $[0.]$ は二進数表記．$\phi$ は適当な基底の元．( $\ket{000}$ とか)

$$\psi=\exp(iC[0.k_1k_2\cdots k_n])\phi.$$

さらに略記法として，定数 $C$ 指数係数 $\{k_j\}_j$ の量子状態 $\psi$ を次のように書く．

$$C[0.k_1k_2\cdots k_n]\phi.$$

あるいは $K=\sum_{j=1}^{n-1} k_j/2^j$ として

$$(C/2^n)[K]\phi.$$

• 二進数表記は，例えば $[0.11] = 2^{-1}+2^{-2}$ ということ．本稿では二進数表記はここでしか出てこないので注意．

指数係数の性質は以下のようである．

• 性質1 : 定数 $C$ 指数係数 $\{x_j\}$ の $\ket{x}=C[x_j]\ket{x'}$ と，定数 $C$ 指数係数 $\{y_j\}$ の $\ket{y}=C[y_j]\ket{y'}$ でテンソル積を取ると，定数 $C$ 指数係数 $\{x_j+y_j\}$ の量子状態 $\{x\}\otimes\ket{y}$ となる．つまり
  
  $$C[x_j]\ket{x'}\otimes C[y_j]\ket{y'}=C[x_j+y_j]\ket{x'}\otimes\ket{y'}.$$
• 性質2 : 定数 $C$ 指数係数 $\{x_j\}$ の $\ket{x}=C[0.x_1x_2\cdots x_n]\ket{x'}$ に $\exp(iCz/2^k)$ をかけると（$z=0\ or\ 1$），定数 $C$ 指数係数 $[0.x_1x_2\cdots x_k+z\cdots x_n]$ の量子状態になる．つまり
  
  $$\exp(iCz/2^k)\cdot C[0.x_1x_2\cdots x_n]\ket{x'} = C[0.x_1\cdots x_k+z\cdots x_n]\ket{x'}.$$
  
  繰り上がる場合もあり注意．

使用例

量子フーリエ変換アルゴリズム

最も代表的なアルゴリズムの一つであるこれの証明も，指数係数表記の性質を用いて楽になる．

アルゴリズム 量子フーリエ変換 :
量子フーリエ変換は，入力状態 $\ket{x_1x_2\cdots x_n}$ を以下の状態に変換するアルゴリズムである．ここで指数係数表記を利用した．

$$\begin{aligned}QFT(\ket{x_1x_2\cdots x_n})=&\frac{1}{\sqrt{N}}(\ket{0}+2\pi[0.x_n]\ket{1})\\&\otimes(\ket{0}+2\pi[0.x_{n-1}x_n]\ket{1})\\&\cdots\\&\otimes(\ket{0}+2\pi[0.x_1\cdots x_{n-1}x_n]\ket{1}).\end{aligned}$$

これを実現する量子回路は以下の通り．(Wikipediaから拝借してきた)

またこの回路中の $R_j$ は以下で定められる．

$$R_{j}=\begin{pmatrix}1&0\\0&\exp(2\pi i/2^j)\end{pmatrix}$$

では証明する．注意として，第一量子ビットの計算を完了したら，第二量子ビット以降では同じことをするだけなのでそれ以後は省略する．

1. まず，$\phi_1=\ket{x_1x_2\cdots}$ とする．($x_1,x_2,\cdots = 0\ or\ 1$)
2. $\ket{x_1}$ に$H$ を作用させる．その結果，状態は以下のようになる．ここで$C$は正規化定数．また$e^{\pi i} = -1$ を利用した．また指数係数表記を利用した．
   
   $$\begin{aligned}\phi_2=&C(\ket{0}+\exp(2\pi i x_1/2)\ket{1})\otimes\ket{x_2\cdots}\\=&C(\ket{0}+2\pi[0.x_1]\ket{1})\otimes\ket{x_2\cdots}.\end{aligned}$$
3. $\phi_2$ に 2ビット目を制御ビットとして $R_{2}$ を実行する．その結果，状態は以下のようになる．ここで指数係数記法の性質2を利用した．
   
   $$\phi_3 = C\{\ket{0}+\exp(2\pi x_2/2^2)\cdot 2\pi[0.x_1]\ket{1}\}\otimes\ket{x_2\cdots}\\=C\{\ket{0}+2\pi[0.x_1x_2]\ket{1}\}\otimes\ket{x_2\cdots}.$$
4. $\phi_3$ に nビット目まで $l$ ビット目を制御ビットとして $R_l$ を実行する．その結果，$l$ 桁目に加わることになるので状態は以下のようになる．
   
   $$\begin{aligned}\phi_4 = C\{\ket{0}+2\pi[0.x_1x_2\cdots x_n]\ket{1}\}\otimes\ket{x_2\cdots}.\end{aligned}$$
5. つぎにn-1ビットの(SWAPしない)QFTを $\ket{x_2}$ に実行する・・(省略)すると，以下のような感じになる．
   
   $$\begin{aligned}\phi_5=&C(\ket{0}+2\pi[0.x_1\cdots x_{n-1}x_n]\ket{1})\\&\cdots\\&\otimes(\ket{0}+2\pi[0.x_{n-1}x_n]\ket{1})\\&\otimes(\ket{0}+2\pi[0.x_n]\ket{1}).\end{aligned}$$
6. 最後にSWAPすると求めたいものになる．(自明)

このように，数式がすっきりして，また性質2でどこが増えていくのかわかりやすくなったと思う．

量子位相推定アルゴリズム

組み合わせを考える必要が出てくるが，これも指数係数記法の性質で考察が楽になる．

アルゴリズム 量子位相推定 : 量子位相推定は，オブザーバブル $U$ の固有状態 $\ket{\phi}$ の固有値 $\exp(2\pi i\theta)$ の $\theta$ を求めるアルゴリズムである．

これを実現する量子回路は以下の通り．(これもWikipediaから拝借してきた)

$CU$ は制御 U ゲートである．では，証明する．証明中，正規化係数は省略する．

1. まず $\phi_1 = \ket{++++\cdots}\otimes \ket{\phi}$ とする．
2. 一番端の $\ket{+}$ と$\ket{\phi}$ で $CU^0$ を実行する．その結果(性質2を用いて)
   
   $$\phi_2=\ket{+++\cdots}\otimes\{\ket{0}+2\pi\theta[0.]\ket{1}\}\otimes\ket{\phi}$$
3. さらに $CU^{2}$ から $CU^{2^n-1}$ まですると，
   
   $$\begin{aligned}\phi_3 =& \{\ket{0}+2\pi\theta[\overbrace{100\cdots}^{n桁}.]\ket{1}\}\\&\otimes\cdots\\&\otimes\{\ket{0}+2\pi\theta[10.]\ket{1}\}\\&\otimes\{\ket{0}+2\pi\theta[0.])\ket{1}\}\\&\otimes\ket{\phi}.\end{aligned}$$
   
   という感じになる．これは掛け算の組み合わせ的にみると，後ろから $j$ 番目の $\ket{0}+2\pi\theta[\overbrace{10\cdots}^{j桁}.]\ket{1}$ について，$\ket{0}$ を選ぶということはつまりテンソル積の $j$ 桁目が $\ket{0}$ になり，なおかつ指数係数の方も(性質1から) $j$ 桁目が 0 になるということである．ということなので，このように組み合わせをするとすべての桁の01のパターンを網羅するため，以下のように書き換えることができる．
   
   $$\phi_3=\sum_{K=0}^{2^n-1}2\pi\theta[K]\ket{K\phi}.$$
4. これに逆フーリエ変換すると，いい感じに打ち消してくれる．ここで量子フーリエ変換について再考する．あるオブザーバブル $A$ の固有状態 $\ket{x}$ に量子フーリエ変換を実行すると以下のようになる．
   
   $$\begin{aligned}QFT(\ket{x})&=\sum_{j=0}^{2^n-1} e^{jx}\ket{x}\\&=\sum_{j=0}^{2^n-1} \exp(2\pi ijx/2^n)\ket{x}\\&=\sum_{K=0}^{2^n-1}(2\pi x/2^n)[K]\ket{x}.\end{aligned}$$
   
   ゆえに固有状態 $\ket{2^n\theta}$ をフーリエ変換すると
   
   $$\begin{aligned}QFT(\ket{2^n\theta})=\sum_{K=0}^{2^n-1}(2\pi \theta)[K]\ket{x} .\end{aligned}$$
   
   よって $\phi_3$ に逆フーリエ変換を作用させると
   
   $$\begin{aligned}(QFT^{-1}\otimes I)\phi_3 &= (QFT^{-1}\otimes I)(QFT(\ket{2^n\theta})\otimes \phi)\\&= \ket{2^n\theta\phi}.\end{aligned}$$
   
   ゆえに
   
   $$\begin{aligned}\phi_4 = \ket{2^n\theta\phi}.\end{aligned}$$
5. この $\phi_4$ の $\ket{2^n\theta}$ は $A$ の固有状態なので，$A$ を基底 $\ket{2^n\theta}$ で観測すれば $2^n\theta$ が確率1で得られる．

指数係数についての所感

勝手に思いついただけなので先行者とかたぶんいるのでは？と思うし，たいして変わってない気もするけど，「性質」として使ったのはあんまりないような気もする．