# 非 Abelian 隐藏子群：矩阵值 Fourier 谱、二面体筛法与开放边界

把 Abelian HSP 中的群换成非交换群，问题定义几乎不变，算法难度却剧烈上升。原因不是没有量子 Fourier 变换，而是 Fourier 系数从标量变成矩阵：单个表示标签通常不足以确定子群，选择什么基、是否联合测量多个陪集态，以及怎样高效实现后处理都成为核心。本课从一般 coset state 推导到二面体 Kuperberg 筛法，并解释图同构为何没有因此自动得到高效量子算法。

## 1. 同一个承诺，不同的陪集几何

设有限群 $G$ 不要求交换，未知 $H\le G$。oracle 满足

$$
f(x)=f(y)
\quad\Longleftrightarrow\quad
xH=yH.
$$

查询并测量函数值后得到左陪集态

$$
|gH\rangle
=\frac1{\sqrt{|H|}}
\sum_{h\in H}|gh\rangle.
$$

因 $g$ 随机，单次输入实际是混合态

$$
\rho_H=\frac1{|G/H|}
\sum_{gH}|gH\rangle\langle gH|.
$$

Ettinger--Høyer--Knill 证明：对任意有限 $G$，只需 $\operatorname{poly}(\log|G|)$ 份这样的状态就能在信息论上确定 $H$。但他们的最优联合测量与经典处理可耗指数时间。因此必须分开写：**oracle 查询复杂度是多项式，不代表已知总运行时间是多项式。**

## 2. 非 Abelian QFT 的输出是什么

不可约酉表示记为 $\sigma\in\widehat G$，维数为 $d_\sigma$。群 QFT 为

$$
F_G|x\rangle
=\sum_{\sigma\in\widehat G}
\sqrt{\frac{d_\sigma}{|G|}}
\sum_{i,j=1}^{d_\sigma}
\sigma(x)_{ij}|\sigma,i,j\rangle.
$$

定义 $H$-不变子空间投影

$$
\Pi_H^\sigma=
\frac1{|H|}\sum_{h\in H}\sigma(h).
$$

它确实是投影：左乘任意 $h_0\in H$ 只重排求和项，所以 $\sigma(h_0)\Pi_H^\sigma=\Pi_H^\sigma$；反过来，其像中的向量都被 $H$ 固定。

对陪集态做 QFT，$\sigma$ 块的振幅矩阵正比于

$$
\sigma(g)\Pi_H^\sigma.
$$

只测表示名 $sigma$ 称为弱 Fourier 采样，其概率为

$$
p(\sigma)
=\frac{d_\sigma|H|}{|G|}
\operatorname{rank}(\Pi_H^\sigma).
$$

继续测行列指标称为强 Fourier 采样，分布依赖所选的表示基。Abelian 表示全是一维，$\Pi_H^\sigma$ 只能是 0 或 1，于是退化成 $H^\perp$；非 Abelian 表示可能高维，投影的方向也携带信息，仅看秩会丢失它。

## 3. 哪些非交换情形仍可高效

若 $H$ 是正规子群，则 $H$-不变子空间在整个 $G$ 作用下保持不变。由 Schur 引理，对不可约 $\sigma$，$\Pi_H^\sigma$ 要么为 0，要么为单位阵。弱 Fourier 标签于是像 Abelian annihilator 一样标识哪些表示在商群 $G/H$ 上下降，正规子群重构可高效完成。

进一步的正结果依赖群结构，而不是“非 Abelian QFT”四个字本身：

- 某些半直积与 affine 群可选择特别的表示基，使强采样暴露隐藏子群；
- extraspecial、nilpotency class 2 及若干近 Hamiltonian 群可递归利用中心和交换商；
- translating coset/hidden translation 把两个函数的相对平移与稳定子群联合求解；
- Abelian hypergroup 形式把部分非交换卷积重新组织为可处理的交换对象。

不同族的输入表示、群运算 oracle 和 QFT 电路并不相同，不能把某一族的多项式算法外推到任意黑盒群。

## 4. 二面体 HSP 化成相位量子比特

二面体群写成

$$
D_N=\mathbb Z_N\rtimes\mathbb Z_2,
$$

其中反射把 $x$ 送到 $-x$。设隐藏反射子群由 $(s,1)$ 生成。测量 oracle 后，忽略全局平移可得

$$
\frac{|x,0\rangle+|x+s,1\rangle}{\sqrt2}.
$$

只对 $\mathbb Z_N$ 坐标做 QFT 并测得随机 $k$，剩下一个带标签的量子比特

$$
|\psi_k\rangle
=\frac{|0\rangle+\omega_N^{ks}|1\rangle}{\sqrt2},
\qquad \omega_N=e^{2\pi i/N}.
$$

未知 $s$ 已编码为相位。难点是 $k$ 随机；单个相位量子比特无法以足够精度直接读出 $s$。

## 5. Kuperberg 筛法怎样放大有用频率

取两态 $|\psi_k\rangle|\psi_\ell\rangle$，做 CNOT 并测量一个量子比特，可按结果得到标签

$$
k+\ell\quad\text{或}\quad k-\ell
$$

的新相位态。把标签按低 $b$ 位分桶，配对低位相同的 $k,\ell$ 并选择差，所得标签可被 $2^b$ 整除。重复“分桶--配对--合并”，逐层清除低位，最终制造标签接近 $N/2$、$N/4$ 等的态；在 $X/Y$ 基测量便能读出 $s$ 的二进制信息。

每层会损失大量样本，而每层又清除若干位。平衡桶宽与层数得到

$$
\exp\bigl(O(\sqrt{\log N})\bigr)
$$

时间和查询复杂度，优于经典 $\Theta(\sqrt N)$ 查询但仍非多项式。原筛法需要相同量级的空间；Regev 的变体用重计算换空间，达到多项式空间与

$$
\exp\bigl(O(\sqrt{\log N\log\log N})\bigr)
$$

时间。后续筛法改善常数和实现方式，尚未得到一般 DHSP 的多项式时间算法。

## 6. 与格和图同构的关系

二面体 coset 问题与某些 unique shortest vector 问题存在约化：若能高效解决足够参数范围的 DHSP，就会威胁相应格问题。但这不是“Shor 已破解所有格密码”；已知筛法仍为次指数，并且约化的近似因子和分布承诺必须保留。

图同构可编码为 wreath product

$$
S_n\wr\mathbb Z_2
$$

上的 HSP：非同构时隐藏子群平凡，同构时含交换两图的元素。困难在于对称群存在巨大高维表示，常见的单寄存器 Fourier 采样对共轭子群几乎不可分。信息论上的多项式陪集态数量并没有给出可实现的联合测量，这仍是 HSP 路线的核心开放边界。

## 7. 小结与习题

- 非 Abelian QFT 输出矩阵块 $\sigma(g)\Pi_H^\sigma$，而非标量正交约束。
- 弱采样只看不变子空间的维数，强采样还依赖表示基。
- 任意有限群 HSP 的查询复杂度为多项式，但已知总时间可为指数。
- 二面体筛法通过相位态标签的加减逐层提纯频率，达到次指数时间。

1. 证明 $\Pi_H^\sigma$ 是 Hermitian 投影。
2. 推导弱 Fourier 采样概率并验证其总和为 1。
3. 展开两份 $|\psi_k\rangle|\psi_\ell\rangle$，验证 CNOT 与测量产生 $k\pm\ell$。
4. 解释正规性为什么使 $\Pi_H^\sigma$ 在不可约块上只能是 0 或 $I$。

## 参考文献与 Zoo 覆盖

- 一般查询与测量：Zoo 37（[Ettinger--Høyer--Knill](https://arxiv.org/abs/quant-ph/0401083)）、143（[Ettinger--Høyer](https://arxiv.org/abs/quant-ph/9807029)）、51（Hallgren--Russell--Ta-Shma）、69（[Lomont 综述](https://arxiv.org/abs/quant-ph/0411037)）。
- 半直积与 affine 群：Zoo 9、22、28、53、71、72、126、207，对应 [Bacon--Childs--van Dam](https://arxiv.org/abs/quant-ph/0504083) 等算法。
- 其他可解群族：Zoo 44、55、56、57、81、273，覆盖 poly-near-Hamiltonian、extraspecial、nil-2 和 Abelian hypergroup 方法。
- 隐藏平移框架：Zoo 43，[Friedl 等](https://arxiv.org/abs/quant-ph/0211091)。
- 二面体与格：Zoo 66（[Kuperberg](https://arxiv.org/abs/quant-ph/0302112)）、78（[Regev 格约化](https://arxiv.org/abs/cs/0304005)）、79、218、311、312。