A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity 2O(√log\ N). In this problem an oracle computes a function f on the dihedral group DN which is invariant under a hidden reflection in DN. By contrast, the classical query complexity of DHSP is O(√N). The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of DN is essentially the abelian quantum Fourier transform. This yields the name of a group representation of DN, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of DN. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.