#$\mathbb{F}_2$ 上的傅里叶变换

$f:\{0,1\}^n\rightarrow \{0,1\}$

$f(x)=\sum_{S\subseteq[n]}\widehat{f(S)}\chi_S(x)$

$\widehat{f(S)}=\langle f,\chi_S\rangle=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}f(x)\chi_S(x)$

$OR(x)=\frac{3}{4}-\frac{1}{4}\cdot(-1)^{x_0}-\frac{1}{4}\cdot(-1)^{x_1}-\frac{1}{4}\cdot(-1)^{x_0+x_1}$

$\chi_\sigma(x)=(-1)^{\sigma\cdot x}$

$f(x)=\sum_{\sigma\in\{0,1\}^n}\widehat{f(\sigma)}\chi_\sigma(x)$

\begin{aligned} \langle\chi_\sigma,\chi_\gamma\rangle&=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}\chi_\sigma(x)\chi_\gamma(x)\\ &=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{\sigma\cdot x+\gamma\cdot x}\\ &=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}\prod_{i,\sigma_i\oplus\gamma_i=1}(-1)^{x_i}\\ \end{aligned}

$\langle\chi_\sigma,\chi_\gamma\rangle=\begin{cases}1&\sigma=\gamma\\0&\sigma\neq\gamma\end{cases}$

$|\chi_\sigma\rangle=\frac{1}{\sqrt{2^n}} \begin{pmatrix} \chi_\sigma(0)\\ \chi_\sigma(1)\\ ...\\ \chi_\sigma(2^n-1) \end{pmatrix}$

$E_{i,j}=\frac{1}{\sqrt{2^n}}\sum_{\sigma\in\{0,1\}^n}\chi_\sigma(i)\chi_\sigma(j)=\frac{1}{\sqrt{2^n}}\sum_{\sigma\in\{0,1\}^n}\chi_i(\sigma)\chi_j(\sigma)=\delta_{i,j}$

$|f\rangle=\frac{1}{\sqrt{\sum_xf(x)^2}} \begin{pmatrix} f(0)\\ f(1)\\ ...\\ f(2^n-1) \end{pmatrix}$

\begin{aligned} |f\rangle&=I|f\rangle\\ &=\sum_{\sigma\in\{0,1\}^n}|\chi_\sigma\rangle\langle\chi_\sigma|f\rangle\\ &=\sum_{\sigma\in\{0,1\}^n}\langle\chi_\sigma|f\rangle|\chi_\sigma\rangle\\ \end{aligned}

$|f\rangle$$|\chi_\sigma\rangle$ 下的展开。

# Deutsch-Jozsa Algorithm

$U_f(|x\rangle|-\rangle)=(-1)^{f(x)}|x\rangle|-\rangle$

\begin{aligned} U_f\left (\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle\right )&=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}g(x)|x\rangle\\ &=|g\rangle\\ &=\sum_{\sigma\in\{0,1\}^n}|\chi_\sigma\rangle\langle\chi_\sigma|g\rangle \end{aligned}

$\langle \chi_0|g\rangle=\frac{1}{2^n}\sum_x\chi_0(x)g(x)=\frac{1}{2^n}\sum_xg(x)=\frac{1}{2^n}\sum_x(-1)^{f(x)}$

• 所以若$f(x)$ 为常函数，就会有$\langle\chi_0|g\rangle=\pm 1$

• 如果$f(x)$ is balanced，就会有$\sum_x(-1)^{f(x)}=0$。那么$\langle\chi_0|g\rangle=0$

Theorem.

$H^{\otimes n}|\chi_\sigma\rangle=|\sigma\rangle$

Proof:

\begin{aligned} H^{\otimes n}|\chi_\sigma\rangle&=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\chi_\sigma(x)H^{\otimes n}|x\rangle\\ &=\frac{1}{2^n}\sum_{x,y\in\{0,1\}^n}\chi_\sigma(x)\cdot(-1)^{x\cdot y}|y\rangle\\ &=\frac{1}{2^n}\sum_{x,y\in\{0,1\}^n}\chi_\sigma(x)\chi_y(x)|y\rangle\\ &=\sum_{y\in\{0,1\}^n}\langle\chi_\sigma|\chi_y\rangle|y\rangle\\ &=|\sigma\rangle \end{aligned}

$\square$.

# Simon’s algorithm

$U_f\left (\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|0\rangle\right )=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle$

$|f\rangle=\frac{1}{\sqrt{2}}(|x\rangle+|x\oplus s\rangle)$

\begin{aligned} \langle\chi_\sigma|f\rangle&=\frac{1}{\sqrt{2^{n+1}}}(\chi_\sigma(x)+\chi_\sigma(x\oplus s))\\ &=\frac{1}{\sqrt{2^{n+1}}}\left ((-1)^{\sigma\cdot x}+(-1)^{\sigma\cdot(x\oplus s)}\right )\\ &=\frac{1}{\sqrt{2^{n+1}}}(-1)^{\sigma\cdot x}\left (1 +(-1)^{\sigma\cdot s}\right ) \end{aligned}

$H^{\otimes n}|f\rangle=H^{\otimes n}\sum_{\sigma\in\{0,1\}^n}\langle\chi_\sigma|f\rangle|\chi_\sigma\rangle=\sum_{\sigma\in\{0,1\}^n}\langle\chi_\sigma|f\rangle|\sigma\rangle$

#$\mathbb{Z}_N$ 上的傅里叶变换

$|\chi_s\rangle=\frac{1}{\sqrt{N}}\begin{pmatrix} \chi_s(0)\\ \chi_s(1)\\ ...\\ \chi_s(N-1) \end{pmatrix}$

• $\chi_s(x)=\chi_x(s)$
• $\sum_{x=0}^{N-1}\chi_s(x)=\begin{cases}1 & s=0\\0& s\neq 0\end{cases}$。（单位根等比求和）
• $\langle\chi_s|\chi_t\rangle=\begin{cases}1&s=t\\0&s\neq t\end{cases}$
• $\chi_s(x)^*=\chi_s(-x)$
• $\sum_{s=0}^{N-1}|\chi_s\rangle\langle\chi_s|=I$

$|g\rangle=\frac{1}{\sqrt{\sum_{i=0}^{N-1}g(x)^2}}\begin{pmatrix} g(0)\\ g(1)\\ ...\\ g(N-1) \end{pmatrix}\\ |g\rangle=\sum_{s=0}^{N-1}\langle\chi_s|g\rangle|\chi_s\rangle$

$|g\rangle=|x\rangle+|x+s\rangle+|x+2s\rangle+...+|x+\left (\frac{N}{s}-1\right )s\rangle$

\begin{aligned} \langle\chi_\sigma|g\rangle&=\sum_{m=0}^{N/s-1}\chi_\sigma(x+ms)^*\\ &=\sum_{m=0}^{N/s-1}\omega^{-\sigma(x+ms)} \end{aligned}

• $\sigma s=0\mod N$，那么：

$\langle\chi_\sigma|g\rangle=\sum_{m=0}^{N/s-1}\omega^{-\sigma x}$

其实结果就是$\omega^{-\sigma x}$，因为$|g\rangle$ 前我们没有考虑归一化常数，而$\|\langle\chi_\sigma|g\rangle\|=1$ 应该。

• $\sigma s\neq 0\mod N$，假设$N$$s$ 的倍数，那么

$\langle\chi_\sigma|g\rangle=\omega^{-\sigma x}\sum_{m=0}^{N/s-1}\omega^{-\sigma ms}=0$

$\mathbb{Z}_N$ 上的量子傅里叶变换可以看作：

$\text{QFT}=\frac{1}{\sqrt{N}}\sum_{x,y=0}^{N-1}\chi_y(x)^*|y\rangle\langle x|$

\begin{aligned} \text{QFT}|g\rangle&=\text{QFT}\sum_{s=0}^{N-1}\langle\chi_s|g\rangle\sum_{x=0}^{N-1}\chi_s(x)|x\rangle\\ &=\sum_{x,y,s=0}^{N-1}\langle\chi_s|g\rangle\chi_s(x)\chi_y(x)^*|y\rangle\\ &=\sum_{y,s=0}^{N-1}\langle\chi_s|g\rangle\left (\sum_{x=0}^{N-1}\chi_{s-y}(x)\right )|y\rangle\\ &=\sum_{s=0}^{N-1}\langle\chi_s|g\rangle|s\rangle \end{aligned}

Edited on Views times