On Quantum Algorithms for Noncommutative Hidden Subgroups
On Quantum Algorithms for Noncommutative Hidden Subgroups
复制标题
非交换隐子群的量子算法
DOI：
10.1007/3-540-49116-3_45
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
P. Høyer
中科院分区：
文献类型：
--
作者：
Mark Ettinger;P. Høyer
量子算法的因式分解和寻找离散的代数先前已被推广到寻找隐藏的子群有限阿贝尔群。本文探讨的可能性，扩大这一一般的观点，以寻找隐藏的非交换群的子群。我们提出了一个量子算法的特殊情况下，二面角群，确定隐藏的子群在一个线性数量的调用输入函数。我们还探讨了开发一种算法来处理数据，明确计算一个子群的生成集的困难。非交换隐子群问题的一般框架进行了讨论，我们指出未来的研究方向。
Quantum algorithms for factoring and finding discrete logarithms have previously been generalized to finding hidden subgroups of finite Abelian groups. This paper explores the possibility of extending this general viewpoint to finding hidden subgroups of noncommutative groups. We present a quantum algorithm for the special case of dihedral groups which determines the hidden subgroup in a linear number of calls to the input function. We also explore the difficulties of developing an algorithm to process the data to explicitly calculate a generating set for the subgroup. A general framework for the noncommutative hidden subgroup problem is discussed and we indicate future research directions.