離散フーリエ変換と量子フーリエ変換の比較
離散フーリエ変換は次の定義です。
\hat{f}_{m}=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}f_{n}\exp\left(i2\pi\frac{mn}{N}\right)
これはf_{n}\in\mathbb{C}というデータから\hat{f}_{m}\in\mathbb{C}というデータへのマッピングです。続いて量子フーリエ変換は次の定義です。
|n\rangle\rightarrow\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle
両方とも似ていますね。ゆえに「これが量子版のフーリエ変換なのか～」と理解できそうですが、そもそも\hat{f}_{m},f_{n}は単なる複素数、|m\rangle,|n\rangleはベクトルなので、そのまま数式を比較すると、二式を同一と捉えるのに違和感を覚えると思います。
本記事は如何にして量子フーリエ変換が上記定義で記述されているか、離散フーリエ変換の観点で説明してみようと思います。
ベクトルによる離散フーリエ変換の方法
最初に挙げたf_{n}ですが、これは
\bm{f}=\left(f_{0}\;\cdots\;f_{n}\;\cdots\;f_{N}\right)^{\top}
というデータの集まりの一要素です。こういうデータの例としては音声信号があげられます。同様に\hat{f}_{m}についても
\hat{\bm{f}}=\left(\hat{f}_{0}\;\cdots\;\hat{f}_{m}\;\cdots\;\hat{f}_{m}\right)^{\top}
というデータの集まりの一要素です。実は離散フーリエ変換はデータをベクトル化すれば
と完結に記述することができます。このWは行列で次の定義です。
W=\frac{1}{\sqrt{N}}\begin{pmatrix}
\omega^{0\cdot 0} & \omega^{0\cdot 1} & \cdots & \omega^{0\cdot (N-1)}\\
\omega^{1\cdot 0} & \omega^{1\cdot 1} & \cdots & \omega^{1\cdot (N-1)}\\
\vdots & \vdots & \ddots & \vdots\\
\omega^{(N-1)\cdot 0} & \omega^{(N-1)\cdot 1} & \cdots & \omega^{(N-1)\cdot (N-1)}\\
\end{pmatrix}
特に
\omega=\exp\left(i\frac{2\pi}{N}\right)
は複素平面上の単位円をN分割するという意味で回転子と呼ばれます。さらにWはユニタリー行列で、Iを単位行列とすれば、
を満たします。\daggerはダガーと呼び、行列の全要素の複素共役をとって転置してくださいという意味です。転置してから複素共役をとっても問題ないです。量子力学においてユニタリー行列は重要でありますが本記事では割愛します。
離散フーリエ変換の標準基底表現
標準基底とは次のベクトルを指します。
\bm{e}_{0}=(1\;0\;\cdots\;0)^{\top},\bm{e}_{1}=(0\;1\;\cdots\;0)^{\top},\cdots,\bm{e}_{N-1}=(0\;0\;\cdots\;1)^{\top}
これらのベクトルの要素数はNとします。標準基底の特徴は基底ベクトルになるだけでなく、基底同士が直交する点です。標準基底を使えば先ほどのデータ\bm{f}は、
\bm{f}=f_{0}\bm{e}_{0}+f_{1}\bm{e}_{1}+\cdots+f_{N-1}\bm{e}_{N-1}
と記述することができます。ここで、
\bm{\omega}_{m}=(\omega^{m\cdot 0}\;\omega^{m\cdot 1}\;\cdots\;\omega^{m\cdot (N-1)})^{\top}
というベクトルを定義すればWは、
W=\frac{1}{\sqrt{N}}\begin{pmatrix}
\bm{\omega}_{0}^{\top} \\
\bm{\omega}_{1}^{\top} \\
\vdots \\
\bm{\omega}_{N-1}^{\top} \\
\end{pmatrix}
と書けます。試しに標準基底のn番目のベクトル\bm{e}_{n}にWを作用させると、
W\bm{e}_{n}=\frac{1}{\sqrt{N}}\left[(\bm{\omega}_{0}^{\top}\bm{e}_{n})\bm{e}_{0}+(\bm{\omega}_{1}^{\top}\bm{e}_{n})\bm{e}_{1}+\cdots+(\bm{\omega}_{N-1}^{\top}\bm{e}_{n})\bm{e}_{N-1}\right]
となります。特に、
\bm{\omega}_{m}^{\top}\bm{e}_{n}=\omega^{m\cdot n}=\exp\left(i2\pi\frac{mn}{N}\right)
なので、
W\bm{e}_{n}=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)\bm{e}_{m}
と記述することができます。これは標準基底を離散フーリエ変換した結果です。
量子フーリエ変換へ
準備が整いました。あとは|n\rangleというベクトルの解説のみです。結論|n\rangleは量子力学上のベクトルの書き方でブラケット記法と呼びます。量子力学では量子状態をベクトルで記述する習慣があり、例えば\psiという状態を
|\psi\rangle=c_{0}|0\rangle+c_{1}|1\rangle+\cdots+c_{N-1}|N-1\rangle
と書きます。量子の世界では状態が離散化されており、例えば光の粒である光子は、0個ある状態、1個ある状態・・・ととり得る状態が決まっています。
ただ量子の世界では実際に光子が何個存在しているか決定しているわけでなく、0個の時も、1個の時も、n個の時も存在していると捉えます。これが状態の重ね合わせであり、n個の光子がある状態を|n\rangleと書けば、N-1の時まで重ね合わせた状態は上の|\psi\rangleになるというわけです。
この|n\rangleは|\psi\rangleとは違い、n個あるという"単一"の状態を表します。これは固有状態と呼ばれます。任意の量子状態は固有状態で分解でき、固有状態は量子状態の基底ベクトルになります。そのような基底ベクトルとして次が挙げられます。
|0\rangle=(1\;0\;\cdots\;0)^{\top},|1\rangle=(0\;1\;\cdots\;0)^{\top},\cdots,|N-1\rangle=(0\;0\;\cdots\;1)^{\top}
あれ？と思いませんか？これは先ほど紹介した標準基底です。だったらそのまま離散フーリエ変換として応用が可能で、前節で示した結果を使えば、
W|n\rangle=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle
と書けます。これが量子フーリエ変換の正体です。最初に紹介した定義は|n\rangleからW|n\rangleに量子状態が変化したという意味で、
|n\rangle\rightarrow\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle
と記述されていたわけです。
量子フーリエ変換をより詳しく
量子フーリエ変換においてWという文字はあまり使いません。よく見る書き方としてはQFTまたはU_{QFT}です。これは量子フーリエ変換の英訳 Quantum Fourier Transform の頭文字をとったものになります。以後WではなくU_{QFT}と記述することにします。
離散フーリエ変換で行ったf_{n}から\hat{f}_{m}のマッピングを量子フーリエ変換上で実施するにはどうすればよいでしょう？それこそ重ね合わせ状態を使う時で、
\bm{f}=f_{0}\bm{e}_{0}+f_{1}\bm{e}_{1}+\cdots+f_{N-1}\bm{e}_{N-1}
と記述できたのと同じように、
|\bm{f}\rangle=f_{0}|0\rangle+f_{1}|1\rangle+\cdots+f_{N-1}|N-1\rangle
を量子フーリエ変換すれば良いです。つまり各固有状態にかかる係数が変換対象として埋め込めれば良いことになります。試しに変換すると、
\begin{align*}
U_{QFT}|\bm{f}\rangle&=\sum_{n=0}^{N-1}f_{n}U_{QFT}|n\rangle \\
&=\sum_{n=0}^{N-1}f_{n}\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle\\
&=\sum_{m=0}^{N-1}\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}f_{n}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle\\
\end{align*}
より、
\begin{align*}
U_{QFT}|\bm{f}\rangle=\sum_{m=0}^{N-1}\hat{f}_{m}|m\rangle\\
\end{align*}
と各固有状態にかかる係数に、離散フーリエ変換の結果
\hat{f}_{m}=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}f_{n}\exp\left(i2\pi\frac{mn}{N}\right)
が反映させられます。そしてこの結果に対してU_{QFT}^{\dagger}を作用させると、U_{QFT}はユニタリー行列であることから、
U_{QFT}^{\dagger}U_{QFT}|\bm{f}\rangle=I|\bm{f}\rangle=|\bm{f}\rangle
より、U_{QFT}^{\dagger}は量子フーリエ変換の逆変換であることが分かります。具体的に逆変換は
U_{QFT}^{\dagger}|n\rangle=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(-i2\pi\frac{mn}{N}\right)|m\rangle
と書けます。
最後に
本来、量子フーリエ変換はこんな回りくどい説明はしないのですが、どうしても疑問化して解決したかったのでこの記事を書きました。筆者と同じ境遇に陥った人に刺さってくれればいいなと思います。ありがとうございました！
Discussion