论文标题
二面体隐藏子组问题的量子多项式时间解决方案
A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem
论文作者
论文摘要
我们为隐藏子组问题$ \ mathbb {d} _ {2^n} $提出了一个多项式时间量子算法。隐藏子组问题的通常方法依赖于问题域中的谐波分析，使用此方法的最著名算法在$ 2^{\ Mathcal {O}（\ sqrt {n}）} $中具有时间复杂性。通过关注问题的编码结构，我们开发了一种多项式时间算法，该算法使用该结构将“步行”沿$ \ Mathbb {d} _ {2^n} $终止在隐藏子组处终止的子组晶格。
We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over $\mathbb{D}_{2^n}$. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in $2^{\mathcal{O}(\sqrt{n})}$. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of $\mathbb{D}_{2^n}$ terminating at the hidden subgroup.
