2003/02/28 by Greg Kuperberg · 1 citation
Mathematics · Physics and Astronomy · #math.RT #quant-ph
published as SIAM J. Comput. 35 (2005), 170-188 · 11 pages. Revised in response to referee reports. Early sections are more accessible; expanded section on other hidden subgroup problems
arxiv created 2004/12/20 · arxiv updated 2019/09/16
We present a quantum algorithm for the dihedral hidden subgroup problem with time and query complexity O(exp(C√(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 with the quantum character transform on the group, just as for other hidden subgroup problems. Then it tensors irreducible representations of DN and extracts summands to obtain target representations. Finally, state tomography on the target representations reveals the hidden subgroup.