量子傅里叶变换、隐含子群和特征标

爱是充实了的生命，正如盛满了酒的酒杯。

# 隐含子群问题

• 例 1：若给定群$G=\langle \{0,1\}^n,\oplus\rangle$，$f$ 为一个函数满足$f(x)=f(x\oplus s)$。那么如果有一个计算$f$ 的黑盒，我们想求$s$，就相当于求子群$K=\{0,s\}$。
• 例 2：离散对数问题。给定群$G=\langle \mathbb{Z}_r\times\mathbb{Z}_r,+(mod\;r)\rangle$，和函数$f$ 满足$f(x_1,x_2)=a^{x_1}b^{x_2}$。那么要求$s=log_ab$ 的话（模$r$ 意义），那么就相当于求解一个子群：$K=\langle\{(l,-ls)\;|\;l\in\mathbb{Z}_r\},+(mod\;r)\rangle$，其实也就是这个周期是一个二维的。

我们下面只考虑有限 Abel 群上的隐含子群问题。而有限 Abel 群的特点是：

1. 有限 Abel 群的不可约表示是一维的。即我们只考虑群表示$\rho:G\rightarrow GL(1,\mathbb{C})$。其中$\mathbb{C}$ 是复数域。

2. 有限 Abel 群的特征标也是有限的。因为群中元素的阶都是有限的，譬如$a^r=e$，那么对于特征标$\chi:G\rightarrow\mathbb{C}$ 就会有$\chi(a)^r=\chi(a^r)=\chi(e)=1$。这样的话$\chi(a)$ 就只能选择$r$ 次单位根，只有有限种选择。

   此外我们进一步限制只讨论生成有限 Abel 群，如果没有生成元而只有一个生成元集合（譬如$\mathbb{Z}_r\times\mathbb{Z}_r$ 只能用$\{(1,0),(0,1)\}$ 生成），那么该群一定同构于若干个生成群的直积，其实不影响讨论。

• 例：考虑群$\{1,a,a^2\}$，其中$a^3=1$。那么它可能的特征标只有三个选择：

  $$\chi(a)^3=1\Rightarrow\\ \begin{aligned} &\chi_0:\begin{cases} \chi_0(a)=e^{2\pi i\cdot 0}\\ \chi_0(a^2)=\chi_1(a)^2=e^{2\pi i\cdot 2\cdot0}\\ \chi_0(1)=\chi_1(a^3)=e^{2\pi i\cdot 3\cdot0}=1\\ \end{cases}\\ & \chi_1:\begin{cases} \chi_1(a)=e^{2\pi i/3}\\ \chi_1(a^2)=e^{4\pi i/3}\\ \chi_1(1)=e^{6\pi i/3}=1\\ \end{cases}\\ & \chi_2:\begin{cases} \chi_2(a)=e^{4\pi i/3}\\ \chi_2(a^2)=e^{2\pi i/3}\\ \chi_2(1)=e^{6\pi i/3}=1\\ \end{cases} \end{aligned}$$

  故可以记为：

  $$\chi_j(a)=e^{2\pi ij/3}$$

然后我们把特征标$\chi_j$ 构成的群记为对偶群，$\hat{G}$，其中$j$ 表示了是第几个单位根。当然，当$G$ 是若干个群的直积，那么$j=(j_1,j_2,...,j_n)$ 也可以。其中$j_i$ 表示第$i$ 个循环群的生成元是第几个单位根。所以如果$G$ 的生成元记为$a$，那么它的阶就是$|G|$，那么就有：

$$\chi_j(a)=e^{2\pi ij/|G|}$$

# 量子傅里叶变换

然后我们定义群$G$ 上的量子傅里叶变换（Quantum Fourier Transformation，QFT，推广形式）为：

$$F_G:=\frac{1}{\sqrt{|G|}}\sum_{x\in G}\sum_{y\in\hat{G}}\chi_y(x)|y\rangle\langle x|$$

其中我们狭义一点，那就令有限生成 Abel 群$G$ 为$\mathbb{Z}_N$（实际上有限生成 Abel 群都同构于$\mathbb{Z}_N$），那么$\chi_y$ 中的$y$ 意思就是$\chi_y(x)=e^{2\pi ixy/N}$，那就得到了最常见的 Fourier Transformation 的形式。进一步地，因为$G\cong\hat{G}$，实际上可以用$G$ 中的元素对应$\hat{G}$ 中的元素。

• 例：在隐含子群问题的例 1 中，$G=\mathbb{Z}_2^n$，那么生成元为$(0,...,0,1),(0,...,1,0),...,(1,...,0,0)$ 共$n$ 个。而且每个生成元在自己的循环群$\mathbb{Z}_2$ 中的阶都是 2。那么$y$ 也是一个长度为$n$ 的二进制串，第$i$ 为为 1 表示第$i$ 个生成元取第 1 个单位根，否则就取第 0 个单位根。那么$\chi_y(x)=(-1)^{x\oplus y}$。

  譬如$n=2,x=11=01\oplus 10$（在生成元下分解），那么如果$y=11$，则$\chi_y(x)=\chi_y(01)\chi_y(10)=e^{2\pi i/2}\cdot e^{2\pi i/2}=1$，因为$01$ 和$10$ 都对应了第 1 个二次单位根，也就是$e^{2\pi i/2}$。最终也就是$\chi_y(x)=(-1)^{x\oplus y}$。

  所以

  $$F_G=\frac{1}{\sqrt{2^n}}\sum_{x,y\in\mathbb{Z}_2^n}(-1)^{x\oplus y}|y\rangle\langle x|$$

  就是 Simon 算法的 QFT。

---

下面回到隐含子群问题。假设我们可以用某种方法（往往就是 Hadamard 变换）制得一个群$G$ 上的均匀叠加态：

$$|G\rangle=\frac{1}{\sqrt{|G|}}\sum_{x\in G}|x\rangle$$

然后施加一个计算函数值的 oracle：

$$\rightarrow \frac{1}{\sqrt{|G|}}\sum_{x\in G}|x\rangle|f(x)\rangle$$

然后我们只看第一寄存器，即取 partial trace，由于原态是一个纠缠态，所以第一寄存器是一个混合态，有：

$$\begin{aligned} \rho&=\frac{1}{|G|/|H|}\sum_{g\in G/H}(\frac{1}{\sqrt{|H|}}\sum_{h\in H}|g+h\rangle\frac{1}{\sqrt{|H|}}\sum_{h\in H}\langle g+h|)\\ &=\frac{1}{|G|}\sum_{g\in G/H,h_1,h_2\in H}|g+h_1\rangle\langle g+h_2| \end{aligned}$$

我们记$|g+H\rangle=\frac{1}{\sqrt{|H|}}\sum_{h\in H}|g+h\rangle$ 是一个纯态，是均匀叠加在陪集$g+H$ 上的。但是不同陪集间是混合的。

然后我们直接作用 QFT：

$$\begin{aligned} F_G\rho F_G^\dagger&=\frac{1}{|G|^2}\sum_{g\in G/H,h_1,h_2\in H}\sum_{x_1,x_2\in G}\sum_{y_1,y_2\in\hat{G}}\chi_{y_1}(x_1)\chi_{y_2}(x_2)^*|y_1\rangle\langle x_1|g+h_1\rangle\langle g+h_2|x_2\rangle\langle y_2|\\ &=\frac{1}{|G|^2}\sum_{g\in G/H,h_1,h_2\in H}\sum_{y_1,y_2\in\hat{G}}\chi_{y_1}(g+h_1)\chi_{y_2}(g+h_2)^*|y_1\rangle\langle y_2|\\ &=\frac{1}{|G|^2}\sum_{y_1,y_2\in\hat{G}}[\sum_{g\in G/H,h_1,h_2\in H}\chi_{y_1}(g)\chi_{y_1}(h_1)\chi_{y_2}(g)^*\chi_{y_2}(h_2)^*]|y_1\rangle\langle y_2|\\ &=\frac{1}{|G|^2}\sum_{y_1,y_2\in\hat{G}}[\sum_{g\in G/H}\chi_{y_1}(g)\chi_{y_2}(g)^*][\sum_{h_1,h_2\in H}\chi_{y_1}(h_1)\chi_{y_2}(h_2)^*]|y_1\rangle\lang y_2| \end{aligned}$$

其中，$\chi_y(g)$ 也可以为商群$G/H$ 上的特征标，那么根据特征标的正交性，有：

$$\sum_{g\in G/H}\chi_{y_1}(g)\chi_{y_2}(g)^*=\frac{|G|}{|H|}\delta_{y_1,y_2}$$

于是原状态为：

$$\begin{aligned} F_G\rho F_G^\dagger &= \frac{1}{|G|\cdot |H|}\sum_{y\in\hat{G}}[\sum_{h\in H}\chi_y(h)\sum_{h\in H}\chi_y(h^{-1})]|y\rangle\langle y|\\ &=\frac{1}{|G|\cdot |H|}\sum_{y\in\hat{G}}[\sum_{h\in H}\chi_y(h)]^2|y\rangle\langle y|\\ &=\frac{|H|}{|G|}\sum_{y\in\hat{G}}\chi_y(H)^2|y\rangle\langle y| \end{aligned}$$

其中，$\chi_y(H)=\frac{1}{|H|}\sum_{h\in H}\chi_y(h)$。其中，

• 若$\forall h\in H,\chi_y(h)=1$，那么有$\chi_y(H)=1$。

• 若$\exists h'\in H,\chi_{y}(h')\neq 1$，那么$h'\in H\Rightarrow h'+H=H$，那么有：

  $$\begin{aligned} \chi_y(H)&=\frac{1}{|H|}\sum_{h\in H}\chi_y(h)\\ &=\frac{1}{|H|}\sum_{h\in h'+H}\chi_y(h)\\ &=\frac{1}{|H|}\sum_{h\in H}\chi_y(h'+h)\\ &=\chi_y(h')\frac{1}{|H|}\sum_{h\in H}\chi_y(h)\\ &=\chi_y(h')\chi_y(H) \end{aligned}$$

因为$\chi_y(h')\neq 1$，所以$\chi_y(H)=0$。故原状态改写为：

$$F_G\rho F_G^\dagger = \frac{|H|}{|G|}\sum_{y\in\hat{G},\chi_y(H)=1}|y\rangle\langle y|$$

所以如果我们在对第一寄存器作 QFT 后再测量，就可以得到$y$，使得$\forall h\in H,\chi_y(h)=1$。这样的话，就可以排除$G$ 中那些$\chi_y(g)\neq 1$ 的元素肯定不在子群$H$ 中。如此往复若干次，取交集的话就可以逐渐得到子群$H$。换句话说，如果测量到$y_1,y_2,...,y_n$，那么我们只需要求交集：

$$Ker\chi_{y_1}\cap Ker\chi_{y_2}\cap...\cap Ker\chi_{y_n}=H$$

即可。

# 复杂度分析

考虑重复测量$k$ 次后，我们得到了一个子群（它显然是个子群）：

$$K=Ker\chi_{y_1}\cap...\cap Ker\chi_{y_k}$$

那么有：$H$ 是$K$ 的子群，$K$ 是$G$ 的子群。根据 Lagrange 定理，$|H|$ 是$|K|$ 的约数，即有$|K|\geq 2|H|$。

注意到，当我们再次采样测量$y_{k+1}$，如果$K$ 是$Ker\chi_{y_{k+1}}$ 的子群，这样的$y_{k+1}$ 有多少个呢？实际上有$\frac{|G|}{|K|}$ 个。为什么呢？我们看之前的式子$F_G\rho F_G^\dagger$ 得知，一共有$\frac{|G|}{|H|}$ 个不同的$y$ 使得$\chi_y(H)=1$，也就是$H$ 是$Ker\chi_y$ 的子群。那么现在如果我们想让$K$ 是$Ker\chi_y$ 的子群，那有多少个$y$ 呢？就是$\frac{|G|}{|K|}$ 个（可以把子群$K$ 看作是$H$）。而所有的$y$ 均以$\frac{|H|}{|G|}$ 等概率得到，故：

Prob (再采样测量一次，得到$y$ 且$K$ 是$Ker\chi_y$ 的子群)=$\frac{|H|}{|G|}\cdot \frac{|G|}{|K|}=\frac{|H|}{|K|}\leq\frac{1}{2}$。

换句话说，我们测量有$>\frac{1}{2}$ 的概率使得$K\cap Ker\chi_y$ 大小至少减少一半（因为$K\cap Ker\chi_y$ 是$K$ 的子群，根据 Lagrange 定理，有$|K|\geq 2|K\cap Ker\chi_y|$）。

故持续重复采样测量$O(log|G|)$ 次，我们就有显著概率获得隐含子群$H$。