Abelian 隐藏子群：Simon、周期查找与离散对数的统一推导

许多著名量子算法都在做同一件事：一个黑盒函数把群元素按某个未知子群的陪集分组，量子傅里叶变换则把“平移不变性”变成关于对偶群的线性约束。本课完整推导有限 Abel 群上的隐藏子群算法，并从通式逐一恢复 Simon、阶查找和离散对数。

1. 问题定义与输入承诺

设有限 Abel 群已分解为

\[ G=\mathbb Z_{N_1}\times\cdots\times\mathbb Z_{N_m}. \]

未知子群 \(H\le G\) 由函数 \(f:G\to S\) 隐藏，承诺

\[ f(x)=f(y) \quad\Longleftrightarrow\quad x-y\in H. \]

也就是说，\(f\) 在每个陪集 \(x+H\) 上常值，不同陪集取不同值。任务是输出 \(H\) 的一组生成元。该“当且仅当”承诺很重要：若不同陪集偶然碰撞，测量后的状态不再是单个均匀陪集态。

2. 从函数查询得到陪集态

先制备群上的均匀叠加并查询 oracle：

\[ \frac1{\sqrt{|G|}} \sum_{x\in G}|x\rangle|0\rangle \longmapsto \frac1{\sqrt{|G|}} \sum_{x\in G}|x\rangle|f(x)\rangle. \]

测量第二寄存器为 \(f(g)\) 后，第一寄存器坍缩为

\[ |g+H\rangle =\frac1{\sqrt{|H|}} \sum_{h\in H}|g+h\rangle. \]

实际算法可以不显式测量第二寄存器；将它丢弃得到各陪集态的混合，后续第一寄存器的测量统计相同。

3. QFT 为何只留下正交补

对标签 \(y=(y_1,\ldots,y_m)\) 定义特征

\[ \chi_y(x)= \exp\!\left( 2\pi i\sum_{j=1}^m\frac{x_jy_j}{N_j} \right). \]

群 QFT 满足

\[ F_G|x\rangle =\frac1{\sqrt{|G|}} \sum_{y\in G}\chi_y(x)|y\rangle. \]

作用在陪集态上：

\[ \begin{aligned} F_G|g+H\rangle &=\frac1{\sqrt{|H||G|}} \sum_{y\in G}\chi_y(g) \left(\sum_{h\in H}\chi_y(h)\right)|y\rangle. \end{aligned} \]

特征正交关系给出

\[\begin{split} \sum_{h\in H}\chi_y(h)= \begin{cases} |H|,&\chi_y(h)=1\quad\forall h\in H,\\ 0,&\text{否则}. \end{cases} \end{split}\]

定义 annihilator（正交补）

\[ H^\perp= \{y\in G:\chi_y(h)=1, \forall h\in H\}. \]

于是

\[ F_G|g+H\rangle =\sqrt{\frac{|H|}{|G|}} \sum_{y\in H^\perp}\chi_y(g)|y\rangle. \]

测量时相位 \(\chi_y(g)\) 消失，得到 \(H^\perp\) 上的均匀随机样本。未知陪集代表元完全不影响分布，这正是算法能够反复使用随机陪集的原因。

4. 从样本恢复 \(H\)

重复“查询--QFT--测量”得到 \(y^{(1)},y^{(2)},\ldots\in H^\perp\)。有限 Abel 群的随机生成性质保证 \(O(\log|G|)\) 个样本以常数成功率生成整个 \(H^\perp\)；再重复可提高可靠度。

每个样本对未知 \(h=(h_1,\ldots,h_m)\) 给出同余约束

\[ \sum_j\frac{y_jh_j}{N_j}\in\mathbb Z. \]

把分母清除后，使用整数线性代数与 Smith 标准形求这些约束的公共解，即得

\[ H=(H^\perp)^\perp. \]

量子查询次数为 \(O(\log|G|)\)；若群分解、群运算与各 \(\mathbb Z_{N_j}\) 的 QFT 均可高效实现，门复杂度也关于 \(\log|G|\) 为多项式。

5. 三个经典算法作为特例

Simon 问题

\(G=\mathbb Z_2^n\)，\(H=\{0,s\}\)。特征为 \(\chi_y(x)=(-1)^{x\cdot y}\)，所以

\[ y\in H^\perp \quad\Longleftrightarrow\quad y\cdot s=0\pmod2. \]

收集 \(n-1\) 个独立方程即可求 \(s\)。

阶与周期查找

函数 \(f(x)=a^x\bmod N\) 隐藏整数周期 \(r\)。严格说无限群 \(\mathbb Z\) 不能直接放进有限寄存器，Shor 选取足够大的 \(\mathbb Z_Q\) 并做近似 Fourier 采样；测量值满足 \(k/Q\approx j/r\)，再用连分数恢复 \(r\)。

离散对数

若 \(h=g^s\) 且 \(g\) 的阶为 \(r\)，定义

\[ f(x,y)=g^x h^y=g^{x+sy}, \qquad (x,y)\in\mathbb Z_r^2. \]

隐藏子群由 \((-s,1)\) 生成。Fourier 样本 \((u,v)\) 满足

\[ -su+v=0\pmod r. \]

当 \(u\) 可逆时直接得到 \(s=vu^{-1}\pmod r\)；其余样本由线性同余联合处理。

6. 承诺放宽与复杂度边界

某些 HSP 只需一次查询即可产生足够信息，但一般算法使用对数多个陪集态。若 \(f\) 不是严格一一标记陪集，而只是近似周期、给出最高若干位或在小区间多对一，需要重新证明 Fourier 峰没有被噪声淹没；不能直接套用理想承诺下的正交关系。

“指数加速”通常指 oracle 查询模型：经典算法在最坏情况下需观察大量输入才能发现碰撞。若 oracle 本身难以相干实现，或群分解未知，完整时间可能包含额外代价。本章下一课将看到，非 Abelian 情形甚至会出现“查询是多项式、总时间仍指数”的明显分离。

7. 小结与习题

  • 函数查询产生随机陪集态。

  • Abelian QFT 将陪集平移不变性变为 \(H^\perp\) 上的支撑。

  • 多个 Fourier 样本给出同余方程，Smith 标准形恢复 \(H\)。

  • Simon、Shor 周期查找和离散对数只是群与子群选择不同。

  1. 证明 \(|H||H^\perp|=|G|\)。

  2. 对 \(G=\mathbb Z_{12}\)、\(H=\langle4\rangle\) 写出全部 \(H^\perp\)。

  3. 从 \(f(x,y)=g^{x+sy}\) 推导离散对数样本方程。

  4. 解释测量第二寄存器与直接丢弃它为什么给出相同的第一寄存器统计。

参考文献

  • Zoo 编号 14：D. Boneh 与 R. Lipton, Quantum Cryptanalysis of Hidden Linear Functions, CRYPTO 1995。

  • Zoo 编号 108：Daniel Simon, On the Power of Quantum Computation, FOCS 1994。

  • Zoo 编号 76：Michael Nielsen 与 Isaac Chuang, Quantum Computation and Quantum Information, 第 5 章。

  • Zoo 编号 30：J. Niel de Beaudrap、Richard Cleve 与 John Watrous, Sharp Quantum versus Classical Query Complexity Separations.

  • Zoo 编号 388：Lisa Hales 与 Sean Hallgren, An Improved Quantum Fourier Transform Algorithm and Applications, FOCS 2000。

  • Zoo 编号 389：Igor Shparlinski 与 Arne Winterhof, Quantum Period Reconstruction of Approximate Sequences, IPL 2007。