量子フーリエ変換 by Yuichiro Minato

はじめに

高速フーリエ変換（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}

ビットを入力し、位相を量子状態で出力

量子フーリエ変換の入力は01のビットになります。これらのビット入力が位相の形で量子状態として出力されます。出力状態をテンソル積を用いて表現すると、

QFT(\mid x_1,x_2,…,x_n \rangle) = \frac{1}{\sqrt{N}}(\mid 0 \rangle + e^{2\pi i [0.x_n]} \mid 1 \rangle) \otimes … \otimes (\mid 0 \rangle + e^{2\pi i [0.x_1x_2…x_n]} \mid 1 \rangle)

[0.x_1x_2…] = \frac{x_1}{2}+\frac{x_2}{2^2}+…

位相にビットが現れた状態での量子状態が得られます。ここで注意したいのは、各量子状態の出現確率は確率振幅の二乗で表せられますが、どの量子状態も出現確率は同一なので測定を通じて位相が得られない点です。

numpyで高速フーリエ変換実装例

高速フーリエ変換は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]

[ 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]

[0.00000000e+00+0.j 1.00000000e+00+0.j 7.40148683e-17+0.j]

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

numpyで量子フーリエ変換

量子フーリエ変換は上記の高速フーリエ変換と同様ですが、量子状態を入力値として出力にも量子状態を得るのが特徴です。回路は再帰的に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]

[ 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])

array([ 0.5+0.j ,  0. +0.5j, -0.5+0.j ,  0. -0.5j])

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

blueqatで実装N=2

N=2の量子フーリエ変換回路は、

--H--Rz2-----
-----*----H--

Blueqatのコードで書くと、コントロール回転ゲートは、

--H----Rz(lambda/2)--X--Rz(-lambda/2)--X------
                     |                 |
---------------------*-----------------*---H--

lambdaにはmath.pi/2をいれます。


from blueqat import Circuit
import math
Circuit().x[0].x[1].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].h[1].run()

#array([ 5.00000000e-01+0.j , -8.32667268e-17-0.5j, -5.00000000e-01+0.j , 8.32667268e-17+0.5j])

array([ 0.35355339-0.35355339j, -0.35355339-0.35355339j,

       -0.35355339+0.35355339j,  0.35355339+0.35355339j])

前回の結果と比べてみますと、同じになってるのが確認できます。


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]

[ 0.5+0.j   0. -0.5j -0.5+0.j   0. +0.5j]

つぎに3量子ビット

次に3量子ビットを行なってみます。

--H--Rz2--Rz3-------------
-----*----|----H--Rz2-----
----------*-------*----H--

blueqatでは、


Circuit().x[:].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].rz(math.pi/8)[0].cx[2,0].rz(-math.pi/8)[0].cx[2,0].h[1].rz(math.pi/4)[1].cx[2,1].rz(-math.pi/4)[1].cx[2,1].h[2].run()

array([-0.13529903-0.32664074j, -0.32664074-0.13529903j,

       -0.32664074+0.13529903j, -0.13529903+0.32664074j,

        0.13529903+0.32664074j,  0.32664074+0.13529903j,

        0.32664074-0.13529903j,  0.13529903-0.32664074j])

array([-0.13529903-0.32664074j, -0.32664074-0.13529903j,
       -0.32664074+0.13529903j, -0.13529903+0.32664074j,
        0.13529903+0.32664074j,  0.32664074+0.13529903j,
        0.32664074-0.13529903j,  0.13529903-0.32664074j])

最後に4量子ビット

最後に4量子ビットでやってみます。

--H--Rz2--Rz3--Rz4--------------------------
-----*----|----|----H--Rz2--Rz3-------------
----------*----|-------*----|----H--Rz2-----
---------------*------------*-------*----H--

blueqatでは、


Circuit().x[:].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].rz(math.pi/8)[0].cx[2,0].rz(-math.pi/8)[0].cx[2,0].rz(math.pi/16)[0].cx[3,0].rz(-math.pi/16)[0].cx[3,0].h[1].rz(math.pi/4)[1].cx[2,1].rz(-math.pi/4)[1].cx[2,1].rz(math.pi/8)[1].cx[3,1].rz(-math.pi/8)[1].cx[3,1].h[2].rz(math.pi/4)[2].cx[3,2].rz(-math.pi/4)[2].cx[3,2].h[3].run()

array([-0.24519632+0.04877258j, -0.2078674 +0.13889256j,

       -0.13889256+0.2078674j , -0.04877258+0.24519632j,

        0.04877258+0.24519632j,  0.13889256+0.2078674j ,

        0.2078674 +0.13889256j,  0.24519632+0.04877258j,

        0.24519632-0.04877258j,  0.2078674 -0.13889256j,

        0.13889256-0.2078674j ,  0.04877258-0.24519632j,

       -0.04877258-0.24519632j, -0.13889256-0.2078674j ,

       -0.2078674 -0.13889256j, -0.24519632-0.04877258j])

array([-0.24519632+0.04877258j, -0.2078674 +0.13889256j,
       -0.13889256+0.2078674j , -0.04877258+0.24519632j,
        0.04877258+0.24519632j,  0.13889256+0.2078674j ,
        0.2078674 +0.13889256j,  0.24519632+0.04877258j,
        0.24519632-0.04877258j,  0.2078674 -0.13889256j,
        0.13889256-0.2078674j ,  0.04877258-0.24519632j,
       -0.04877258-0.24519632j, -0.13889256-0.2078674j ,
       -0.2078674 -0.13889256j, -0.24519632-0.04877258j])

numpyのfftでも確認してみました。元の定義の符号がFFTとQFTが異なっているので、共役をとっています。


print(np.fft.fft(np.array([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1])/4).conj())

[ 0.25      -0.j          0.23096988-0.09567086j  0.1767767 -0.1767767j

  0.09567086-0.23096988j  0.        -0.25j       -0.09567086-0.23096988j

 -0.1767767 -0.1767767j  -0.23096988-0.09567086j -0.25      -0.j

 -0.23096988+0.09567086j -0.1767767 +0.1767767j  -0.09567086+0.23096988j

  0.        +0.25j        0.09567086+0.23096988j  0.1767767 +0.1767767j

  0.23096988+0.09567086j]

[ 0.25      -0.j          0.23096988-0.09567086j  0.1767767 -0.1767767j
  0.09567086-0.23096988j  0.        -0.25j       -0.09567086-0.23096988j
 -0.1767767 -0.1767767j  -0.23096988-0.09567086j -0.25      -0.j
 -0.23096988+0.09567086j -0.1767767 +0.1767767j  -0.09567086+0.23096988j
  0.        +0.25j        0.09567086+0.23096988j  0.1767767 +0.1767767j
  0.23096988+0.09567086j]

以上でblueqatで実装ができました。

量子フーリエ変換

Yuichiro Minato

はじめに.css-1yssqf7{opacity:0.6;border:0;border-color:inherit;border-style:solid;border-bottom-width:1px;width:100%;margin-top:var(--chakra-space-2);}

離散フーリエ変換

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

量子フーリエ変換

ビットを入力し、位相を量子状態で出力

numpyで高速フーリエ変換実装例

numpyで量子フーリエ変換

blueqatで実装N=2

つぎに3量子ビット

最後に4量子ビット

はじめに