The hidden subgroup problem for infinite groups
Greg Kuperberg (UC Davis)
遵循Shor在整数中进行时期查找的算法的例子,我们探索了离散无限组的隐藏子组问题(HSP)。 在硬度方面,我们表明HSP对于理性数的添加剂组和非非阿贝尔自由组的正常子组来说是NP-硬的。 我们还间接将短向向问题的一个版本减少到 Z^k 的伪多项式查询成本中的 HSP。 在算法方面,我们将 Z^k 中的 HSP 的 Shor-Kitaev 算法(具有标准的多项式查询成本)推广到隐藏子组存在缺陷等级或等效无限索引的情况。 最后,我们概述了阿贝尔隐藏移位问题(AHShP)的拉伸指数时间算法,扩展了作者以及Regev和Peikert的前期工作。 因此,在任何有限生成的 HSP 中,几乎 abelian 组也有一个拉伸的指数时间算法。
Following the example of Shor's algorithm for period-finding in the integers, we explore the hidden subgroup problem (HSP) for discrete infinite groups. On the hardness side, we show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups. We also indirectly reduce a version of the short vector problem to HSP in ℤ^k with pseudo-polynomial query cost. On the algorithm side, we generalize the Shor-Kitaev algorithm for HSP in ℤ^k (with sta...