非 Abelian 隐藏子群问题

在 Abelian 隐藏子群 词条中我们看到：Simon、周期查找、离散对数这些算法背后是同一个框架——oracle 把群元素按未知子群的陪集分组，而量子 Fourier 变换把”平移不变性”翻译成对偶群上的线性约束，采样若干次即可解出子群。整个故事干净利落，以至于一个自然的问题立刻浮现：把群换成非交换群，同一套机器还能转吗？

答案出人意料地微妙。问题的定义几乎不用改，陪集态的制备也一模一样，量子傅里叶变换在任意有限群上都有定义、而且对许多非交换群也能高效实现。真正的变化在于：非交换群的不可约表示可以是高维的，Fourier 系数从标量变成矩阵。于是”测到一个频率标签”不再直接给出一条线性约束——单个表示标签通常不足以确定子群；选择什么基来测量矩阵指标、是否对多个陪集态做联合测量、以及后处理能否高效完成，全都成为新的核心问题。

这个问题绝非纯理论好奇心。二面体群上的隐藏子群问题与某些格最短线性无关向量问题存在约化（Regev），而图同构可以编码为对称群 wreath product 上的隐藏子群问题——任何一端的高效算法都会立刻改写密码学或复杂度理论的版图。历史脉络大致是：Simon（1994）与 Shor 的算法统一为 Abelian HSP 之后，Ettinger–Høyer–Knill 证明了一般有限群上查询复杂度的多项式界；Hallgren–Russell–Ta-Shma 解决了正规隐藏子群；Kuperberg 对二面体群给出次指数时间的筛法，Regev 随后把它改良为多项式空间；而对图同构所需的对称群情形，已知的 Fourier 采样技术被证明不足以完成任务。本词条按”一般理论 → 可解情形 → 二面体筛法 → 开放边界”的顺序展开，所有引用集中在文末。

读者只需熟悉 Simon 算法、群 QFT 与相位估计；表示论的背景（不可约表示、特征标、矩阵元正交性）可对照群表示矩阵元词条，本节用到之处会就地复习。

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

1.1 问题定义

设 $G$ 为有限群，不要求交换。未知子群 $H\le G$ 由一个函数 $f:G\to S$（$S$ 为某个有限值集）隐藏，承诺与 Abelian 情形逐字平行：

$$f(x)=f(y)⟺xH=yH.$$

也就是说：$f$ 在每个左陪集 $xH=\{xh:h\in H\}$ 上取常值，且不同陪集取不同值。任务仍以输出 $H$ 的一组生成元为完成标准。取左陪集只是约定，改右陪集得到等价的问题；关键在于 $H$ 不必正规，陪集一般不再构成商群——这正是”陪集几何”与 Abelian 情形的第一个差别。

1.2 为什么这个问题重要

两个动机值得先记住，后文会分别展开：

• 二面体群 $D_N$ 上的 HSP：Regev 给出了从某些 unique shortest vector（唯一最短向量）格问题到二面体陪集问题的约化。格密码的安全性假设因此与一般非 Abelian HSP 的算法边界挂上了钩。
• 对称群 $S_n$（及其 wreath product）上的 HSP：图同构可以编码进来。图同构是少数既未被证明 NP 完全、又没有已知多项式算法的自然问题，量子路线能否在此突破是非 Abelian HSP 研究的主线之一。

经典算法能做到什么程度？对一般黑盒群上的 HSP，经典查询需要指数量级：即使对结构上相当温和的二面体隐藏反射问题，经典查询复杂度也是 $\Theta (\sqrt{N})$ 量级。这与 Abelian 情形形成鲜明对照——那里量子算法把指数（或亚指数，视具体问题而定）的经典复杂度直接降到多项式。本词条的核心问题就是：量子计算机对非交换群能复制这种飞跃吗？

1.3 陪集态：量子部分的全部原料

量子部分的第一步与 Abelian 情形完全相同。制备群上的均匀叠加，查询 oracle：

$$\frac{1}{\sqrt{|G|}}\sum _{x\in G}|x⟩|0⟩⟼\frac{1}{\sqrt{|G|}}\sum _{x\in G}|x⟩|f(x)⟩.$$

测量第二寄存器，设得到值 $f(g)$。由承诺，取该值的 $x$ 恰好构成左陪集 $gH$，因此第一寄存器坍缩为陪集态 (coset state)

$$|gH⟩=\frac{1}{\sqrt{|H|}}\sum _{h\in H}|gh⟩.$$

注意两个陪集态要么相同、要么正交：若 $gH=g^{\prime }H$，两态相等；若 $gH\cap g^{\prime }H=\varnothing$，内积 $⟨gH|g^{\prime }H⟩$ 的求和项两两正交，结果为零。不同左陪集恰好有 $[G:H]=|G|/|H|$ 个，且等概率出现。

由于 $g$ 均匀随机且测量值不被记录，单次制备实际得到的是混合态

$${\rho }_H=\frac{1}{|G/H|}\sum _{gH}|gH⟩⟨gH|,$$

其中求和取遍全部 $|G/H|=[G:H]$ 个左陪集。这是一个合法的密度矩阵：各项是相互正交的一维投影，系数 $1/[G:H]$ 非负且总和为 $1$。每次调用 oracle 都得到一份 ${\rho }_H$ 的拷贝——这就是算法能使用的全部原料，其余一切（QFT、测量、联合处理）都只是对 ${\rho }_H^{\otimes m}$ 的加工。

1.4 查询复杂度与运行时间必须分开记账

Ettinger–Høyer–Knill 证明了一个看似终结问题的结果：对任意有限群 $G$，只需

$$\mathrm{poly}(\log |G|)$$

份陪集态，就能在信息论意义上唯一确定 $H$。直观地说，不同子群 $H\ne H^{\prime }$ 对应的 ${\rho }_H$ 与 ${\rho }_{H^{\prime }}$ 足够”可分”，而对充分多份拷贝存在一个联合测量把候选子群逐一排除。

但这个结果有一个决定性的保留条款：他们构造的最优联合测量及其经典后处理可耗指数时间。“存在这样一个测量”是 Hilbert 空间几何的陈述，“用多项式个量子门实现它”是另一回事。由此得到全课最重要的记账原则：

oracle 查询复杂度是多项式，不代表已知总运行时间是多项式。

非 Abelian HSP 研究的全部张力都浓缩在这一句话里：信息就在 ${\rho }_H$ 中，而且用量不多；缺的是一台能高效把它读出来的机器。QFT 是造这台机器的第一个候选零件，下面我们就去看它在非交换群上到底输出什么。

2. 非 Abelian QFT 的输出是什么

2.1 不可约表示与群 QFT

先复习表示论的三件标准事实（证明见群表示矩阵元）：

• 有限群 $G$ 的不可约酉表示（inequivalent irreducible unitary representations）只有有限个，记为 $\sigma \in \hat{G}$，其维数记为 $d_{\sigma }$。
• 维数平方和等于群阶：

$$\sum _{\sigma \in \hat{G}}{d}_{\sigma }^2=|G|.$$

• 矩阵元正交关系 (Schur orthogonality)：在适当归一化下，不同不可约表示的矩阵元作为 $G$ 上的函数两两正交：

$$\frac{d_{\sigma }}{|G|}\sum _{x\in G}\sigma (x{)}_{ij}\overline{{\sigma }^{\prime }(x{)}_{i^{\prime }{j}^{\prime }}}={\delta }_{\sigma {\sigma }^{\prime }}{\delta }_{i{i}^{\prime }}{\delta }_{j{j}^{\prime }}.$$

群 QFT 定义为把”群元基”映到”表示标签 + 矩阵元指标基”的酉变换：

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

两点验证。第一，维数对得上：右端基矢总数为 ${\sum }_{\sigma }{d}_{\sigma }^2=|G|$，与左端的 $|G|$ 个群元基一致。第二，酉性：任意两个群元基像的内积为

$$⟨x^{\prime }|F_G^{†}{F}_G|x⟩=\sum _{\sigma ,i,j}\frac{d_{\sigma }}{|G|}\overline{\sigma (x^{\prime }{)}_{ij}}\sigma (x{)}_{ij}={\delta }_{x,x^{\prime }},$$

这正是矩阵元正交关系（取 $\sigma ={\sigma }^{\prime }$ 并对全部 $\sigma$ 求和）的内容。对许多具体群族（对称群、二面体群、Heisenberg 群等），$F_G$ 有 $\mathrm{poly}(\log |G|)$ 规模的已知电路构造；QFT 本身不是瓶颈。

2.2 $H$-不变子空间投影

整个非 Abelian 理论的核心对象是如下算子。对每个不可约表示 $\sigma$，定义

$${\Pi }_H^{\sigma }=\frac{1}{|H|}\sum _{h\in H}\sigma (h).$$

它是”子群方向上的群平均”。下面这条引理给出它的全部代数性质，后面每一步推导都建立在它之上。

Lemma 1. ${\Pi }_H^{\sigma }$ 是 Hermitian 投影（即 $({\Pi }_H^{\sigma }{)}^2={\Pi }_H^{\sigma }$ 且 $({\Pi }_H^{\sigma }{)}^{†}={\Pi }_H^{\sigma }$），并且它的像恰好是 $\sigma$ 中被 $H$ 全部元素固定的向量构成的子空间。

证明。分三步，每步只用”有限群中固定一个因子、另一个因子跑遍 $H$ 时乘积也跑遍 $H$“这一重排事实。

第一步，幂等性。利用表示的同态性质 $\sigma (h)\sigma (h^{\prime })=\sigma (h{h}^{\prime })$：

$$({\Pi }_H^{\sigma }{)}^2=\frac{1}{|H{|}^2}\sum _{h\in H}\sum _{h^{\prime }\in H}\sigma (h{h}^{\prime }).$$

固定 $h$，映射 $h^{\prime }\mapsto h{h}^{\prime }$ 是 $H$ 上的双射，故内层求和 ${\sum }_{h^{\prime }}\sigma (h{h}^{\prime })={\sum }_{h^{\prime \prime }\in H}\sigma (h^{\prime \prime })=|H|{\Pi }_H^{\sigma }$，与 $h$ 无关。外层对 $|H|$ 个 $h$ 求和，得

$$({\Pi }_H^{\sigma }{)}^2=\frac{1}{|H{|}^2}\cdot |H|\cdot |H|{\Pi }_H^{\sigma }={\Pi }_H^{\sigma }.$$

第二步，自伴性。$\sigma$ 是酉表示，故 $\sigma (h{)}^{†}=\sigma (h{)}^{-1}=\sigma (h^{-1})$；而 $h\mapsto h^{-1}$ 是 $H$ 上的双射，所以

$$({\Pi }_H^{\sigma }{)}^{†}=\frac{1}{|H|}\sum _{h\in H}\sigma (h^{-1})={\Pi }_H^{\sigma }.$$

第三步，像等于 $H$-固定子空间。一方面，对任意 $h_0\in H$，重排 $h\mapsto h_{0}h$ 给出

$$\sigma (h_0){\Pi }_H^{\sigma }=\frac{1}{|H|}\sum _{h\in H}\sigma (h_{0}h)={\Pi }_H^{\sigma },$$

因此像中任何向量 $v={\Pi }_H^{\sigma }w$ 都满足 $\sigma (h_0)v=v$，即被 $H$ 固定。另一方面，若 $v$ 被每个 $\sigma (h)$ 固定，则 ${\Pi }_H^{\sigma }v=\frac{1}{|H|}{\sum }_h\sigma (h)v=\frac{1}{|H|}{\sum }_{h}v=v$，即 $v$ 在像中。Q.E.D.

注意 $\mathrm{tr}{\Pi }_H^{\sigma }=\mathrm{rank}{\Pi }_H^{\sigma }$：投影的特征值只有 $0$ 和 $1$，迹就是 $1$ 的个数，即像的维数。这个等式马上要用。

2.3 陪集态的 Fourier 谱

现在把 $F_G$ 作用到陪集态上，看每个 $\sigma$ 块里装着什么。计算完全是机械的，关键是第一步用同态性质把 $\sigma (gh)$ 拆开：

$$\begin{array}{rl}{F}_G|gH⟩& =\frac{1}{\sqrt{|H|}}\sum _{h\in H}\sum _{\sigma }\sqrt{\frac{d_{\sigma }}{|G|}}\sum _{i,j}\sigma (gh{)}_{ij}|\sigma ,i,j⟩\\ & =\frac{1}{\sqrt{|H|}}\sum _{\sigma }\sqrt{\frac{d_{\sigma }}{|G|}}\sum _{i,j}(\sigma (g)\sum _{h\in H}\sigma (h){)}_{ij}|\sigma ,i,j⟩\\ & =\sum _{\sigma }\sqrt{\frac{d_{\sigma }|H|}{|G|}}\sum _{i,j}(\sigma (g){\Pi }_H^{\sigma }{)}_{ij}|\sigma ,i,j⟩,\end{array}$$

其中第二行用了 $\sigma (gh)=\sigma (g)\sigma (h)$ 并把对 $h$ 的求和搬进矩阵乘积；第三行代入 ${\sum }_h\sigma (h)=|H|{\Pi }_H^{\sigma }$，并把 $\sqrt{|H|}$ 乘进归一化因子。

结论：$\sigma$ 块的振幅矩阵正比于

$$\sigma (g){\Pi }_H^{\sigma }.$$

对照 Abelian 情形就能看出质变。Abelian 群的不可约表示全是一维，${\Pi }_H^{\sigma }$ 是 $1\times 1$ 矩阵，只能是 $0$ 或 $1$，于是谱自动退化为 annihilator $H^{\perp }$ 上的均匀分布——每个标签都是一条关于 $H$ 的线性约束。非 Abelian 表示可以是高维的：${\Pi }_H^{\sigma }$ 是一个一般秩大于零的非平凡投影，投影的方向（而不仅仅是秩）携带关于 $H$ 的信息。左乘的 $\sigma (g)$ 则记录陪集的位置。信息都在，但封装在矩阵里，读法不再唯一。

3. 弱采样与强采样

测 Fourier 标签时有一个在 Abelian 情形不存在的自由度：矩阵元基 $|\sigma ,i,j⟩$ 有三个指标，测到什么程度是可选择的。两种极端做法各有名字。

3.1 弱 Fourier 采样：只读表示名

弱 Fourier 采样 (weak Fourier sampling) 只测量表示名 $\sigma$，丢弃行、列指标 $i,j$。由上一节的谱展开，测得 $\sigma$ 的概率是该块振幅的模方和：

$$\begin{array}{rl}p(\sigma )& =\frac{d_{\sigma }|H|}{|G|}\sum _{i,j}\left|\right(\sigma (g){\Pi }_H^{\sigma }{)}_{ij}{|}^2\\ & =\frac{d_{\sigma }|H|}{|G|}\mathrm{tr}\left((\sigma (g){\Pi }_H^{\sigma }{)}^{†}(\sigma (g){\Pi }_H^{\sigma })\right)\\ & =\frac{d_{\sigma }|H|}{|G|}\mathrm{tr}\left({\Pi }_H^{\sigma }\sigma (g{)}^{†}\sigma (g){\Pi }_H^{\sigma }\right)=\frac{d_{\sigma }|H|}{|G|}\mathrm{tr}{\Pi }_H^{\sigma }.\end{array}$$

逐行说明：第一行到第二行用 Frobenius 范数恒等式 ${\sum }_{ij}|A_{ij}{|}^2=\mathrm{tr}(A^{†}A)$；第三行展开厄米共轭（$(AB{)}^{†}=B^{†}{A}^{†}$ 且 $\Pi$ 自伴）；随后 $\sigma (g{)}^{†}\sigma (g)=I$（酉性）与 $({\Pi }_H^{\sigma }{)}^2={\Pi }_H^{\sigma }$（幂等）相继化简。最后用 $\mathrm{tr}{\Pi }_H^{\sigma }=\mathrm{rank}{\Pi }_H^{\sigma }$，得到

$$p(\sigma )=\frac{d_{\sigma }|H|}{|G|}\mathrm{rank}({\Pi }_H^{\sigma }).$$

这个公式里藏着一个重要观察：右端不依赖于陪集代表元 $g$。随机性（落在哪个陪集）完全被酉因子 $\sigma (g)$ 吸收进 Frobenius 范数的不变性中。因此弱采样的分布是 $H$ 的确定的函数，重复采样得到的是同一分布的独立样本。

3.2 概率总和的验证

一个好的一致性检查是验证 ${\sum }_{\sigma }p(\sigma )=1$。这需要一条特征标事实。设 ${\chi }_{\sigma }(x)=\mathrm{tr}\sigma (x)$ 为 $\sigma$ 的特征标。考虑正则表示——$G$ 在 $\mathbb{C}[G]$ 上的左乘作用 $R(x)|y⟩=|xy⟩$。它的特征标可以直接数出来：$R(h)$ 的矩阵在基 $\{|y⟩\}$ 下的对角元计数满足 $hy=y$ 的 $y$ 的个数，而左乘作用在 $h\ne e$ 时没有不动点，故

$${\chi }_R(h)=\{\begin{array}{ll}|G|,& h=e,\\ 0,& h\ne e.\end{array}$$

另一方面，正则表示分解为各不可约表示的直和，其中 $\sigma$ 出现 $d_{\sigma }$ 次（这是 ${\sum }_{\sigma }{d}_{\sigma }^2=|G|$ 的精细形式），取迹得 ${\chi }_R={\sum }_{\sigma }{d}_{\sigma }{\chi }_{\sigma }$。合起来：

$$\sum _{\sigma \in \hat{G}}{d}_{\sigma }{\chi }_{\sigma }(h)=|G|{\delta }_{h,e}.$$

于是

$$\begin{array}{rl}\sum _{\sigma }p(\sigma )& =\frac{|H|}{|G|}\sum _{\sigma }{d}_{\sigma }\mathrm{tr}{\Pi }_H^{\sigma }=\frac{|H|}{|G|}\sum _{\sigma }{d}_{\sigma }\cdot \frac{1}{|H|}\sum _{h\in H}{\chi }_{\sigma }(h)\\ & =\frac{1}{|G|}\sum _{h\in H}(\sum _{\sigma }{d}_{\sigma }{\chi }_{\sigma }(h))=\frac{1}{|G|}\sum _{h\in H}|G|{\delta }_{h,e}=1,\end{array}$$

最后一步因为只有 $h=e$ 一项存活。每一步都有出处：第一行是弱采样公式与 ${\Pi }_H^{\sigma }$ 的定义，第二行交换求和顺序，第三行代入正则表示特征标恒等式。这同时验证了谱展开的归一化确实正确。

3.3 强 Fourier 采样与基的依赖性

强 Fourier 采样 (strong Fourier sampling) 把行、列指标 $i,j$ 也测掉。它的分布有一个 Abelian 情形没有的新特征：依赖表示基的选取。原因不难想见——$\sigma (x{)}_{ij}$ 的数值在换基 $\sigma (x)\mapsto U\sigma (x)U^{†}$ 下会改变，而 ${\Pi }_H^{\sigma }$ 的方向也随之旋转；测量 $i,j$ 正是在探问这个方向。换一组基，同一集合 ${\rho }_H$ 给出的行列分布就变了。因此”强采样有没有用”不是一个纯粹的群论问题，而是”这个群有没有一组好基”的问题——这正是第 5 节中各正结果的实际形态。

把两种采样放在一起总结：

• Abelian 情形：所有 $d_{\sigma }=1$，${\Pi }_H^{\sigma }\in \{0,1\}$，弱采样已经给出全部信息，退化为 $H^{\perp }$ 上的均匀分布。
• 非 Abelian 情形：表示可能高维，$\mathrm{rank}{\Pi }_H^{\sigma }$ 只是投影的维数；仅看秩会把投影的方向信息整个扔掉。弱采样与强采样之间隔着的信息差，就是非 Abelian HSP 比 Abelian 情形难得多的定量来源。

4. 小例子：$S_3$ 中隐藏一个对换

上面的公式都比较抽象，找一个能完整手算的例子把它们全部落实。取最小的非交换群

$$G=S_3,|G|=6,$$

以及由对换生成的二阶子群

$$H=\{e,(12)\},|H|=2.$$

4.1 群与表示

$S_3$ 有三个共轭类，因此恰有三个不可约表示：

• 平凡表示 ${\sigma }_{\mathrm{triv}}$：$d=1$，所有群元映为 $1$；
• 符号表示 ${\sigma }_{\mathrm{sgn}}$：$d=1$，映为置换的符号 $\mathrm{sgn}(x)\in \{+1,-1\}$；
• 标准表示 ${\sigma }_{\mathrm{std}}$：$d=2$，即 $S_3$ 作为正三角形对称群在平面上的自然作用；对换是反射（特征值 $+1,-1$），三循环是旋转 $\pm 2\pi /3$。

维数检查：$1^2+1^2+2^2=6=|G|$，符合维数平方和公式。

4.2 三个投影的秩

由于 $|H|=2$，每个投影都是 ${\Pi }_H^{\sigma }=\frac{1}{2}(I+\sigma ((12)))$，逐个计算。

平凡表示：${\sigma }_{\mathrm{triv}}((12))=1$，故

$${\Pi }_H^{\mathrm{triv}}=\frac{1}{2}(1+1)=1,\mathrm{rank}=1.$$

符号表示：对换是奇置换，${\sigma }_{\mathrm{sgn}}((12))=-1$，故

$${\Pi }_H^{\mathrm{sgn}}=\frac{1}{2}(1-1)=0,\mathrm{rank}=0.$$

标准表示：取一组基使反射 $(12)$ 对角化，${\sigma }_{\mathrm{std}}((12))=\mathrm{diag}(1,-1)$，于是

$${\Pi }_H^{\mathrm{std}}=\frac{1}{2}(I+\mathrm{diag}(1,-1))=\mathrm{diag}(1,0),\mathrm{rank}=1.$$

注意这里能看到 Lemma 1 的第三步在起作用：$\mathrm{diag}(1,0)$ 的像是被反射 $(12)$ 固定的直线——即该反射的对称轴方向。

4.3 弱采样分布与共轭盲区

代入弱采样公式 $p(\sigma )=\frac{d_{\sigma }|H|}{|G|}\mathrm{rank}{\Pi }_H^{\sigma }$，其中 $|H|/|G|=2/6=1/3$：

$$p(\mathrm{triv})=\frac{1}{3}\cdot 1=\frac{1}{3},p(\mathrm{sgn})=\frac{1}{3}\cdot 0=0,p(\mathrm{std})=\frac{2}{3}\cdot 1=\frac{2}{3}.$$

总和 $\frac{1}{3}+0+\frac{2}{3}=1$，与 3.2 节的一般验证一致。弱采样永远看不到符号表示：$H$ 中的对换在符号表示里贡献 $-1$，与单位元的 $+1$ 恰好抵消——这正是”群平均抹掉不含 $H$-不变向量的表示”的一般现象。

现在看关键的一点。换成共轭的子群 $H^{\prime }=\{e,(23)\}$ 或 $H^{\prime \prime }=\{e,(13)\}$ 重新计算：三个对换在 $S_3$ 中互为共轭，特征标在共轭类上取常值，因此每个 ${\chi }_{\sigma }((\cdot ))$ 相同，三个投影的秩与上面完全一样，弱采样分布一字不差。也就是说，弱 Fourier 采样原则上无法区分三个共轭的二阶子群——而它们之间的区别（到底哪个对换在 $H$ 里）恰恰编码在 ${\Pi }_H^{\mathrm{std}}$ 的投影方向中：三个子群各自对应标准表示里三条不同的反射轴。要把方向读出来，就必须测量矩阵指标、并且基要选好——这正是强采样存在的理由，也是它”基依赖”的具体含义。

这个六阶群的玩具模型已经演示了一般理论的全部要点：矩阵值谱、秩与方向的分离、弱采样的共轭盲区。后文的图同构困境，本质上就是这个盲区在 $S_n$ 上的指数级放大。

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

5.1 正规子群：Schur 引理把一切变回 Abelian 情形

有一类非交换 HSP 可以彻底解决：$H$ 是正规子群（记 $H⊴G$，即对所有 $g\in G$ 有 $gH=Hg$）。正规性的推论是 ${\Pi }_H^{\sigma }$ 与整个表示对易：

$${\Pi }_H^{\sigma }\sigma (g)=\frac{1}{|H|}\sum _{h\in H}\sigma (hg)=\frac{1}{|H|}\sum _{h^{\prime }\in H}\sigma (g{h}^{\prime })=\sigma (g){\Pi }_H^{\sigma },$$

其中第二个等号做了代换 $h=g{h}^{\prime }{g}^{-1}$：因为 $H$ 正规，$h^{\prime }$ 随 $h$ 跑遍 $H$。于是 ${\Pi }_H^{\sigma }$ 与不可约表示 $\sigma$ 的所有矩阵对易。Schur 引理断言：与不可约表示全部矩阵对易的算子必为标量阵 $\lambda I$。但 ${\Pi }_H^{\sigma }$ 同时是投影，${\lambda }^2=\lambda$ 迫使 $\lambda \in \{0,1\}$。结论：对不可约的 $\sigma$，

$${\Pi }_H^{\sigma }\in \{0,I\},$$

且 ${\Pi }_H^{\sigma }=I$ 当且仅当每个 $h\in H$ 在 $\sigma$ 中都作用平凡。这与 Abelian 情形中"${\Pi }_H^{\sigma }\in \{0,1\}$"的标量版本完全同构：弱 Fourier 标签于是像 Abelian annihilator 一样，恰好标识出那些穿过商群 $G/H$ 下降的表示（即 $\sigma$ 在 $H$ 上平凡的表示，它们自然地是 $G/H$ 的表示）。采到足够多的标签后，取相应表示核的交即可重构 $H$，正规子群重构可高效完成（Hallgren–Russell–Ta-Shma，Zoo 51）。注意此时商群 $G/H$ 仍可以非交换——正规性抹平的是谱的形式，而不是群本身。

5.2 更多正结果概览

正规情形之外的正结果都依赖具体的群结构，而不是”非 Abelian QFT”四个字本身。几类代表性的进展：

• 某些半直积与 affine 群：可以选择特别的表示基，使强 Fourier 采样暴露隐藏子群；Bacon–Childs–van Dam 对相当广泛的一类群给出了系统性的”好基”构造。这类结果的教训是：基的选择是算法设计的一部分，而非事后细节。
• extraspecial、nilpotency class 2 及若干近 Hamiltonian 群：这些群”离交换不远”——中心很大或所有子群接近正规——可递归地利用中心与交换商，把问题逐层化约到已解决的 Abelian 情形。
• translating coset / hidden translation：把两个函数的相对平移与稳定子群联合求解；这是 hidden shift 一类问题的推广框架，Friedl 等人的工作表明在若干非交换群上仍可高效处理。
• Abelian hypergroup 形式：把部分非交换卷积重新组织为可处理的交换对象，从而在超群层面恢复 Abelian 算法的结构。

5.3 一句必要的警告

上面每一条的输入模型都不相同：群的呈现方式（乘法表、生成元、置换表示、黑盒群运算）、群运算 oracle 的具体形式、以及 QFT 电路的构造，全都因群族而异。不能把某一族的多项式算法外推到任意黑盒群——这正是 Ettinger–Høyer–Knill 的查询上界与”已知高效算法”之间那条鸿沟的日常形态：查询总是够的，电路和后处理要逐族争取。

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

一般理论讲完，转到最重要的单个战场：二面体群。它是”最小的真正困难”的非 Abelian HSP，也是通向格问题的桥梁。

6.1 二面体群与隐藏反射

二面体群写成半直积

$$D_N={\mathbb{Z}}_N⋊{\mathbb{Z}}_2,$$

元素为对 $(x,b)$，$x\in {\mathbb{Z}}_N$，$b\in \{0,1\}$；几何上 $(x,0)$ 是正 $N$ 边形的旋转、$(x,1)$ 是反射。群乘法由”反射共轭旋转会反向”决定，即

$$(x,b)\cdot (y,c)=(x+(-1{)}^{b}y,b+c).$$

具体地，$(x,0)\cdot (y,c)=(x+y,c)$，而 $(x,1)\cdot (y,c)=(x-y,1+c)$——第二个分量 $b=1$ 把 $y$ 送到 $-y$，这正是半直积中 ${\mathbb{Z}}_2$ 对 ${\mathbb{Z}}_N$ 的作用。

取隐藏反射子群

$$H=\{(0,0),(s,1)\},$$

由单个反射 $(s,1)$ 生成，$|H|=2$，$s\in {\mathbb{Z}}_N$ 未知。它是子群因为 $(s,1{)}^2=(s-s,0)=(0,0)$。它的左陪集形如

$$(x,0)H=\{(x,0),(x+s,1)\},$$

即每个陪集把一个旋转和一个反射配成对。Oracle 的”当且仅当”承诺意味着测得函数值后，第一寄存器坍缩到某个随机的陪集对上；忽略均匀随机的全局平移 $x$（它不含 $s$ 的信息），所得状态为

$$\frac{|x,0⟩+|x+s,1⟩}{\sqrt{2}}.$$

6.2 逐步推导相位态

$D_N$ 的完整不可约表示可以用半直积理论列出，但对二阶反射子群，一个更经济的做法足够了：只对 ${\mathbb{Z}}_N$ 坐标做普通的 Abel 群 QFT，${\mathbb{Z}}_2$ 坐标原样保留。记 ${\omega }_N=e^{2\pi i/N}$，$F_N|x⟩=\frac{1}{\sqrt{N}}{\sum }_k{\omega }_N^{kx}|k⟩$。逐步计算：

$$\begin{array}{rl}\frac{|x,0⟩+|x+s,1⟩}{\sqrt{2}}& \stackrel{F_N\otimes I}{\mapsto }\frac{1}{\sqrt{2N}}\sum _{k=0}^{N-1}({\omega }_N^{kx}|k⟩|0⟩+{\omega }_N^{k(x+s)}|k⟩|1⟩)\\ & =\frac{1}{\sqrt{2N}}\sum _{k=0}^{N-1}{\omega }_N^{kx}|k⟩\otimes (|0⟩+{\omega }_N^{ks}|1⟩).\end{array}$$

第二行只是提取公因子 ${\omega }_N^{kx}$。现在测量 $k$ 寄存器：每个 $k$ 的概率为

$$\frac{1}{2N}\cdot \Vert |0⟩+{\omega }_N^{ks}|1⟩{\Vert }^2=\frac{1}{2N}\cdot 2=\frac{1}{N},$$

即 $k$ 均匀随机，与 $s$ 无关——$k$ 寄存器本身不携带信息。测量后剩下一个带标签的相位量子比特

$$|{\psi }_k⟩=\frac{|0⟩+{\omega }_N^{ks}|1⟩}{\sqrt{2}},{\omega }_N=e^{2\pi i/N}.$$

未知 $s$ 已完整编码为相位。每次 oracle 查询产生一个这样的量子比特，标签 $k$ 已知但均匀随机。整个二面体 HSP 就此化约为一个纯量子态问题：给定一堆 $\{|{\psi }_k⟩\}$，求 $s$。

6.3 单个相位量子比特为什么不够

如果 $k$ 可以由我们选择，问题几乎是平凡的：取 $k$ 为 $2$ 的幂，逐位做相位估计即可读出 $s$。但 $k$ 是均匀随机的，这带来三重困难：

• 单个 $|{\psi }_k⟩$ 是一个量子比特，任何测量至多提取一个经典比特（Holevo 界），而 $s$ 有 ${\log }_{2}N$ 比特；
• 态不可克隆，每个陪集态只给一次机会，用完即毁；
• $k$ 的分布不受我们控制，无法保证拿到”好用的”频率。

于是自然的思路是组合多个样本：不单独测量每个相位量子比特，而是让它们两两相互作用，把随机标签加工成越来越”整齐”的标签。这就是 Kuperberg 筛法。

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

7.1 核心操作：两个相位态的加减

取两个样本 $|{\psi }_k⟩|{\psi }_{\ell }⟩$，展开张量积：

$$|{\psi }_k⟩|{\psi }_{\ell }⟩=\frac{1}{2}(|00⟩+{\omega }_N^{\ell s}|01⟩+{\omega }_N^{ks}|10⟩+{\omega }_N^{(k+\ell )s}|11⟩).$$

做一个 CNOT（第一比特控制、第二比特为目标：$|a,b⟩\mapsto |a,b\oplus a⟩$）。四个基矢的映射是 $|00⟩\mapsto |00⟩$、$|01⟩\mapsto |01⟩$、$|10⟩\mapsto |11⟩$、$|11⟩\mapsto |10⟩$，故

$$\stackrel{\mathrm{CNOT}}{\mapsto }\frac{1}{2}(|00⟩+{\omega }_N^{\ell s}|01⟩+{\omega }_N^{(k+\ell )s}|10⟩+{\omega }_N^{ks}|11⟩).$$

按第二比特分组重写：

$$=\frac{1}{2}(|0⟩+{\omega }_N^{(k+\ell )s}|1⟩)|0⟩+\frac{1}{2}({\omega }_N^{\ell s}|0⟩+{\omega }_N^{ks}|1⟩)|1⟩.$$

现在测量第二个量子比特：

• 得 $0$（概率 $1/2$）：第一比特坍缩为 $\frac{|0⟩+{\omega }_N^{(k+\ell )s}|1⟩}{\sqrt{2}}=|{\psi }_{k+\ell }⟩$；
• 得 $1$（概率 $1/2$）：第一比特为 $\frac{{\omega }_N^{\ell s}|0⟩+{\omega }_N^{ks}|1⟩}{\sqrt{2}}={\omega }_N^{\ell s}|{\psi }_{k-\ell }⟩$，其中整体相位 ${\omega }_N^{\ell s}$ 不可观测。

于是可按测量结果得到标签为

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

的新相位态，两种结果都有用（和与差都服从同类分布）。这一步的本质：两个随机频率被加工成一个可加性组合的频率，代价是两份样本变一份。标签的算术从此受我们支配。

7.2 分桶与逐层清零

有了加减操作，就可以组织流水线。固定一个桶宽参数 $b$。一层 (stage) 的操作是：

1. 把当前池中所有态按标签的低 $b$ 位分桶；
2. 在同一桶内两两配对，做 7.1 的合并，需要差时就取 $k-\ell$ 分支；
3. 低位相同的 $k,\ell$ 给出 $k-\ell \equiv 0(\mathrm{mod}{2}^b)$，即新标签可被 $2^b$ 整除。

于是每一层把标签的低 $b$ 位清零。假设第 $t$ 层入口处所有标签都可被 $2^{tb}$ 整除，把它们按接下来的 $b$ 位分桶配对，出口处标签即可被 $2^{(t+1)b}$ 整除。重复”分桶–配对–合并”约 ${\log }_{2}N/b$ 层，低位的零一路蔓延到高位，最终制造出标签接近 $N/2$、$N/4$ 等”高位孤立”的态。

7.3 终点测量：读出 $s$ 的二进制位

为什么标签 $N/2$、$N/4$ 的态是好东西？直接代入相位态定义。若 $N$ 为 $2$ 的幂且 $k=N/2$：

$$|{\psi }_{N/2}⟩=\frac{|0⟩+{\omega }_N^{Ns/2}|1⟩}{\sqrt{2}}=\frac{|0⟩+e^{i\pi s}|1⟩}{\sqrt{2}}=\frac{|0⟩+(-1{)}^s|1⟩}{\sqrt{2}},$$

即 $|+⟩$（$s$ 偶）或 $|-⟩$（$s$ 奇）。在 $X$ 基测一次，精确读出 $s\mathrm{mod}2$。同理，标签 $N/4$ 给出 ${\omega }_N^{Ns/4}=i^s\in \{1,i,-1,-i\}$，态是 $|0⟩+i^s|1⟩$ 的四种之一；在 $X$ 基与 $Y$ 基各测若干份即可确定 $s\mathrm{mod}4$。一般地，在 $X/Y$ 基测量便能读出 $s$ 的二进制信息——筛法的终点把”巨大的随机频率”换成了”逐个二进制位的确定读出”。

7.4 复杂度记账：样本、层数与平衡

现在回答关键问题：整个流水线消耗多少份陪集态？逐项记账。设桶宽为 $b$。

• 每层需要的池子大小。$L$ 个态落入 $2^b$ 个桶，能配成的对数约为 $L^2/2^{b+1}$（生日界的量级）。要让配对机会充足，需要 $L\gtrsim 2^{b+1}$，即池子必须保持约 $2^{\Theta (b)}$ 的规模。
• 每层的存活率。每对消耗两份样本、产出一份，再计入分桶不完全、测量分支等常数损耗，每过一层池子规模乘一个小于 $1$ 的常数因子 $r$。所以第 $t$ 层末的池子约为 $L_0{r}^t$。
• 层数。每层清 $b$ 位，标签共约 ${\log }_{2}N$ 位，故层数 $m=\Theta ((\log N)/b)$。
• 初始样本量。要让流水线活到第 $m$ 层、且终层池子仍有 $2^{\Theta (b)}$ 规模，需要 $L_0{r}^m\gtrsim 2^{\Theta (b)}$，即

$$L_0\approx 2^{\Theta (b)+m{\log }_2(1/r)}=2^{\Theta (b+(\log N)/b)}.$$

总查询数与时间都是这个量级（每层处理是多对一的门操作，经典分桶排序也吸收在同一量级内）。最后一步是参数平衡：总代价指数中有两项，$b$ 与 $(\log N)/b$，一升一降。对 $f(b)=b+c\frac{\log N}{b}$ 求极值，$f^{\prime }(b)=1-\frac{c\log N}{b^2}=0$ 给出

$$b=\Theta \left(\sqrt{\log N}\right),m=\Theta \left(\sqrt{\log N}\right),$$

两项同阶，代回即得总复杂度

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

的时间和查询复杂度。需要说明：上面的存活率、生日界都是启发式记账，严格的组合分析（含各层桶结构的尾部估计）见 Kuperberg 原文；但参数平衡的形态就是”桶宽”与”层数”两项取平。

把这个结果放进坐标系：$\exp (O(\sqrt{\log N}))$ 优于经典 $\Theta (\sqrt{N})$ 查询（因为 $\sqrt{\log N}\ll \frac{1}{2}\log N$），但仍远大于 $\mathrm{poly}(\log N)$——这是一个次指数算法：比任何 $N$ 的多项式都快，比任何 $\log N$ 的多项式都慢。二面体 HSP 因此落在”多项式（Abelian）“与”指数（一般经典）“之间的地带。

7.5 Regev 变体与后续改进

原筛法还有一个实际缺陷：需要 $\exp (O(\sqrt{\log N}))$ 量级的空间——流水线中途必须同时储存指数多个相位量子比特。Regev 的变体用重计算换空间：不保存中间池子，改为在需要时按递归结构重新制备所需样本，达到多项式空间，代价是递归加深带来额外因子，时间为

$$\exp (O(\sqrt{\log N\log \log N})).$$

后续工作继续改善筛法的常数和实现方式，但截至目前的图景未变：尚未得到一般二面体 HSP 的多项式时间量子算法。这道次指数的门槛，正是下一节两个应用故事的分水岭。

8. 与格和图同构的关系

8.1 二面体 HSP 与格问题

Regev 证明：二面体陪集问题与某些 unique shortest vector（唯一最短向量）格问题存在约化——具体地说，若某参数范围内的 DHSP 能被高效求解，则相应近似因子下的唯一最短向量问题也可被高效求解，从而威胁基于该格问题的密码构造。

这条约化值得逐字咀嚼，因为两层保留条款都不可省略：

1. “若能高效解决足够参数范围的 DHSP”。约化只对特定参数范围与特定分布的实例成立；它不是”任意 DHSP 实例随便解”的推论。目前最好的筛法是次指数而非多项式，离”高效解决所需参数范围”尚有本质距离。
2. “这不是’Shor 已破解所有格密码’“。Shor 算法破解的是基于 Abelian 群周期结构（整数分解、离散对数）的密码；格密码的困难性假设不同。已知筛法仍为次指数，并且约化的近似因子和分布承诺必须保留——放松其中任何一条，推出的结论都会变形。

一句话总结：DHSP 与格问题之间有一座已经勘探清楚的桥，但桥上还缺一台多项式时间的发动机。

8.2 图同构与 wreath product

另一个动机是图同构（GI）。编码方式如下：取两个各有 $n$ 个顶点的图，考虑它们不交并上的置换对称。相关的群是 wreath product

$$S_n\wr {\mathbb{Z}}_2,$$

可看作”$S_n$ 作用两份，外加一个交换两份的 ${\mathbb{Z}}_2$“。适当归约后（先处理自同构平凡化的情形），GI 化为该群上的 HSP，且隐藏子群有干净的语义：

• 两图非同构时，没有置换能交换两个图，隐藏子群平凡；
• 两图同构时，隐藏子群含有一个交换两图的元素（阶为 $2$）。

因此一个针对 $S_n\wr {\mathbb{Z}}_2$ 的高效 HSP 算法会立即解决 GI。困难在哪里？回看第 4 节的玩具模型就能猜到大方向：对称群存在维数巨大的不可约表示（其维数随 $n$ 快速增长，远超多项式尺度），而 GI 相关的候选子群彼此共轭。弱采样只看秩——秩由特征标决定、特征标在共轭类上取常值——对共轭子群给出完全相同的分布；常见的单寄存器 Fourier 采样（无论弱还是强）对这类共轭子群几乎不可分，已知分析表明单凭它提取不到足够信息。

于是局面是：Ettinger–Høyer–Knill 保证 $\mathrm{poly}(\log |G|)$ 份陪集态在信息论上足够，但那只证明”存在区分各候选子群的联合测量”；这个联合测量作用在指数维的空间上，没有已知的高效实现。这不是工程上的暂时困难——对 $S_n$ 的表示论结构已有多方面的分析表明，简单的 Fourier 采样路线在此系统性失效。为 GI 的 HSP 路线找到可实现的联合测量（或证明其不可能），仍是该方向的核心开放边界。更多算法视角见图同构专页。

8.3 开放边界

把全课的图景收敛为三句话。其一，非 Abelian HSP 的信息论已经解决（查询多项式即够），卡住的是计算——联合测量与后处理。其二，在这条边界上，二面体群是唯一被攻到次指数深度的非平凡案例，它的每一步前进（Kuperberg、Regev、后续筛法）都直接牵动格密码的假设强度。其三，图同构仍站在边界之外：我们知道陪集态里有答案，但还没有人能高效地把它读出来。

9. 小结与习题

• 非 Abelian QFT 输出矩阵块 $\sigma (g){\Pi }_H^{\sigma }$，而非标量正交约束；${\Pi }_H^{\sigma }=\frac{1}{|H|}{\sum }_{h\in H}\sigma (h)$ 是到 $H$-不变子空间的 Hermitian 投影。
• 弱采样只看不变子空间的维数（$p(\sigma )=\frac{d_{\sigma }|H|}{|G|}\mathrm{rank}{\Pi }_H^{\sigma }$，与陪集 $g$ 无关），强采样还探问投影方向、且依赖表示基；共轭子群在弱采样下不可区分。
• 任意有限群 HSP 的查询复杂度为多项式（Ettinger–Høyer–Knill），但已知最优联合测量的总时间可为指数；查询与运行时间必须分开记账。
• $H$ 正规时 Schur 引理迫使 ${\Pi }_H^{\sigma }\in \{0,I\}$，问题退化回 annihilator 结构，可高效求解；其余正结果（半直积好基、近交换群、hidden translation、Abelian hypergroup）均依赖具体群结构。
• 二面体 HSP 化约为相位量子比特 $|{\psi }_k⟩=\frac{1}{\sqrt{2}}(|0⟩+{\omega }_N^{ks}|1⟩)$ 的标签加工问题；Kuperberg 筛法通过标签的加减逐层提纯频率，参数平衡给出 $\exp (O(\sqrt{\log N}))$ 次指数时间，Regev 变体以 $\exp (O(\sqrt{\log N\log \log N}))$ 时间换取多项式空间。
• 二面体 HSP 经 Regev 约化牵动特定参数范围的格问题；图同构编码为 $S_n\wr {\mathbb{Z}}_2$ 上的 HSP，因对称群高维表示与共轭子群的不可分性而悬而未决。

习题

1. 补全 Lemma 1 的证明细节：验证 ${\Pi }_H^{\sigma }$ 是 Hermitian 投影，并举例说明若把求和范围从 $H$ 换成 $G$ 的一个任意子集，幂等性一般不再成立。有限群中哪一步推理用到了”子集对乘法封闭”？
2. 推导弱 Fourier 采样概率 $p(\sigma )=\frac{d_{\sigma }|H|}{|G|}\mathrm{rank}{\Pi }_H^{\sigma }$，并用正则表示的特征标分解 ${\sum }_{\sigma }{d}_{\sigma }{\chi }_{\sigma }(h)=|G|{\delta }_{h,e}$ 验证 ${\sum }_{\sigma }p(\sigma )=1$。这个恒等式在 Abel 群 ${\mathbb{Z}}_N$ 上退化成什么熟悉的求和公式？
3. 对 $G=S_3$、$H=\{e,(13)\}$，重算三个不可约表示上 ${\Pi }_H^{\sigma }$ 的秩与弱采样分布，确认它与第 4 节 $H=\{e,(12)\}$ 的结果完全相同。再用标准表示中 $(13)$ 的反射轴方向，解释强采样为何仍能区分这两个子群。
4. 解释正规性为什么使 ${\Pi }_H^{\sigma }$ 在不可约块上只能是 $0$ 或 $I$：先证正规子群时 ${\Pi }_H^{\sigma }$ 与所有 $\sigma (g)$ 对易，再引用 Schur 引理与幂等性完成论证。若 $H$ 不正规，上述推理在哪一步断裂？
5. 展开两份 $|{\psi }_k⟩|{\psi }_{\ell }⟩$，验证 CNOT 与测量产生 $k\pm \ell$（包括测量得 $1$ 时整体相位的处理）。再回答：为什么两个分支都有用，而不是把一半样本扔掉？
6. 设 $N=2^m$。写出用标签为 $N/2$ 与 $N/4$ 的相位态读出 $s\mathrm{mod}4$ 的完整测量方案（指明测量基与每种结果的对应比特）。进一步思考：要读出 $s$ 的全部 $m$ 位，筛法终点需要哪些标签的态？这解释了为什么层数按 ${\log }_{2}N/b$ 计。

参考文献与 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。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch10-hidden-structures/nonabelian-hidden-subgroup
• 内容遵循 CC BY-NC-SA 4.0 许可协议