量子フーリエ変換
量子フーリエ変換とは、信号処理で使われる離散フーリエ変換を量子回路上に実装したものです。
離散フーリエ変換は、離散的（単位時間毎）に $N$ 回だけ物理量 $x_j$（$j=0,1,\cdots,N-1$）を測定した場合、以下で表すことができます。
$$x_j=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}X_ke^{2\pi ikj/N}$$
量子フーリエ変換は、この離散フーリエ変換（$x_j\to X_k$）を用いて、以下の変換で定義されます。
$$\sum_{j=0}^{N-1}x_j\ket{j} \to \sum_{k=0}^{N-1}X_k\ket{k}$$
このとき、状態ベクトルは以下のように変換されます。
$$\ket{j} \to \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ikj/N}\ket{k} －①$$
量子フーリエ変換を量子回路で実現するため、状態ベクトル $\ket{j}$ を量子ビットで表す必要があります。$N=2^n$ とし、10進法である $j$ を２進法で表すと、
$$j=j_1\cdot2^{n-1}+j_2\cdot2^{n-2}+\cdots+j_n\cdot2^0 －②$$
状態ベクトルは以下で置き替えます。
$$\ket{j}=\ket{j_1j_2\cdots j_n}=\ket{j_1}\otimes\ket{j_2}\otimes\cdots\otimes\ket{j_n}$$
n=4 の場合の変換
以下に、$n=4$（$N=2^4$）として①を計算すると以下のようになります。
$$\ket{j} \to \frac{1}{\sqrt{2^4}}\sum_{k=0}^{2^4-1}e^{2\pi ikj/2^4}\ket{k}$$$$=\frac{1}{4}\Big(\ket{0}+e^{2\pi i(0.j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_3j_4)}\ket{1}\Big)$$$$\otimes\Big(\ket{0}+e^{2\pi i(0.j_2j_3j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_1j_2j_3j_4)}\ket{1}\Big) －③$$
③を導く
$k$ を２進法に書き替えると、
$$\ket{j} \to \frac{1}{4}\sum_{k_1=0}^1\sum_{k_2=0}^1\sum_{k_3=0}^1\sum_{k_4=0}^1e^{2\pi ij(k_12^3+k_22^2+k_32^1+k_42^0)/2^4}\ket{k_1k_2k_3k_4}$$
指数部分を分解し、それぞれ和を取ると、
$$=\frac{1}{4}\sum_{k_1=0}^1e^{2\pi ijk_1/2}\ket{k_1}\otimes\sum_{k_2=0}^1e^{2\pi ijk_2/2^2}\ket{k_2}$$$$\otimes\sum_{k_3=0}^1e^{2\pi ijk_3/2^3}\ket{k_3}\otimes\sum_{k_4=0}^1e^{2\pi ijk_4/2^4}\ket{k_4}$$
$$=\frac{1}{4}\Big(\ket{0}+e^{2\pi ij/2}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi ij/2^2}\ket{1}\Big)$$$$\otimes\Big(\ket{0}+e^{2\pi ij/2^3}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi ij/2^4}\ket{1}\Big)$$
ここで、各指数部分に②を代入すると、
$$e^{2\pi ij/2}=e^{2\pi i(j_12^2+j_22+j_3+j_4/2)}=e^{2\pi i(j_4/2)}=e^{2\pi i(0.j_4)}$$
$$e^{2\pi ij/2^2}=e^{2\pi i(j_12+j_2+j_3/2+j_4/2^2)}=e^{2\pi i(j_3/2+j_4/2^2)}=e^{2\pi i(0.j_3j_4)}$$
$$e^{2\pi ij/2^3}=e^{2\pi i(j_1+j_2/2+j_3/2^2+j_4/2^3)}=e^{2\pi i(j_2/2+j_3/2^2+j_4/2^3)}=e^{2\pi i(0.j_2j_3j_4)}$$
$$e^{2\pi ij/2^4}=e^{2\pi i(j_1/2+j_2/2^2+j_3/2^3+j_4/2^4)}=e^{2\pi i(0.j_1j_2j_3j_4)}$$
これらより、③の結果が導かれます。
量子回路
量子フーリエ変換を実現する量子回路は以下になります。「$H$」はアダマールゲート、「$R_m$」は制御回転ゲートを表します。
アダマールゲートは、量子ビットに対し以下の変換を行います。
$$\ket{0}\to\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$$
$$\ket{1}\to\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$$
制御回転ゲートは、制御ビットが $\ket{0}$ のときはそのまま通し、$\ket{1}$ のときは以下の変換を行います。
$$\ket{0}\to\ket{0}$$
$$\ket{1}\to e^{2\pi i/2^m}\ket{1}$$
最後のスワップゲートは、以下のような量子ビットの入れ替えを行います。
$$\ket{j_1}\otimes\ket{j_2}\otimes\ket{j_3}\otimes\ket{j_4}\to\ket{j_4}\otimes\ket{j_3}\otimes\ket{j_2}\otimes\ket{j_1}$$
n=4 の場合の動作
$j_1$ ビットが各ゲートを通過（$H\to R_2\to R_3\to R_4$）した場合を計算します。まず、アダマールゲートで変換すると、
$$\ket{j_1j_2j_3j_4}=\frac{1}{\sqrt{2}}\Big(\ket{0}+e^{2\pi i(0.j_1)}\ket{1}\Big)\otimes\ket{j_2j_3j_4}$$
$R_2$ ゲートで変換すると、
$$=\frac{1}{\sqrt{2}}\Big(\ket{0}+e^{2\pi i(0.j_1j_2)}\ket{1}\Big)\otimes\ket{j_2j_3j_4}$$
続けて $R_3,R_4$ で変換すると、
$$=\frac{1}{\sqrt{2}}\Big(\ket{0}+e^{2\pi i(0.j_1j_2j_3j_4)}\ket{1}\Big)\otimes\ket{j_2j_3j_4}$$
$j_2$ ビットが各ゲートを通過（$H\to R_2\to R_3$）した場合を計算すると同様に、
$$=\frac{1}{\sqrt{2}}\Big(\ket{0}+e^{2\pi i(0.j_1j_2j_3j_4)}\ket{1}\Big)\otimes\frac{1}{\sqrt{2}}\Big(\ket{0}+e^{2\pi i(0.j_2j_3j_4)}\ket{1}\Big)\otimes\ket{j_3j_4}$$
従って $j_3$ ビットと $j_4$ ビットも計算すると以下になります。
$$=\frac{1}{\sqrt{2^4}}\Big(\ket{0}+e^{2\pi i(0.j_1j_2j_3j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_2j_3j_4)}\ket{1}\Big)$$$$\otimes\Big(\ket{0}+e^{2\pi i(0.j_3j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_4)}\ket{1}\Big)$$
最後にスワップゲートで変換すると、$j_1$ と $j_4$ 、$j_2$ と $j_3$ のビットが入れ替わるため、③が得られます。
$$=\frac{1}{\sqrt{2^4}}\Big(\ket{0}+e^{2\pi i(0.j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_3j_4)}\ket{1}\Big)$$$$\otimes\Big(\ket{0}+e^{2\pi i(0.j_2j_3j_4)}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i(0.j_1j_2j_3j_4)}\ket{1}\Big)$$
