非 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）、143（Ettinger--Høyer）、51（Hallgren--Russell--Ta-Shma）、69（Lomont 综述）。

  • 半直积与 affine 群：Zoo 9、22、28、53、71、72、126、207，对应 Bacon--Childs--van Dam 等算法。

  • 其他可解群族：Zoo 44、55、56、57、81、273，覆盖 poly-near-Hamiltonian、extraspecial、nil-2 和 Abelian hypergroup 方法。

  • 隐藏平移框架：Zoo 43，Friedl 等。

  • 二面体与格：Zoo 66（Kuperberg）、78（Regev 格约化）、79、218、311、312。