A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

Abstract

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.

Lemma 4.3 is incorrect and cannot be corrected by minor revision. The main algorithm requires the states described in its conclusion, and so must be either reworked or removed