学群表示论时，对 Fourier basis 和 Fourier transformation 有了个理解。

学布尔函数分析时，有了新的理解。

学量子密码学时，又有了新的理解。

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

我们考虑一个布尔函数:

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

或者写为$f:\mathbb{F}^n_2\rightarrow\mathbb{F}_2$，即在有限域$\mathbb{F}_2$ 上考虑。

那么任何一个函数$f$ 都可以写为：

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

其中，$\chi_S(x)=\prod_{i\in S}(-1)^{x_i}=(-1)^{\sum_{i\in S}x_i}$。（实际上，$\chi(x)=(-1)^x$ 是$\mathbb{F}_2$ 的群特征标）而

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

被称为 Fourier coefficient of $f$ on $S$。

譬如考虑或函数：$OR:\{0,1\}^2\rightarrow\{0,1\}$，就有：

$$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}$$

然后如果我们用一个 01 串来表示$S$，就会有：

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

其中，$\sigma_i=1$ 表示$i\in S$，那么$\sigma\cdot x$（点乘）就其实等于$\sum_{i\in S}x_i$ 了。故原 Fourier expansion 写为：

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

我们其实可以证明，$\{\chi_\sigma\}$ 是正交的。因为：

$$\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}$$

实际上也就是，$\sigma,\gamma$ 如果第$i$ 位都为 1，那么$x_i$ 就会被算两遍。所以我们只考虑$\sigma_i\oplus\gamma_i=1$ 的那些位。又因为$x$ 遍历了所有$\{0,1\}^n$，所以就有：

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

---

我们推广上述的 Fourier expansion 到量子的情况。

因为恒有：$\chi_\sigma(x)^2=1$，因此我们定义单一化后的向量：

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

那么实际上有：$\sum_{\sigma\in\{0,1\}^n}|\chi_\sigma\rangle\langle\chi_\sigma|=I$。为什么呢？譬如令$E=\sum_{\sigma\in\{0,1\}^n}|\chi_\sigma\rangle\langle\chi_\sigma|$，那么：

$$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\otimes|b\rangle)=|x\rangle\otimes|b\oplus f(x)\rangle$，其中$f$ 的输出为$\{0,1\}$。那么有：

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

去掉辅助比特，也就是$U_f|x\rangle=(-1)^{f(x)}|x\rangle$。令$g(x)=(-1)^{f(x)}$，那么就有：

$$\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}$$

因为$\chi_0(x)=(-1)^{0\cdot x}= 1$，那么有：

$$\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$。

所以$f(x)$ 是常函数、或者$f(x)$ is balanced 分别对应了$U_f\left (\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle\right )$ 中，$|\chi_0\rangle$ 的概率幅度为 1，或者为 0 的情况。

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

假如说有一个函数$f(x)=f(x\oplus s)$，对于$y\neq x\oplus s$ 有$f(x)\neq f(y)$。那么:

$$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$$

那么我们不断测量$H^{\otimes n}|f\rangle$，策略出的结果$\sigma$ 一定满足$(-1)^{\sigma\cdot s}\neq -1$

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

对于$s,x\in\mathbb{Z}_N$，我们定义：$\chi_s(x)=\omega^{s\cdot x}$，其中$s\cdot x$ 是$\mathbb{Z}_N$ 上的乘法。而$\omega=e^{\frac{2\pi i}{N}}$。

然后向量类似：

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

那么这个 Fourier basis 也有类似的性质：

• $\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:\mathbb{Z}_n\rightarrow\mathbb{Z}_n$，我们也可以进行 Fourier expansion：

$$|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$$

---

我们看一下 Period-finding 问题。假如我们类似之前，作用$U_f$ 后测量第二寄存器，得到了如下状态（省略了归一化常数）：

$$|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$$

实际上，就算$N$ 不是$s$ 的倍数，都有$\langle\chi_\sigma|g\rangle\approx 0$，这个概率振幅会很小。

因此，如果在$|\chi_\sigma\rangle$ 下测量，测量结果巨大概率为$\sigma s=0\mod N$ 的那些$\sigma$。

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

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

那么给定$|g\rangle=\sum_{s=0}^{N-1}\langle\chi_s|g\rangle|\chi_s\rangle$，就有：

$$\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}$$

所以我们对$\text{QFT}|g\rangle$ 进行测量，测量的结果极大概率都是满足$\sigma s=0\mod N$ 的那些$\sigma$。