量子科技中心_量科网

继Shor整数周期发现算法的范例之后，该研究团队针对离散无限群的隐子群问题（HSP）展开探索。在计算难度方面，研究人员证明HSP对于有理数加法群以及非阿贝尔自由群的正规子群具有NP困难性，并通过伪多项式查询代价将短向量问题的一个变体间接归约到Z^k空间中的HSP问题。在算法层面，该工作将Z^k空间（标准多项式查询代价）的Shor-Kitaev算法推广至隐子群秩缺失或等价无限指数的情形。最后，该团队基于作者先前成果及Regev与Peikert的研究，提出了阿贝尔隐位移问题（AHShP）的拉伸指数时间算法框架。由此可推知，任何有限生成、拟阿贝尔群中的HSP问题同样存在拉伸指数时间解法。