论文标题
通用代数的隐藏子组问题
The Hidden Subgroup Problem for Universal Algebras
论文作者
论文摘要
隐藏的亚组问题（HSP）是一个计算问题，包括特殊情况整数分解，离散对数问题，图形同构和最短的向量问题。著名的多项式时间量子算法用于分解和离散对数是Abelian群体对HSP的通用多项式时间量子解决方案的受限制版本，但是尽管有重点研究尚未发现完整的解决方案。我们建议将HSP的概括包括任意代数结构，并分析有关2元素代数的功能的新问题。我们证明了诸如量子拖动（即多项式时间），经典拖延，量子棘手且经典棘手的所有能力的完整分类。特别是，我们确定了一类代数，与经典计算机相比，广义HSP在量子计算机上表现出超级多项式速度。
The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no full solution has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, and classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.
