Quantum algorithm for a generalized hidden shift problem

Details Quantum algorithm for a generalized hidden shift problem Quantum algorithm for a generalized hidden shift problem

2005-07-19

arxiv.org/abs/quant-ph/0507190v1

Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1225-1234

Physics

Quantum Physics

16 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum algorithm for a generalized hidden shift problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum algorithm for a generalized hidden shift problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum algorithm for a generalized hidden shift problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-288016