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

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

# 隐含子群问题

• 例 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|}\sum_{g\in G}(\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|\cdot |H|}\sum_{g\in G,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\cdot|H|}\sum_{g\in G,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\cdot|H|}\sum_{g\in G,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\cdot|H|}\sum_{y_1,y_2\in\hat{G}}[\sum_{g\in G,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\cdot|H|}\sum_{y_1,y_2\in\hat{G}}[\sum_{g\in G}\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}\chi_{y_1}(g)\chi_{y_2}(g)^*=|G|\cdot \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$。

---

# 非 Abel 情况

下面我们考虑更一般的情况。考虑这样一个变换：

$$|x\rangle\rightarrow|\hat{x}\rangle:=\frac{1}{\sqrt{|G|}}\sum_{\sigma\in \hat{G}}d_\sigma|\sigma,\sigma(x)\rangle$$

其中，$d_\sigma$ 是不可约表示$\sigma$ 的维度。$|\sigma\rangle$ 就是唯一表示$\sigma$ 的一个标签，而$|\sigma(x)\rangle$ 定义为：

$$\begin{aligned} |\sigma(x)\rangle &:=(\sigma(x)\otimes 1_{d_\sigma})\sum_{k=1}^{d_\sigma}\frac{|k,k\rangle}{\sqrt{d_\sigma}}\\ &=\sum_{j,k=1}^{d_\sigma}\frac{\sigma(x)_{j,k}}{\sqrt{d_\sigma}}|j,k\rangle \end{aligned}$$

于是变换的矩阵为：

$$F_G:=\sum_{x\in G}|\hat{x}\rangle\langle x|$$

可以验证它是酉的：

$$\begin{aligned} \langle \sigma(x)|\sigma(y)\rangle &=\frac{1}{d_\sigma}\sum_{k=1}^{d_\sigma}\langle k|\sigma(x)\sigma(y)^\dagger|k\rangle\otimes\langle k|k\rangle\\ &=\frac{1}{d_\sigma}\sum_{k=1}^{d_\sigma}\langle k|\sigma(x)\sigma(y)^\dagger|k\rangle\\ &=\frac{tr(\sigma(x)\sigma(y)^\dagger)}{d_\sigma}\\ &=\frac{\chi_\sigma(xy^{-1})}{d_\sigma}\\ \langle\hat{x}|\hat{y}\rangle &=\sum_{\sigma\in\hat{G}}\frac{d_\sigma^2}{|G|}\langle \sigma(x)|\sigma(y)\rangle\\ &=\sum_{\sigma\in\hat{G}}\frac{d_\sigma}{|G|}\chi_\sigma(xy^{-1})\\ &=\delta_{x,y} \end{aligned}$$

下面我们证明，$F_G$ 实际上就是把群的左右正则表示对角化。譬如对两个表示$\sigma,\sigma'$，那么它们的直和就是：

$$(\sigma\oplus\sigma')(x)=\begin{pmatrix}\sigma(x)&\\&\sigma'(x)\end{pmatrix}$$

那么对于一个表示$L$，把他对角化也就是拆分成若干个直和。

对于左正则表示$L$，有$L(x)|y\rangle=|xy\rangle$，那么$F_G$ 的作用为：

$$\begin{aligned} \hat{L}(x)&=F_GL(x)F_G^\dagger\\ &=\sum_{y,y'\in G}|\hat{y}\rangle\langle y|L(x)|y'\rangle\langle \hat{y'}|\\ &=\sum_{y,y'\in G}|\hat{y}\rangle\langle y|xy'\rangle\langle\hat{y'}|\\ &=\sum_{y\in G}|\hat{xy}\rangle\langle\hat{y}|\\ &=\sum_{\sigma,\sigma'\in\hat{G}}\sum_{y\in G}\frac{d_\sigma d_{\sigma'}}{|G|}|\sigma,\sigma(xy)\rangle\langle \sigma',\sigma'(y)|\\ &=\sum_{\sigma,\sigma'\in\hat{G}}\sum_{y\in G} \sum_{j,k=1}^{d_\sigma}\sum_{j',k'=1}^{d_{\sigma'}} \frac{\sqrt{d_\sigma d_{\sigma'}}}{|G|}\sigma(xy)_{j,k}\sigma'(y)_{j',k'}^*|\sigma,j,k\rangle\langle\sigma',j',k'|\\ &=\sum_{\sigma,\sigma'\in\hat{G}}\sum_{j,k,l=1}^{d_\sigma}\sum_{j',k'=1}^{d_{\sigma'}}\frac{\sqrt{d_\sigma d_{\sigma'}}}{|G|}\sigma(x)_{j,l}|\sigma,j,k\rangle\langle \sigma',j',k'|\cdot\sum_{y\in G}\sigma(y)_{l,k}\sigma'(y)_{j',k'}^*\\ &=\sum_{\sigma,\sigma'\in\hat{G}}\sum_{j,k,l=1}^{d_\sigma}\sum_{j',k'=1}^{d_{\sigma'}}\frac{\sqrt{d_\sigma d_{\sigma'}}}{|G|}\sigma(x)_{j,l}|\sigma,j,k\rangle\langle \sigma',j',k'|\cdot\frac{|G|}{d_\sigma}\delta_{\sigma,\sigma'}\delta_{l,j'}\delta_{k,k'}\\ &=\sum_{\sigma \in \hat{G}}\sum_{j,k,l=1}^{d_\sigma}\sigma(x)_{j,l}|\sigma,j,k\rangle\langle\sigma,l,k|\\ &=\sum_{\sigma\in\hat{G}}\sum_{j,l=1}^{d_\sigma}\sigma(x)_{j,l}|\sigma,j\rangle\langle\sigma,l|\otimes \sum_{k=1}^{d_\sigma}|k\rangle\langle k|\\ &=\bigoplus_{\sigma\in\hat{G}}(\sigma(x)\otimes 1_{d_\sigma}) \end{aligned}$$

注意上述推导中，有：

$$\sigma(xy)_{j,k}=[\sigma(x)\sigma(y)]_{j,k}=\sum_{l=1}^{d_\sigma}\sigma(x)_{j,l}\sigma(y)_{l,k}$$

而且

$$\begin{aligned} \sum_{\sigma,j,l}\sigma(x)_{j,l}|\sigma,j\rangle\langle \sigma,l|\otimes 1&=\sum_{\sigma}|\sigma\rangle\langle\sigma|\otimes (\sigma(x)\otimes 1)\\ &=\bigoplus_\sigma (\sigma(x)\otimes 1) \end{aligned}$$

因为$|\sigma\rangle$ 是对表示$\sigma$ 的一个唯一编码，其实类似于，譬如有三个表示$\sigma_1,\sigma_2,\sigma_3$，那么就有：

$$|\sigma_1\rangle\langle\sigma_1|=\begin{pmatrix}1 & & \\ & 0& \\ & &0\end{pmatrix}\\ |\sigma_2\rangle\langle\sigma_2|=\begin{pmatrix}0 & & \\ & 1& \\ & &0\end{pmatrix}\\ |\sigma_3\rangle\langle\sigma_3|=\begin{pmatrix}0 & & \\ & 0& \\ & &1\end{pmatrix}\\$$

那么显然：

$$|\sigma_1\rangle\langle\sigma_1|\otimes \sigma_1(x)+|\sigma_2\rangle\langle\sigma_2|\otimes \sigma_2(x)+|\sigma_3\rangle\langle\sigma_3|\otimes \sigma_3(x)=\begin{pmatrix} \sigma_1(x)&&\\ &\sigma_2(x)&\\ &&\sigma_3(x) \end{pmatrix}\\ =\sigma_1(x)\oplus\sigma_2(x)\oplus\sigma_3(x)$$

同理，类似地有：

$$\hat{R}(x)=F_GR(x)F_G^\dagger=\bigoplus_{\sigma\in\hat{G}}(1_{d_\sigma}\otimes \sigma(x)^*)$$

其中$R$ 是右正则表示，满足$R(x)|y\rangle=|yx^{-1}\rangle$。

---

下面我们看一下 Non-Abelian Group 的 HSP 问题。

假如目前我们考虑的是左陪集相同，即：

$$f(x)=f(y)\Leftrightarrow x^{-1}y\in H$$

（当然我们也可以定义右陪集的 HSP 问题，类似地$f(x)=f(y)\Leftrightarrow yx^{-1}\in H$）。

那么类似地，我们还是制备态：

$$\rho_H=\frac{1}{|G|}\sum_{x\in G}|x,f(x)\rangle\langle x,f(x)|$$

如果我们去掉第二寄存器，也就是取 partial trace，就会得到一个在不同陪集上混合，同一陪集上叠加的态：

$$\begin{aligned} \rho_H&=\frac{1}{|G|}\sum_{g\in G}(\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|\cdot |H|}\sum_{g\in G}\sum_{h,h'\in H}|g+h\rangle\langle g+h'|\\ &=\frac{1}{|G|\cdot|H|}\sum_{g\in G}\sum_{h,h'\in H}R(h^{-1})|g\rangle\langle g|R(h'^{-1})^\dagger\\ &=\frac{1}{|G|\cdot |H|}\sum_{h,h'\in H}R(h^{-1})\sum_{g\in H}|g\rangle\langle g| R(h'^{-1})^\dagger\\ &=\frac{1}{|G|\cdot |H|}\sum_{h,h'\in H}R(h^{-1}h')\\ &=\frac{1}{|G|}\sum_{h\in H}R(h) \end{aligned}$$

然后作用 QFT，就会有：

$$\hat{\rho}_H=F_G\rho_HF_G^\dagger=\frac{1}{|G|}\bigoplus_{\sigma\in\hat{G}}(1_{d_\sigma}\otimes \sigma(H)^*)\\ =\frac{1}{|G|}\sum_{\sigma\in\hat{G}}|\sigma\rangle\langle \sigma|\otimes (1_{d_\sigma}\otimes\sigma(H)^*)$$

其中，$\sigma(H)=\sum_{h\in H}\sigma(h)$。

假设我们用这样一组测量算子去测量：$\{|\sigma\rangle\langle\sigma|\otimes 1\;|\;\sigma\in \hat{G}\}$。那么测得结果是$\sigma$ 的概率为：

$$\begin{aligned} Pr(\sigma)&=\frac{1}{|G|}tr(1_{d_\sigma}\otimes\sigma(H)^*)\\ &=\frac{d_\sigma}{|G|}\sum_{h\in H}\chi_\sigma(h)^*\\ &=\frac{d_\sigma}{|G|}\sum_{h\in H}\chi_\sigma(h^{-1})\\ &=\frac{d_\sigma}{|G|}\sum_{h\in H}\chi_\sigma(h) \end{aligned}$$

其中，类似前述推导，我们知道

$$\sum_{h\in H}\chi_\sigma(h)=\begin{cases} d_\sigma|H| & \forall h\in H,\chi_\sigma(h)=1\\ 0& else \end{cases}$$

所以测得一个满足$\forall h\in H,\chi_\sigma(h)=1$ 的平凡特征标$\sigma$ 概率为$\frac{d_\sigma^2 |H|}{|G|}$。

此时就不能类比之前 Abel 的情况（复杂度分析一章），不能保证在$O(log|G|)$ 次重复采样后得到$H$ 了。事实上，如果$H$ 是$G$ 的一个正规子群，仍然可以在$O(log|G|)$ 次重复采样得到$H$。