@yuichirominato 2018.08.04更新

量子フーリエ変換

アダマール変換 量子ゲート 量子フーリエ変換

はじめに

高速フーリエ変換(FFT)は、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる離散フーリエ変換(DFT)を計算機上で高速に計算するアルゴリズムですが、同様のものが量子フーリエ変換(QFT)として量子コンピュータ回路で実現できますので確認したいと思います。

離散フーリエ変換

離散フーリエ変換の式は下記の通りです。

$F(t) = \sum_{x=0}^{N-1}f(x)e^{-i\frac{2\pi t x}{N}}$

ちなみに逆離散フーリエ変換は下記の通りです。

$f(x) = \frac{1}{N}\sum_{t=0}^{N-1}F(t)e^{i\frac{2\pi xt}{N}}$

離散フーリエ変換の行列表記

まずは離散フーリエ変換をみてみます。入力に行列変換を行うことで、出力を得ます。
$N=4$の時、$W = e^{\frac{-2\pi i}{N}}$とおくと、

$$ \begin{align}
\left[
\begin{array}{r}
X_0\\
X_1\\
X_2\\
X_3
\end{array}
\right]
&=&
\left[
\begin{array}{rrrr}
W^0&W^0&W^0&W^0\\
W^0&W^1&W^2&W^3\\
W^0&W^2&W^4&W^6\\
W^0&W^3&W^6&W^9
\end{array}
\right]
\left[
\begin{array}{r}
x_0\\
x_1\\
x_2\\
x_3
\end{array}
\right]\\
&=&
\left[
\begin{array}{rrrr}
W^0&W^0&W^0&W^0\\
W^0&W^2&W^1&W^3\\
W^0&W^4&W^2&W^6\\
W^0&W^6&W^3&W^9
\end{array}
\right]
\left[
\begin{array}{r}
x_0\\
x_2\\
x_1\\
x_3
\end{array}
\right]\\
&=&
\left[
\begin{array}{rrrr}
W^0&W^0&W^0W^0&W^0W^0\\
W^0&W^2&W^1W^0&W^1W^2\\
W^0&W^0&W^2W^0&W^2W^0\\
W^0&W^2&W^3W^0&W^3W^2
\end{array}
\right]
\left[
\begin{array}{r}
x_0\\
x_2\\
x_1\\
x_3
\end{array}
\right]\\
&=&
\left[
\begin{array}{rrrr}
1&0&W^0&0\\
0&1&0&W^1\\
1&0&W^2&0\\
0&1&0&W^3
\end{array}
\right]
\left[
\begin{array}{rrrr}
W^0_2&W^0_2&0&0\\
W^0_2&W^1_2&0&0\\
0&0&W^0_2&W^0_2\\
0&0&W^0_2&W^1_2
\end{array}
\right]
\left[
\begin{array}{r}
x_0\\
x_2\\
x_1\\
x_3
\end{array}
\right]\\
&=&
\left[
\begin{array}{rrrr}
1&0&W^0&0\\
0&1&0&W^1\\
1&0&W^2&0\\
0&1&0&W^3
\end{array}
\right]
\left[
\begin{array}{rrrr}
F_2&\\
&F_2
\end{array}
\right]
\left[
\begin{array}{r}
x_0\\
x_2\\
x_1\\
x_3
\end{array}
\right]
\end{align} $$

こちらは$N=2$のフーリエ変換を再帰的に利用しています。

量子フーリエ変換

量子フーリエ変換は上記のベクトルの代わりに量子状態$\sum_{i=0}^{N-1}x_i\mid i\rangle$を入力として量子状態$\sum_{i=0}^{N-1}y_i\mid i \rangle$を得ます。

基底状態にあるときは、

$QFT:\mid x \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_n^{xk}\mid k\rangle$

ここで、$\omega_n = e^{\frac{2\pi i}{N}}$とすると、変換部分は、

$F_N=
\frac{1}{\sqrt{N}}
\left[
\begin{array}{rrrr}
1 & 1 & 1 & \cdots &1\\
1 & \omega_n&\omega_n^2&\cdots&\omega_n^{N-1}\\
1 & \omega_n^2&\omega_n^4&\cdots&\omega_n^{2(N-1)}\\
1 & \omega_n^3&\omega_n^6&\cdots&\omega_n^{3(N-1)}\\
\vdots&\vdots&\vdots&&\vdots\\
1 & \omega_n^{N-1}&\omega_n^{2(N-1)}&\cdots&\omega_n^{(N-1)(N-1)}
\end{array}
\right]
$

$F_2$はアダマールゲート、

$
F_2
=
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rr}
\omega^0&\omega^0\\
\omega^0&\omega^1
\end{array}
\right]
=
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rr}
1&1\\
1&-1
\end{array}
\right]
$

$F_4$は高速フーリエ変換と同様に変形したあと、$F_2$への再帰部分は$I$と$F_2$のテンソル積がとれて、その他行列は、回転ゲートとHゲートへ数学的に分解できる。大きなゲートになっても再帰的にどんどん計算が進む。

$$ \begin{align}
F_4
&=&
\frac{1}{\sqrt{4}}
\left[
\begin{array}{rrrr}
\omega^0&\omega^0&\omega^0&\omega^0\\
\omega^0&\omega^1&\omega^2&\omega^3\\
\omega^0&\omega^2&\omega^4&\omega^6\\
\omega^0&\omega^3&\omega^6&\omega^9
\end{array}
\right]\\
&=&
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rrrr}
1&0&\omega^0&0\\
0&1&0&\omega^1\\
1&0&\omega^2&0\\
0&1&0&\omega^3
\end{array}
\right]
\left[
\begin{array}{rrrr}
F_2&\\
&F_2
\end{array}
\right]\\
&=&
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rrrr}
1&0&\omega^0&0\\
0&1&0&\omega^1\\
1&0&\omega^0 \omega^2&0\\
0&1&0&\omega^1 \omega^2
\end{array}
\right]
\cdot
( I \otimes F_2 )\\
&=&
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rrrr}
1&0&1&0\\
0&1&0&1\\
1&0&-1&0\\
0&1&0&-1
\end{array}
\right]
\left[
\begin{array}{rrrr}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&\omega^1
\end{array}
\right]
\cdot
( I \otimes F_2 )\\
&=&
\frac{1}{\sqrt{2}}
\left[
\begin{array}{rr}
1&1\\
1&-1
\end{array}
\right]
\otimes
\left[
\begin{array}{rr}
1&0\\
0&1
\end{array}
\right]
\cdot
\left[
\begin{array}{rrrr}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&\omega^1
\end{array}
\right]
\cdot
( I \otimes F_2 )\\
&=&
( H \otimes I )
\cdot
\left[
\begin{array}{rrrr}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&\omega^1
\end{array}
\right]
\cdot
( I \otimes F_2 )
\end{align} $$

高速フーリエ変換実装例

高速フーリエ変換はpythonのnumpyを使うことで実装ができます。早速例題でやってみたいと思います。{0,1,0}という離散値をfftにかけてみます。

import numpy as np
print(np.fft.fft([0,1,0]))
[ 1. +0.j        -0.5-0.8660254j -0.5+0.8660254j]

このようになりました。高速フーリエ変換では、複素数が答えに出てきました。
再度これに逆高速フーリエ変換をかけてみて元に戻ることを確認してみたいと思います。

print(np.fft.ifft(np.fft.fft([0,1,0])))
[0.00000000e+00+0.j 1.00000000e+00+0.j 7.40148683e-17+0.j]

多少少数はずれますが、だいたい元に戻っています。

量子フーリエ変換

量子フーリエ変換は上記の高速フーリエ変換と同様ですが、量子状態を入力値として出力にも量子状態を得るのが特徴です。
回路は再帰的にQFTをかけて、実現できます。

ここで特徴的なのは量子状態を出力で得ますが、計算してみると、F4 = [[1,1,1,1],[1,1j,-1,-1j],[1,-1,1,-1],[1,-1j,-1,1j]]/2
なので、

print(1/2*np.array([[1,1,1,1],[1,1j,-1,-1j],[1,-1,1,-1],[1,-1j,-1,1j]])@np.array([0,0,0,1]))                                                                 
[ 0.5+0.j   0. -0.5j -0.5+0.j   0. +0.5j]

状態ベクトルで量子状態が取り出せそうですが、出現確率は1/4ずつなので、観測してもダメそうです。FFTで確認してみると、

np.fft.fft(np.array([0,0,0,1])/2)                                                                                                      
array([ 0.5+0.j ,  0. +0.5j, -0.5+0.j ,  0. -0.5j])

符号の問題はありますが、同じように出ました。

あわせて読みたい