隐藏子群问题

隐藏子群问题（HSP）：给定群 $G$ 与函数 $f:G\to X$，满足 $f$ 在某个子群 $H\le G$ 的每个陪集上取常值、不同陪集取不同值，求 $H$。量子解法框架是对 $f$ 的定义域做量子傅里叶采样：制备 $\frac{1}{\sqrt{|G|}}{\sum }_g|g⟩|f(g)⟩$，丢函数值后对 $G$ 的对偶对象做 QFT 并测量，从样本恢复 $H$。

要点

• Abelian 情形完整解决：实例包括 Simon 算法（$G={\mathbb{Z}}_2^n$）、Bernstein-Vazirani（线性结构）、周期查找（$G=\mathbb{Z}$）、离散对数（$G=\mathbb{Z}\times \mathbb{Z}$）——统一推导见 Abelian 隐藏子群问题。
• 非 Abelian 情形是公开前沿：图同构（对称群 $S_n$）与最短格向量（二面体群 $D_n$）都归约为相应 HSP，标准傅里叶采样已知不够——Kuperberg 等筛法给出亚指数算法，详见非 Abelian 隐藏子群问题。
• 变体家族：隐藏平移、隐藏非线性结构、黑盒环与理想（有限黑盒环与理想）可视为框架的松化推广。
• 经典下界：随机查询需要 $\Theta (\sqrt{|G/H|})$ 级别，量子多项式——HSP 是展示”结构 vs 查询”差异的范式问题。

关联词条

• 概念：周期查找、量子傅里叶变换
• 算法：Abelian 隐藏子群问题、非 Abelian 隐藏子群问题、群同构测试

取材：Abelian 隐藏子群问题 的统一推导。

参考文献

• P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 1484 (1997). arXiv:quant-ph/9508027
• S. Hallgren. Polynomial-Time Quantum Algorithms for Pell’s Equation and the Principal Ideal Problem. Proc. 34th ACM STOC, 653 (2002).
• Nielsen & Chuang.《量子计算与量子信息》第 5 章（隐藏子群视角的 Shor 算法）.