论文标题
用于解决隐藏子组问题的多项式时间量子算法
Polynomial-time quantum algorithm for solving the hidden subgroup problem
论文作者
论文摘要
隐藏的亚组问题〜（HSP）是量子计算中最重要的问题之一。量子算法在其经典对应物上实现指数加速的许多问题可以减少到Abelian HSP。但是，没有有效的量子算法来求解非亚伯HSP。我们发现，可以通过多步量子计算使用量子算法来将HSP简化为嵌套的结构化搜索问题，该问题通过使用量子算法有效地解决。然后，我们通过使用该算法解决了在多项式时间内可以将HSP和可以简化为Abelian和非阿贝尔HSP的问题。
The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.
