留空

# Dihedral Group 的群结构

首先我们考虑一下 dihedral group $D_N=\langle r,s:r^2=s^N=1,rs=s^{-1}r\rangle$ 的结构，实际上它是$\mathbb{Z}_N$ 和$\mathbb{Z}_2$ 的半直积。

具体地，因为$D_N$ 中所有的元素形式都可以写作$s^xr^a$，其中$x\in \mathbb{Z}_N,a\in\mathbb{Z}_2$。
注意到$r^as^y=s^{(-1)^ay}r^a$（使用$rs=s^{-1}r$ 共$a$ 次），所以

$$\begin{aligned} s^xr^a\cdot s^yr^b&=s^xs^{(-1)^ay}r^{a}r^b=s^{x+(-1)^a}r^{a+b}.\\ \end{aligned}$$

因此，$D_N\cong (\mathbb{Z}_N,+)\rtimes_\varphi (\mathbb{Z}_2,+)$，其中$\varphi:\mathbb{Z}_2\to Aut(\mathbb{Z}_N)$ 定义为$\varphi(a)(y)=(-1)^ay$。

$(\mathbb{Z}_N,+)\rtimes_\varphi (\mathbb{Z}_2,+)$ 上的群运算为

$$(x,a)\cdot (y,b)=(x+\varphi(a)(y),a+b)=(x+(-1)^ay,a+b).$$

因此单位元是$(0,0)$，逆元为

$$(x,a)^{-1}=(-(-1)^ax,a).$$

f
我们知道，$\mathbb{Z}_N\rtimes_\varphi\mathbb{Z}_2$ 所有的子群只有 3 种情况：

• 循环群$\langle(x,0)\rangle$，其中$x\in\mathbb{Z}_N$ 要么是 0，要么是$N$ 的一个因子；
• 二元群$\langle (y,1)\rangle=\{(y,1),(0,0)\}$，其中$y\in\mathbb{Z}_N$；
• 二面体群$\langle (x,0),(y,1)\rangle$，其中$x\in\mathbb{Z}_N$ 是$N$ 的一个因子，$y\in\mathbb{Z}_x$。

Ettinger and Høyer 提出了：不失困难性地，我们可以认为 dihedral group 上的隐含子群都是第二种情况，即可以认为 hidden subgroup 都是二元群$\langle (y,1)\rangle=\{(y,1),(0,0)\}$，所以只需要寻找$y\in\mathbb{Z}_N$。

他们的主要思想是，首先考虑函数$f:D_N\to S$ hides a subgroup $H=\langle (x,0),(y,1)\rangle$，那么我们可以考虑函数$f$ 限制在 abelian 群$\mathbb{Z}_N\times \{0\}\leq D_N$ 上。
这个函数 hides the subgroup $\langle (x,0)\rangle$，而且因为限制后的群是 abelian 的，可以量子有效地找到$x$。
又因为$\langle (x,0)\rangle\unlhd D_N$，所以可以考虑商群$D_N/\langle(x,0)\rangle$，我们在商群上定义$f'$，那么这个$f'$ 就会 hide $\langle (y,1)\rangle$。

换句话说，当$f$ hide $\langle (x,0),(y,1)\rangle$ 时，$x$ 是更容易求出的。因此我们认为，dihedral hidden subgroup problem 的困难程度在于寻找$y$，即不失困难性地我们假设$f$ hides $H=\langle (y,1)\rangle$ for some $y\in\mathbb{Z}_N$。

# Fourier Sampling in the Dihedral Group

我们知道，对于子群$H=\{(y,1),(0,0)\}$，它一共有$|D_N|/2=N$ 个左陪集，可以由代表元$(z,0):z\in\mathbb{Z}_N$ 来表示。

因为我们知道

$$(z_1,0)^{-1}\cdot (z_2,0)=(-z_1,0)\cdot (z_2,0)=(-z_1+z_2,0),$$

因此$(z_1,0)\cdot H=(z_2,0)\cdot H\iff -z_1+z_2=0$。所以每一个$z\in\mathbb{Z}_N$ 都恰好一一对应一个左陪集$(z,0)\cdot H$。

还是利用之前 Fourier sampling 的做法，假设我们构造了$\frac{1}{\sqrt{2N}}|(a,b),f(a,b)\rangle$，然后测量$|f(a,b)\rangle$，以相同的概率随机掉到一个陪集$(z,0)H$ 中，即得到了状态

$$|(z,0)H\rangle\triangleq\frac{1}{\sqrt{2}}(|z,0\rangle+|y+z,1\rangle).$$

我们试图通过这个状态来求解$y$。

之前的标准做法是对两个寄存器一起做$D_N$ 上的 QFT，然后再测量群表示。
但是在这里我们先只在第一个寄存器上做 QFT over $\mathbb{Z}_N$，实际上可以证明：对第一个寄存器做 QFT 并测量等价于对 2 个寄存器一起做 QFT over $D_N$ 和测量。得到的信息是一样的（不明）。

所以做 QFT 后，得到状态

$$\frac{1}{\sqrt{2N}}\sum_{k\in\mathbb{Z}_N}(\omega^{kz}_N|k,0\rangle+\omega^{k(y+z)}_N|k,1\rangle)=\frac{1}{\sqrt{N}}\sum_{k\in\mathbb{Z}_N}\omega^{kz}_N|k\rangle\otimes\frac{1}{\sqrt{2}}(|0\rangle+\omega^{ky}_N|1\rangle).$$

所以在测量第一个寄存器后，我们将以相等的概率得到一个$k\in\mathbb{Z}_N$，然后第二个寄存器的状态是

$$|\psi_k\rangle=\frac{1}{\sqrt{2}}(|0\rangle+\omega^{ky}_N|1\rangle).$$

剩下的问题就是给定$k$，如何从$|\psi_k\rangle$ 中得到$y$。

实际上，目前的过程是基于 Fourier sampling 的最优解，并没有损失什么信息。

如果我们可以给定$k$ 后构造$|\psi_k\rangle$ 就好了（而不是以均匀随机的概率得到$k$）。因为譬如给定$k=N/2$，那么$|\psi_{N/2}\rangle=\frac{1}{\sqrt{2}}(|0\rangle+(-1)^{y}|1\rangle)$，直接在$|\pm\rangle$ 基下测量就可以得到$y$。

Kuperberg 算法的核心思想就是组合$|\psi_k\rangle$，来尽可能地提升我们想要的$k$ 的权重。

给定$|\psi_p\rangle$ 和$|\psi_q\rangle$ 后，我们可以组合它们得到状态：

$$\begin{aligned} |\psi_p,\psi_q\rangle&=\frac{1}{2}(|0,0\rangle+\omega^{yp}_N|1,0\rangle+\omega^{yq}_N|0,1\rangle+\omega^{y(p+q)}_N|1,1\rangle)\\ \text{(apply CNOT)}&\mapsto\frac{1}{2}(|0,0\rangle+\omega^{yp}_N|1,1\rangle+\omega^{yq}_N|0,1\rangle+\omega^{y(p+q)}_N|1,0\rangle)\\ &=\frac{1}{\sqrt{2}}(|\psi_{p+q},0\rangle+\omega^{yq}_N|\psi_{p-q},1\rangle). \end{aligned}$$

这意味着测量第二个寄存器时，我们可以分别以 1/2 的概率得到 0 和 1，然后得到对应状态$|\psi_{p\pm q}\rangle$。

本质上$p,q$ 都是群不可约表示的 label，而$|\psi_{p\pm q}\rangle$ 的提取可以理解为两个不可约表示的张量积后，再直和分解为两个不可约表示：$R^{(p)}\otimes R^{(q)}=R^{(p+q)}\oplus R^{(p-q)}$。

# The Kuperberg sieve

接下来我们设$N=2^n$。实际上对于$D_N$，我们只需要得到$y$ 的奇偶性就可以得出$y$ 了。
因为$D_N$ 有 2 个子群都同构于$D_{N/2}$:

$$\{(2x,0),(2x,1):x\in\mathbb{Z}_{N/2}\},\qquad \{(2x,0),(2x+1,1):x\in\mathbb{Z}_{N/2}\}.$$

如果$y$ 是偶数，那么 hidden subgroup $H$ 是前者的一个子群，否则$H$ 是后者的一个子群。

因此一旦我们知道$y$ 的奇偶性，我们可以限制在$D_{N/2}$ 上来寻找$y$ 的倒数第二位，以此类推。

Kuperberg 算法如下进行：

1. 首先，准备$\varTheta(16^{\sqrt{n}})$ 个状态

   $$|\psi_k\rangle=\frac{1}{\sqrt{2}}(|0\rangle+\omega^{ky}_N|1\rangle),$$

   每一个$k$ 都是从$\mathbb{Z}_N$ 中独立均匀随机选取的，这可以由前述 Fourier sampling 做到。
2. 对于每个$j=0,1,...,m-1$，其中$m=\lceil\sqrt{n}\rceil$，假设现在所有的状态$|\psi_k\rangle$ 对应的$k$ 的最后$mj$ 位都是 0。把这些状态配对，使得每一对$|\psi_p\rangle$ 和$|\psi_q\rangle$ 都满足至少$p,q$ 的最后$mj$ 位是 0（已经满足了），以及后$mj..m(j+1)$ 位相同。把不能配对的状态丢掉。
3. 用之前介绍的方法创造$|\psi_{p\pm q}\rangle$，如果得到$+$，那么也丢掉。
4. 最后剩下了一对状态是$|\psi_0\rangle$ 和$|\psi_{2^{n-1}}\rangle$（可以证明，初始状态那么多时，大概率会剩下这样一对状态），然后进行测量第二个状态。

这个算法 query 了$2^{(O\sqrt{n})}$ 次来准备初始的$\varTheta(16^{\sqrt{n}})$ 个状态，然后执行了$O(\sqrt{n})$ 个 step，每一个 step 也都需要进行$2^{O(\sqrt{n})}$ 次配对、测量。所以最后 query 和运行时间复杂度都是$2^{O(\sqrt{n})}$。