今回、量子フーリエ変換アルゴリズムの解説をします。blueqatのサイトにはチュートリアルはありますが、n量子ビットにおける例はありませんでしたので、それを載せることにしました。
通常の古典計算機における高速フーリエ変換(Fast Fourier Transformation(FFT))においては入力データビット長に対して$ O(n2^n) $オーダーの処理が可能ですが、これでは入力データ列の増大に対して容易に計算不能な時間がかかるようになります。
しかし量子フーリエ変換を用いれば、$ O(logn) $オーダーで済みます。
まず、あらゆる波動は様々な周波数成分の重ね合わせで表現できます。これは光、音波に限らずあらゆる波動に共通です。フーリエ変換とは、波動におけるそれを構成する周波数成分に分解し、それぞれの振幅を周波数座標(スペクトル座標)に写像して調べるものです。その式は、
F(\omega)=\int_{-\infty}^{\infty}e^{-i\omega t}f(t)dt
となります。ここで$ \omega $は角振動数（rad/s)です。手計算ではこの式で周波数成分は完全に分解することができます。本来、これは時間範囲には負の無限から正の無限まで取らなければなりません。しかしながら、計算機は無限を扱えません。そのため、計算機においてはこれを行列演算に直して有限時間範囲のみの計算を行います。これは離散フーリエ変換(Discrete Fourier Transformation(DFT))と呼ばれる手法で、次の式で表されます。
F_j=\sum_{k=1}^{N}e^{-i2\pi jk/N}f_k.
ここで、kは時間、jは周波数、Nは時間範囲(データ長)に相当します。この際、周波数成分への分解が可能な周波数の限界は、スペクトルとして用意するデータ長の長さ(解像度)の半分です。この式における$ e^{-2i\pi jk/N} $を成分とする行列が離散フーリエ変換の行列です。しかしながら、この行列を生成し、作用させるにはデータ長に対して$ O(2^{2n}) $オーダーの時間がかかります。
古典計算機いおいてはこれを改善した高速フーリエ変換アルゴリズム(FFT)があります。処理時間は前述のように$ O(n2^n) $となり、現状古典計算機における最速のものです。しかしながら、これ以上の高速化は古典では実現していません。量子計算機において、これを高速で行うアルゴリズムが考案されました。それが量子フーリエ変換(Quantum Fourier Transform(QFT))です。これは量子計算機においてその計算方式と位相が簡単にゲートでくわえられることを利用したもので、O(logn)オーダーでの計算が可能です。その式は、2進小数、
k = 0.k_1 k_2 \cdots k_{n}=\sum_{i=1}\frac{k_i}{2^i}
を用いて、
\begin{align}
\mid j \rangle &=& \sum_{k=0}^{2^n-1}e^{-2i\pi jk/2^n-1}\mid k \rangle \\
&=& \sum_{k_1=0}^{1
}\sum_{k_2=0}^{1}\ldots\sum_{k_n}^{1}e^{-2i\pi j(2^{n-1}k_1+2^{n-2}k_2+\ldots +k_n)/2^n}\mid k_1 k_2 \ldots k_n \rangle \\
\end{align}
と表されます。
量子回路の上では $ R_l\mid 0 \rangle \rightarrow \mid 0 \rangle , R_l\mid 1
\rangle \rightarrow e^{-2i\pi / 2^l}\mid 1 \rangle $ 任意位相ゲートRを用いて図1のようにあらわされます。そうして、これを用いて4量子ビットで表された状態 $ \mid 000 0 \rangle $のQFT結果が図2のようになります。 付録 にはより様々な状態にフーリエ変換結果を載せました 。
それらからわかるように、波の幅が狭くなるほどにスペクトルには高周波数の周波数成分が現れるようになります。この関係を覚えておくといろいろなところで役立ちます。例えば、電子が座標標空間においては局在している場合、ハイゼンベルグの不確定性関係二よって波数空間においては広範囲にわたって存在しているなどです。
図1 量子フーリエ変換を実行する量子回路。
図2 $ \mid 000 0 \rangle $の量子フーリエ変換結果。●は各状態における係数の実部、+は虚部を表します。
QFTを用いることで、入力するデータの長さを容易く増大させることができるため、誤り耐性量子計算が世に出れば、一気に量子計算機の需要が拡大することが期待されています。それのみならず、これは量子位相推定など様々な誤り耐性量子計算機用量子アルゴリズムにおける様々なアルゴリズムで利用されているため、誤り耐性量子計算の基本と言えます。そろそろ誤り耐性量子計算機の研究が始まっているため、2年以内には世に出る可能性が高いです。それまでに、これをマスターすることを私は勧めます。