量子フーリエ変換とは

/量子コンピュータ

量子フーリエ変換

量子フーリエ変換とは、信号処理で使われる離散フーリエ変換を量子回路上に実装したものです。

離散フーリエ変換は、離散的(単位時間毎)に $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$ を2進法で表すと、

$$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=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 i0.j_4}\ket{1}\Big)\otimes\Big(\ket{0}+e^{2\pi i0.j_3j_4}\ket{1}\Big)\otimes\cdots\otimes\Big(\ket{0}+e^{2\pi i0.j_1j_2j_3j_4}\ket{1}\Big)$$

③を導く

$k$ を2進法に書き替えると、

$$\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\cdots\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\cdots\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)}$$

$$\cdots$$

$$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}$$

 

数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

タイトルとURLをコピーしました