離散フーリエ変換から量子フーリエ変換を導く

離散フーリエ変換と量子フーリエ変換の比較

前提
・$ii$は虚数単位$i=−1i=\sqrt{-1}$とする。
・$m,nm,n$は整数とする。
・$zz$が複素数であることを$z∈Cz\in\mathbb{C}$と書く。
・$⊤\top$は転置とする。例えば$(a b c)⊤=(abc)(a\;b\;c)^{\top}=\begin{pmatrix}a\\b\\c\end{pmatrix}$

離散フーリエ変換は次の定義です^[1]。

$$f^m=1N∑n=0N−1fnexp⁡(i2πmnN) \hat{f}_{m}=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}f_{n}\exp\left(i2\pi\frac{mn}{N}\right)$$

これは$fn∈Cf_{n}\in\mathbb{C}$というデータから$f^m∈C\hat{f}_{m}\in\mathbb{C}$というデータへのマッピングです。続いて量子フーリエ変換は次の定義です。

$$∣n⟩→1N∑m=0N−1exp⁡(i2πmnN)∣m⟩ |n\rangle\rightarrow\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle$$

両方とも似ていますね。ゆえに「これが量子版のフーリエ変換なのか～」と理解できそうですが、そもそも$f^m,fn\hat{f}_{m},f_{n}$は単なる複素数、$∣m⟩,∣n⟩|m\rangle,|n\rangle$はベクトルなので、そのまま数式を比較すると、二式を同一と捉えるのに違和感を覚えると思います。

本記事は如何にして量子フーリエ変換が上記定義で記述されているか、離散フーリエ変換の観点で説明してみようと思います。

ベクトルによる離散フーリエ変換の方法

最初に挙げた$fnf_{n}$ですが、これは

$$f=(f0 ⋯ fn ⋯ fN)⊤ \bm{f}=\left(f_{0}\;\cdots\;f_{n}\;\cdots\;f_{N}\right)^{\top}$$

というデータの集まりの一要素です。こういうデータの例としては音声信号があげられます。同様に$f^m\hat{f}_{m}$についても

$$f^=(f^0 ⋯ f^m ⋯ f^m)⊤ \hat{\bm{f}}=\left(\hat{f}_{0}\;\cdots\;\hat{f}_{m}\;\cdots\;\hat{f}_{m}\right)^{\top}$$

というデータの集まりの一要素です。実は離散フーリエ変換はデータをベクトル化すれば

$$f^=Wf \hat{\bm{f}}=W\bm{f}$$

と完結に記述することができます。この$WW$は行列で次の定義です。

$$W=1N(ω0⋅0ω0⋅1⋯ω0⋅(N−1)ω1⋅0ω1⋅1⋯ω1⋅(N−1)⋮⋮⋱⋮ω(N−1)⋅0ω(N−1)⋅1⋯ω(N−1)⋅(N−1)) 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}$$

特に

$$ω=exp⁡(i2πN) \omega=\exp\left(i\frac{2\pi}{N}\right)$$

は複素平面上の単位円を$NN$分割するという意味で回転子と呼ばれます。さらに$WW$はユニタリー行列で、$II$を単位行列とすれば、

$$WW†=I WW^{\dagger}=I$$

を満たします。$†\dagger$はダガーと呼び、行列の全要素の複素共役をとって転置してくださいという意味です。転置してから複素共役をとっても問題ないです。量子力学においてユニタリー行列は重要でありますが本記事では割愛します。

離散フーリエ変換の標準基底表現

標準基底とは次のベクトルを指します。

$$e0=(1 0 ⋯ 0)⊤,e1=(0 1 ⋯ 0)⊤,⋯ ,eN−1=(0 0 ⋯ 1)⊤ \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}$$

これらのベクトルの要素数は$NN$とします。標準基底の特徴は基底ベクトルになるだけでなく、基底同士が直交する点です。標準基底を使えば先ほどのデータ$f\bm{f}$は、

$$f=f0e0+f1e1+⋯+fN−1eN−1 \bm{f}=f_{0}\bm{e}_{0}+f_{1}\bm{e}_{1}+\cdots+f_{N-1}\bm{e}_{N-1}$$

と記述することができます。ここで、

$$ωm=(ωm⋅0 ωm⋅1 ⋯ ωm⋅(N−1))⊤ \bm{\omega}_{m}=(\omega^{m\cdot 0}\;\omega^{m\cdot 1}\;\cdots\;\omega^{m\cdot (N-1)})^{\top}$$

というベクトルを定義すれば$WW$は、

$$W=1N(ω0⊤ω1⊤⋮ωN−1⊤) W=\frac{1}{\sqrt{N}}\begin{pmatrix} \bm{\omega}_{0}^{\top} \\ \bm{\omega}_{1}^{\top} \\ \vdots \\ \bm{\omega}_{N-1}^{\top} \\ \end{pmatrix}$$

と書けます。試しに標準基底の$nn$番目のベクトル$en\bm{e}_{n}$に$WW$を作用させると、

$$Wen=1N[(ω0⊤en)e0+(ω1⊤en)e1+⋯+(ωN−1⊤en)eN−1] 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]$$

となります。特に、

$$ωm⊤en=ωm⋅n=exp⁡(i2πmnN) \bm{\omega}_{m}^{\top}\bm{e}_{n}=\omega^{m\cdot n}=\exp\left(i2\pi\frac{mn}{N}\right)$$

なので、

$$Wen=1N∑m=0N−1exp⁡(i2πmnN)em 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⟩|n\rangle$というベクトルの解説のみです。結論$∣n⟩|n\rangle$は量子力学上のベクトルの書き方でブラケット記法と呼びます。量子力学では量子状態をベクトルで記述する習慣があり、例えば$ψ\psi$という状態を

$$∣ψ⟩=c0∣0⟩+c1∣1⟩+⋯+cN−1∣N−1⟩ |\psi\rangle=c_{0}|0\rangle+c_{1}|1\rangle+\cdots+c_{N-1}|N-1\rangle$$

と書きます。量子の世界では状態が離散化されており、例えば光の粒である光子は、$00$個ある状態、$11$個ある状態・・・ととり得る状態が決まっています。

ただ量子の世界では実際に光子が何個存在しているか決定しているわけでなく、$00$個の時も、$11$個の時も、$nn$個の時も存在していると捉えます。これが状態の重ね合わせであり、$nn$個の光子がある状態を$∣n⟩|n\rangle$と書けば、$N−1N-1$の時まで重ね合わせた状態は上の$∣ψ⟩|\psi\rangle$になるというわけです^[2]。

この$∣n⟩|n\rangle$は$∣ψ⟩|\psi\rangle$とは違い、$nn$個あるという"単一"の状態を表します。これは固有状態と呼ばれます。任意の量子状態は固有状態で分解でき、固有状態は量子状態の基底ベクトルになります。そのような基底ベクトルとして次が挙げられます。

$$∣0⟩=(1 0 ⋯ 0)⊤,∣1⟩=(0 1 ⋯ 0)⊤,⋯ ,∣N−1⟩=(0 0 ⋯ 1)⊤ |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⟩=1N∑m=0N−1exp⁡(i2πmnN)∣m⟩ W|n\rangle=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle$$

と書けます。これが量子フーリエ変換の正体です。最初に紹介した定義は$∣n⟩|n\rangle$から$W∣n⟩W|n\rangle$に量子状態が変化したという意味で、

$$∣n⟩→1N∑m=0N−1exp⁡(i2πmnN)∣m⟩ |n\rangle\rightarrow\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(i2\pi\frac{mn}{N}\right)|m\rangle$$

と記述されていたわけです。

量子フーリエ変換をより詳しく

量子フーリエ変換において$WW$という文字はあまり使いません。よく見る書き方としては$QFTQFT$または$UQFTU_{QFT}$です。これは量子フーリエ変換の英訳 Quantum Fourier Transform の頭文字をとったものになります。以後$WW$ではなく$UQFTU_{QFT}$と記述することにします。

離散フーリエ変換で行った$fnf_{n}$から$f^m\hat{f}_{m}$のマッピングを量子フーリエ変換上で実施するにはどうすればよいでしょう？それこそ重ね合わせ状態を使う時で、

$$f=f0e0+f1e1+⋯+fN−1eN−1 \bm{f}=f_{0}\bm{e}_{0}+f_{1}\bm{e}_{1}+\cdots+f_{N-1}\bm{e}_{N-1}$$

と記述できたのと同じように、

$$∣f⟩=f0∣0⟩+f1∣1⟩+⋯+fN−1∣N−1⟩ |\bm{f}\rangle=f_{0}|0\rangle+f_{1}|1\rangle+\cdots+f_{N-1}|N-1\rangle$$

を量子フーリエ変換すれば良いです。つまり各固有状態にかかる係数が変換対象として埋め込めれば良いことになります。試しに変換すると、

$$UQFT∣f⟩=∑n=0N−1fnUQFT∣n⟩=∑n=0N−1fn1N∑m=0N−1exp⁡(i2πmnN)∣m⟩=∑m=0N−11N∑n=0N−1fnexp⁡(i2πmnN)∣m⟩ \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*}$$

より、

$$UQFT∣f⟩=∑m=0N−1f^m∣m⟩ \begin{align*} U_{QFT}|\bm{f}\rangle=\sum_{m=0}^{N-1}\hat{f}_{m}|m\rangle\\ \end{align*}$$

と各固有状態にかかる係数に、離散フーリエ変換の結果

$$f^m=1N∑n=0N−1fnexp⁡(i2πmnN) \hat{f}_{m}=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}f_{n}\exp\left(i2\pi\frac{mn}{N}\right)$$

が反映させられます。そしてこの結果に対して$UQFT†U_{QFT}^{\dagger}$を作用させると、$UQFTU_{QFT}$はユニタリー行列であることから、

$$UQFT†UQFT∣f⟩=I∣f⟩=∣f⟩ U_{QFT}^{\dagger}U_{QFT}|\bm{f}\rangle=I|\bm{f}\rangle=|\bm{f}\rangle$$

より、$UQFT†U_{QFT}^{\dagger}$は量子フーリエ変換の逆変換であることが分かります。具体的に逆変換は

$$UQFT†∣n⟩=1N∑m=0N−1exp⁡(−i2πmnN)∣m⟩ U_{QFT}^{\dagger}|n\rangle=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}\exp\left(-i2\pi\frac{mn}{N}\right)|m\rangle$$

と書けます。

最後に

本来、量子フーリエ変換はこんな回りくどい説明はしないのですが、どうしても疑問化して解決したかったのでこの記事を書きました。筆者と同じ境遇に陥った人に刺さってくれればいいなと思います。ありがとうございました！

脚注

1. 信号処理の分野ではこれは"逆"離散フーリエ変換になります。

2. 光子の場合、無限個ある状態まで重ね合わせられますが、分かりやすさを優先して$N−1N-1$までに絞っています。