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 2(O)(root(log N)). In this problem an oracle computes a function f on the dihedral group D-N which is invariant under a hidden reflection in D-N. By contrast, the classical query complexity of DHSP is O(root 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 D-N, 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 D-N. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.