



01092nas a2200121   4500008004100000245006100041210006100102260001500163520070800178100002300886700001700909856004400926       2005                        eng d00aQuantum algorithm for a generalized hidden shift problem0 aQuantum algorithm for a generalized hidden shift problem  c2005/07/193 a  Consider the following generalized hidden shift problem: given a function f
on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the
unknown shift s in Z_N. For M=N, this problem is an instance of the abelian
hidden subgroup problem, which can be solved efficiently on a quantum computer,
whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for
which no efficient algorithm is known. For any fixed positive epsilon, we give
an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M
> N^epsilon. The algorithm is based on the "pretty good measurement" and uses
H. Lenstra's (classical) algorithm for integer programming as a subroutine.
1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/quant-ph/0507190v1