A subexponential-time quantum algorithm for the dihedral hidden subgroup problem
Skip to main content
Open Access Publications from the University of California

## Published Web Location

https://arxiv.org/pdf/quant-ph/0302112.pdf
No data is associated with this publication.
Abstract

We present a quantum algorithm for the dihedral hidden subgroup problem with time and query complexity $O(\exp(C\sqrt{\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(\sqrt{N})$. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins with the quantum character transform on the group, just as for other hidden subgroup problems. Then it tensors irreducible representations of $D_N$ and extracts summands to obtain target representations. Finally, state tomography on the target representations reveals the hidden subgroup.

Item not freely available? Link broken?
Report a problem accessing this item