量子フーリエ変換 自分用まとめ

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

量子フーリエ変換(QFT)の自分用まとめ。フーリエ級数展開、フーリエ変換、離散フーリエ変換、量子フーリエ変換。

## フーリエ級数展開
[「8. フーリエ級数展開とフーリエ変換」](https://suzumushi0.hatenablog.com/entry/2017/07/02/095218)を参照

- **フーリエ級数展開 ($-\pi\sim\pi$の周期2$\pi$)**

```math
\begin{eqnarray}
f(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty} [a_n \mathrm{cos}(nt) + b_n \mathrm{sin}(nt)] \\
a_n = \frac{1}{\pi} \int_{-\pi}^{\pi} f(t) \mathrm{cos}(nt) dt \\
b_n = \frac{1}{\pi} \int_{-\pi}^{\pi} f(t) \mathrm{sin}(nt) dt
\end{eqnarray}
```

- **複素フーリエ級数展開 ($-\pi\sim\pi$の周期2$\pi$)**

```math
\begin{eqnarray}
f(t) = \sum_{n=-\infty}^{\infty} c_n e^{int} \\
c_n = \frac{1}{2\pi} \int_{-\pi}^{\pi} f(t) e^{-int} dt
\end{eqnarray}
```

- **複素フーリエ級数展開 ($-L\sim L$の周期2$L$)**

```math
\begin{eqnarray}
f(t) = \sum_{n=-\infty}^{\infty} c_n e^{i\frac{n\pi}{L}t} \\
c_n = \frac{1}{2L} \int_{-L}^{L} f(t) e^{-i\frac{n\pi}{L}t} dt
\end{eqnarray}
```




## フーリエ変換 
[「フーリエ級数とフーリエ展開」](https://www.kspub.co.jp/download/1565401b.pdf)を参照。
$L\rightarrow \infty$で無限周期関数を扱えるようにするよ
まず$c_n$を代入して、

```math
\begin{eqnarray}
f(t) = \sum_{n=-\infty}^{\infty} \frac{1}{2L} \int_{-L}^{L} f(t') e^{-i\frac{n\pi}{L}t'} dt' \, e^{i\frac{n\pi}{L}t}
\end{eqnarray}
```
$\omega_n = \frac{n\pi}{L}$ として、$\frac{1}{2L} = \frac{1}{2\pi} (\omega_{n+1}-\omega_{n}) \simeq \frac{1}{2\pi} d\omega$により、

```math
\begin{eqnarray}
f(t) &=& \sum_{n=-\infty}^{\infty} \frac{d\omega}{2\pi} \int_{-\infty}^{\infty} f(t') e^{-i\omega t'} dt' \, e^{i\omega t} \\
&=& \frac{1}{2\pi} \int_{-\infty}^{\infty} [\int_{-\infty}^{\infty} f(t') e^{-i\omega t'} dt'] e^{i\omega t} d\omega
\end{eqnarray}
```
級数展開の式における周波数成分$c_n$にあたる部分を抜き出して、

```math
\begin{eqnarray}
F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i\omega t} dt
\end{eqnarray}
```
これがフーリエ変換の式となる。




## 離散フーリエ変換
- **離散時間フーリエ変換**

[「5. 離散時間フーリエ変換」](http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/dtft.html)を参照。
関数$f(t)$が離散的である場合を考える。デルタ関数を用いて

```math
\begin{eqnarray}
f(t) = \sum_{n=-\infty}^{\infty} f[n] \delta(t-n)
\end{eqnarray}
```
と表すと、

```math
\begin{eqnarray}
F(\omega) &=& \int_{-\infty}^{\infty} f(t) e^{-i\omega t} dt \\
&=& \int_{-\infty}^{\infty} \sum_{n=-\infty}^{\infty} f[n] \delta(t-n) e^{-i\omega t} dt \\
&=& \sum_{n=-\infty}^{\infty} f[n] \int_{-\infty}^{\infty} \delta(t-n) e^{-i\omega t} dt \\
&=& \sum_{n=-\infty}^{\infty} f[n] e^{-i\omega n}
\end{eqnarray}
```
逆変換は、一周期のみ積分で

```math
\begin{eqnarray}
f[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} F(\omega) e^{i \omega n} d\omega
\end{eqnarray}
```


- **離散時間・離散周波数フーリエ変換**

[「6. 離散フーリエ変換」](http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/dft.html)を参照。
離散時間フーリエ変換では、離散信号$f(x)$から周期$2\pi$の連続周期信号$F(\omega)$が生成された。逆変換では$F(\omega)\rightarrow f(x)$であるが積分計算を行うことになる。これを避けるために$F(\omega)$も離散的であるような変換が欲しい。離散信号$f(x)$を定義域外で周期的に続いていく信号と考える。周期N点の離散信号$f(x)$は周期$2\pi$の離散信号$F(\omega)$に変換される。$F(\omega)$は$\frac{2\pi}{N}$間隔で離散化される。
![img463.png](https://qiita-image-store.s3.amazonaws.com/0/230477/6e09c278-15a1-0763-8ed0-15e558737340.png)
![img464.png](https://qiita-image-store.s3.amazonaws.com/0/230477/97caf388-ea7b-e736-0ab0-e3290c77a584.png)

離散周期信号$F(\omega) = \sum_{k=-\infty}^{\infty} c_k \delta (\omega-\frac{2\pi k}{N})$と表すと、逆変換は

```math
\begin{eqnarray}
f[n] &=& \frac{1}{2\pi} \int_{-\pi}^{\pi} \sum_{k=-\infty}^{\infty} c_k \delta(\omega - \frac{2\pi k}{N}) e^{i\omega n} d\omega \\
&=& \frac{1}{2\pi} \sum_{k=0}^{N-1} c_k e^{i \frac{2\pi kn}{N}} \\
&=& \frac{1}{N}  \sum_{k=0}^{N-1} F[k] e^{i \frac{2\pi kn}{N}} \,\,\, (n = 0, 1, \cdots , N-1) \\
\end{eqnarray}
```
順変換は、

```math
\begin{eqnarray}
F[k] &=& \sum_{n=0}^{N-1} f[n] e^{-i \frac{2\pi kn}{N}} \,\,\, (k = 0, 1, \cdots , N-1)
\end{eqnarray}
```


順変換を行列表記すると、

```math
\begin{eqnarray}

\begin{pmatrix}
F_0 \\ F_1 \\ F_2 \\ \cdot \\ \cdot \\ \cdot \\ F_{N-1}
\end{pmatrix}
=
\frac{1}{\sqrt{N}}
\begin{pmatrix}
e^{-i \frac{2\pi}{N} 0\cdot0} & e^{-i \frac{2\pi}{N} 0\cdot1} & \cdot & \cdot & \cdot & e^{-i \frac{2\pi}{N} 0\cdot (N-1)}  \\
e^{-i \frac{2\pi}{N} 1\cdot0} & e^{-i \frac{2\pi}{N} 1\cdot1} \\
\cdot \\
\cdot \\
\cdot \\
e^{-i \frac{2\pi}{N} (N-1)\cdot0} & \cdot & \cdot & \cdot& \cdot & \cdot
\end{pmatrix}

\begin{pmatrix}
f_0 \\ f_1 \\ f_2 \\ \cdot \\ \cdot \\ \cdot \\ f_{N-1}
\end{pmatrix}


\end{eqnarray} 
```



## 量子フーリエ変換
[「量子コンピュータ入門(宮野+古澤)」](https://www.amazon.co.jp/dp/4535788057/ref=asc_df_45357880572512887/?tag=jpgo-22&creative=9303&creativeASIN=4535788057&linkCode=df0&hvadid=295681864682&hvpos=1o1&hvnetw=g&hvrand=16342351750706532816&hvpone=&hvptwo=&hvqmt=&hvdev=c&hvdvcmdl=&hvlocint=&hvlocphy=1009279&hvtargid=pla-590239702277&th=1&psc=1)、[「量子フーリエ変換 (Quantum Fourier Transform) とは」](https://whyitsso.net/physics/quantum_mechanics/QFT.html)を参照。

### 目標

まず離散フーリエ変換を少し定義し直す(上2つの文献ではマイナス無しの方を順変換扱いしている、QCEngineではマイナスの方を順変換使いしてしているので注意)。

```math
\begin{eqnarray}
F_k &=& \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} f_n e^{i \frac{2\pi kn}{N}} \,\,\, (k = 0, 1, \cdots , N-1)
\end{eqnarray}
```

量子フーリエ変換で目指すところは、ある量子状態$\ket{x}$

```math
\begin{eqnarray}
\ket{x} &=& x_0\ket{00}+x_1\ket{01}+x_2\ket{10}+x_3\ket{11} \\
&=& x_0\ket{0}+x_1\ket{1}+x_2\ket{2}+x_3\ket{3} \\
&=& \sum_{j=0}^{N-1} x_j \ket{j}
\end{eqnarray}
```
が量子回路に入力されたとして、$x_j$の数値列$[x_0, x_1, x_2, x_3, \cdots]$を離散フーリエ変換した数値列$y_k=[y_0, y_1, y_2, y_3, \cdots]$

```math
\begin{eqnarray}
y_k &=& \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{i \frac{2\pi kj}{N}}
\end{eqnarray}
```
を求めることである。直接$y_k$を出力することは出来ないので、出力が

```math
\begin{eqnarray}
\ket{y} &=& \sum_{k=0}^{N-1} y_k \ket{k}
\end{eqnarray}
```
となるように基底$\ket{j}$を$\ket{k}$に変換することを目標とする。

定義を代入すると、

```math
\begin{eqnarray}
\ket{y} &=& \sum_{k=0}^{N-1} \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_j e^{i \frac{2\pi kj}{N}} \ket{k} \\
&=& \sum_{n=0}^{N-1} x_j \{ \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2\pi kj}{N}} \ket{k}\}  \\
となり、\\
\ket{x} &=& \sum_{j=0}^{N-1} x_j \ket{j}
\end{eqnarray}
```
と見比べると、

```math
\begin{eqnarray}
\ket{j} \rightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2\pi kj}{N}} \ket{k}\
\end{eqnarray}
```
の基底変換が達成出来れば、自動的に$\ket{y}$の係数$y_k$は$x_j$の離散フーリエ変換となることがわかる。


### アルゴリズムの導出
$N=2^n$とする。状態$\ket{k} = \ket{k_0} \otimes \ket{k_1} \otimes \ket{k_2} \cdots \otimes \ket{k_{n-1}}$のn個量子ビットで表現されているとし、$k=2^{n-1}k_{n-1}+ \cdots + 2^0k_0$の2進数に対応すると決める(古澤本では並びが逆)。

```math
\begin{eqnarray}
\ket{j} &\rightarrow& \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i \frac{2\pi kj}{N}} \ket{k} \\
&=& \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i \frac{2\pi kj}{2^n}} \ket{k} \\
&=& \frac{1}{\sqrt{2^n}} \sum_{k_0=0}^{1} \sum_{k_1=0}^{1} \cdots \sum_{k_{n-1}=0}^{1} e^{i \frac{2\pi}{2^n}j(2^{n-1}k_{n-1}+ \cdots + 2^0k_0)} \ket{k_0} \otimes \ket{k_1} \otimes \ket{k_2} \cdots \otimes \ket{k_{n-1}} \\
&=& \frac{1}{\sqrt{2^n}} (\sum_{k_0=0}^{1} e^{i \frac{2\pi}{2^n}j(2^0k_0)} \ket{k_0}) \otimes \cdots \otimes (\sum_{k_0=0}^{1} e^{i \frac{2\pi}{2^n}j(2^{n-1}k_{n-1})} \ket{k_{n-1}}) \\
&=& \frac{1}{\sqrt{2^n}} (\ket{0} + e^{i2\pi \frac{j}{2^n}} \ket{1}) \otimes \cdots \otimes (\ket{0} + e^{i2\pi \frac{j}{2}} \ket{1}) \\
&=& \frac{1}{\sqrt{2^n}} (\ket{0} + e^{i2\pi 0.j_{n-1}j_{n-2}\cdots j_0} \ket{1}) \otimes \cdots \otimes (\ket{0} + e^{i2\pi 0.j_0}\ket{1} ) \\
\end{eqnarray}
```
ここで、$j$(10進数)$=j_{n-1}j_{n-2}\cdots j_0$(２進数)であり、例えば$j/2$(10進数)$=j_{n-1}.j_{n-2}\cdots j_0$(2進数)で整数部分は$e^{i2\pi}$によって消滅して少数部分が残る事実を使った。

### 量子回路での実装
- **1qubitの場合**

n=1、$\ket{j}=\ket{j_0}$であり、

```math
\begin{eqnarray}
\ket{j_0} \rightarrow \frac{1}{\sqrt{2}} (\ket{0} + e^{i2\pi 0.j_0}\ket{1})
\end{eqnarray}
```
つまり、

```math
\begin{eqnarray}
\ket{0} \rightarrow \frac{1}{\sqrt{2}} (\ket{0} + \ket{1}) \\
\ket{1} \rightarrow \frac{1}{\sqrt{2}} (\ket{0} - \ket{1})
\end{eqnarray}
```
を実現すればよい。アダマールゲートのみで一発。

- **2qubitの場合**


<div align="center">
<img src="https://qiita-image-store.s3.amazonaws.com/0/230477/14e904aa-f2aa-5783-51ae-ac562fd9b373.png" width=50%>
</div>
n=2、$\ket{j}=\ket{j_0} \otimes \ket{j_1}$であり、

```math
\begin{eqnarray}
\ket{j_0} \otimes \ket{j_1} \rightarrow \frac{1}{2} (\ket{0} + e^{i2\pi 0.j_1j_0}\ket{1}) \, (\ket{0} + e^{i2\pi 0.j_0}\ket{1})
\end{eqnarray}
```
を実現すればよい。

まずは$j_1$に対してアダマールゲートをかけると、

```math
\begin{eqnarray}
\ket{j_0} \otimes \ket{j_1} \rightarrow \frac{1}{\sqrt 2} \ket{j_0} \otimes (\ket{0} + e^{i2\pi 0.j_1}\ket{1})
\end{eqnarray}
```
次に$j_0$が1の時に位相ファクター$e^{i2\pi/4}$を$j_1$に作用させるようなcontrolled-R1ゲートを作用させると$0.j_1j_0$が作れる、

```math
\begin{eqnarray}
\ket{j_0} \otimes \ket{j_1} \rightarrow \frac{1}{\sqrt 2} \ket{j_0} \otimes (\ket{0} + e^{i2\pi 0.j_1j_0}\ket{1})
\end{eqnarray}
```
あとは$j_0$にアダマールゲートをかけると

```math
\begin{eqnarray}
\ket{j_0} \otimes \ket{j_1} \rightarrow \frac{1}{\sqrt 2} (\ket{0} + e^{i2\pi 0.j_0}\ket{1}) \otimes (\ket{0} + e^{i2\pi 0.j_1j_0}\ket{1})
\end{eqnarray}
```
順番が逆転しているのでSWAPゲートを最後にかける。

- **QCEngineでの回路実装**

QCEngineでは逆QFTが$e^{ikx}$の方に対応しているので注意。また、関数として用意されている`.QFT();`および`.invQFT();`はswap変換を行ってくれないので手動で行う必要がある。
<img width="537" alt="Screen Shot 2018-10-14 at 19.25.15.png" src="https://qiita-image-store.s3.amazonaws.com/0/230477/b01ad6bc-0636-fdb7-72ae-2633080e643b.png">

以下にQCEngineで使用したコードを示す。

```C++
qc_options.color_by_phase = true;

qc.reset(2);
var a = qint.new(2, 'a');
qc.codeLabel('状態|1>');
a.write(1);
qc.codeLabel();

qc.nop();
qc.codeLabel('invQFT');
a.invQFT();
qc.codeLabel();

qc.codeLabel('SWAP');
a.exchange();
qc.codeLabel();
```